5
\$\begingroup\$

I implemented the group function:

group' :: (Ord a) => [a] -> [[a]]
group' [] = []
group' xs = takeWhile (== head' xs) (sorted xs) : 
                           (group' $ dropWhile (== head' xs) (sorted xs))
                    where sorted ys   = mergesort' (ys)
                          head' (x:_) = x

Note - please assume mergesort is implemented properly.

Its signature is: [a] -> [a] where the latter list is sorted.

How's it look? Is head''s pattern matching exhaustive? It seems to me it is since group xs will only be reached if group's argument is non-empty, i.e. it'll always have a head.

\$\endgroup\$
5
\$\begingroup\$

You have made some uncommon stylistic choices which are not to your benefit, and a few things aren't doing what I think you think they're doing.

First, the stylistic elements. Your whitespace is excessive, there's no need to push everything that far to the right and out of line with the beginning of the RHS. I also would move the colon down to begin the next line, this is mostly a matter of personal style. The parentheses around ys are unnecessary and while harmless noise for the compiler will distract your human reader. My version would look like this.

group' xs = takeWhile (== head' xs) (sorted xs)
          : group' (dropWhile (== head' xs) (sorted xs))
    where sorted ys   = mergesort' ys
          head' (x:_) = x

Now to the meat of it. As it is, your definition of sorted is just giving a different name to mergesort'. The two uses in the main body of the function will cause sorted xs to be recomputed each time (ie twice!). The correct definition is not to create an inner function which is passed a list to be sorted as a parameter, but to bind a sorted version of the outer function's parameter.

group' xs = takeWhile (== x) sorted : group' (dropWhile (== x) sorted)
    where sorted = mergesort' xs -- Computed once, the result is used twice
          x = head sorted

You'll notice that I gave the same treatment to head', this is less of a performance hit and more a matter of consistency. If you wanted to be really pedantic you could bind the section as well, but (and this is an art not a science) I feel that this version is less readable.

group' xs = takeWhile p sorted : ...
    where ...
          p = (== head sorted)

This is still doing more work than it needs though! Once you've made the first recursive call, the tail passed to group' will always already be sorted, and doesn't need to be resorted with each recursive step. One way to handle this would be to pull the main functionality of group' into an inner function named something like group'' and change the body of group' to just be group'' (mergesort' xs). Now the list is only sorted once.

I think it makes more sense though to separate the two functions entirely. There is in fact no requirement that the list being grouped is sorted, so let's relax that constraint.

group' :: (Eq a) => [a] -> [[a]]
group' []     = []
group' (x:xs) = (x : takeWhile (== x) xs) : group' (dropWhile (== x) xs)

elementSets :: (Ord a) => [a] -> [[a]] -- Same functionality as original group'
elementSets = group' . mergeSort'

And just so you see what's happening,

> group' [2,2,1,2,2,2]
[[2,2],[1],[2,2,2]]
> elementSets [2,2,1,2,2,2]
[[1],[2,2,2,2,2]]

Note that we can now find the head of the list through pattern matching instead of calling head because we don't need to assume the list may be out of order. We do however have to remember to add that element back to the prefix of what we're returning!

There's one more improvement we can make though! As it is, our group' function will walk the prefix of the list equal to the first element twice each recursive step (once for takeWhile, and once for dropWhile). We can eliminate that inefficiency by using span which returns the prefix matching the predicate and the remainder in one go.

group' (x:xs) = (x : prefix) : group' remainder
    where (prefix, remainder) = span (== x) xs

And there we have it.

Regarding your question about whether head''s pattern matching was exhaustive, the answer is that it is not exhaustive because the definition of head' contained no case which would match every possible pattern (ie head' []). It was however "safe" to use because of how group' was defined, and the case of the empty list was handled through pattern matching at the outer level. In general you shouldn't rely on tricky business like that, it can be difficult to notice when coming back to code you or someone else has written, and can blow up on you if you have to change the definition of the function.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks! Besides your excellent, detailed post, I especially learned from your last sentence - ` In general you shouldn't rely on tricky business like that` \$\endgroup\$ – Kevin Meredith May 9 '14 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.