StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I would first and foremost start using pattern-matching.</p> <pre><code>areListsEqual :: Eq a => [a] -> [a] -> Bool areListsEqual [ ] [ ] = True areListsEqual [ ] _ = False areListsEqual _ [ ] = False areListsEqual (x:xs) (y:ys) = x == y && areListsEqual xs ys </code></pre> <p>Note how much more readable this is, when <code>head</code> and <code>tail</code> is avoided.</p> <pre><code>charlieSort :: Eq a => [[a]] -> [[a]] charlieSort [ ] = [] charlieSort [x ] = [x] charlieSort xs@(first:second:theRest) | areListsEqual xs wip = wip | otherwise = charlieSort wip where swapPairIfNeeded a b | length a >= length b = [second,first] | otherwise = [first,second] modifiedPair = swapPairIfNeeded first second wip = take 1 modifiedPair ++ charlieSort (drop 1 modifiedPair ++ theRest) </code></pre> <p>I changed the <code>if</code>-<code>then</code>-<code>else</code> to a guard for slightly improved readability (YMMV). Instead of checking that the list has at least two elements with a call to <code>length</code> we use pattern-matching, which also allows us to name <code>first</code>,<code>second</code>,<code>theRest</code> directly. The <code>name @ pattern</code> pattern both matches the input against <code>pattern</code> <em>and</em> names the whole input as <code>name</code>.</p> <p>Now, I want to avoid using <code>take</code> and <code>drop</code> for extracting the two elements of <code>modifiedPair</code>, so the last two lines are changed into</p> <pre><code> [shorter,longer] = swapPairIfNeeded first second wip = [shorter] ++ charlieSort ([longer] ++ theRest) </code></pre> <p>where you could write the last line as</p> <pre><code> wip = shorter : charlieSort (longer : theRest) </code></pre> <p>if you preferred. But why should <code>swapPairIfNeeded</code> return the <code>shorter</code> and the <code>longer</code> of the <code>first</code> and <code>second</code> list in a <em>list</em> ? Why not use a pair like</p> <pre><code> swapPairIfNeeded a b | length a >= length b = (second,first) | otherwise = (first,second) (shorter,longer) = swapPairIfNeeded first second </code></pre> <p>? In most circumstances, it is better to use tuples for fixed number of values (possibly of differing types) and to use lists for variable number of values (necessarily of same type). But it seems strange that <code>swapPairIfNeeded</code> compares its arguments <code>a</code> and <code>b</code>, but then returns <code>first</code> and <code>second</code> anyway. In this case, instead of letting it return <code>a</code> and <code>b</code> in a pair, I will remove <code>swapPairIfNeeded</code> altogether instead :</p> <pre><code> (shorter,longer) | length first >= length second = (second,first) | otherwise = (first,second) </code></pre> <p>"unfolding" the body of <code>swapPairIfNeeded</code> into the definition of <code>(shorter,longer)</code>.</p> <p>So now the code of <code>charlieSort</code> looks like</p> <pre><code>charlieSort :: Eq a => [[a]] -> [[a]] charlieSort [ ] = [] charlieSort [x ] = [x] charlieSort xs@(first:second:theRest) | areListsEqual xs wip = wip | otherwise = charlieSort wip where (shorter,longer) | length first >= length second = (second,first) | otherwise = (first,second) wip = shorter : charlieSort (longer : theRest) </code></pre> <p>Finally, I should remark that <code>charlieSort</code> doesn't really implement bubble-sort, because the recursive call to <code>charlieSort</code> will not only make one "bubble-up" pass along the list, but also fully sort the list <code>longer : theRest</code>, so that all that has to be done after this recursive call (before returning one "level up") is to possibly percolate <code>shorter</code> to its rightful place.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload