Critique of code form Real World Haskell, Chapter 3 exercise [closed]

Question

I'm working through Real World Haskell, and at the moment doing the exercises at the end of Chapter 3.

I'm taking an unusual approach: even though I know there are some language features they haven't covered yet that would help me, I am trying to do these exercises using only things they have explicitly covered. Why? Just kind of for fun really. It feels like it is forcing me to give my brain some extra practice with recursion.

So I just completed the exercise posed as follows: "Create a function that sorts a list of lists based on the length of each sublist. (You may want to look at the sortBy function from the Data.List module.)"

Now, they threw in the hint about the Data.List module. But they didn't say a word about where reference doc can be found, about how to import stuff, etc. So I decided to roll my own sort just to see if I could do it. I used Bubble Sort since it's the simplest algorithm.

The result is below. I'd like to get you Haskell gurus to critique it please ... but with the following caveat in mind: If you suggest improvements, please base them on language features covered through chapter 3 of Real World Haskell (or what you guess those features might be without going to the trouble of looking it up). I know there are tons of awesome language features waiting for me that will let me make this code better, but right now the specific challenge was to do it with the "primitive" features covered so far.

I'm sure there are cases where I'm reaching around my shoulder to scratch my elbow, cases where I'm using explicit control flow when recursion and pattern matching could do more for me, etc. I'm sure the code could be made much shorter and more readable too. I bet there are good idioms I don't know about that can be used with the primitive language features I'm limiting myself to. Those are the kinds of tips I'd love to receive.

This is probably the ugliest code I'm proud of in any language (at least, that I can remember). My first stab, in a functional language, at something beyond "Hello, world" type stuff. And now you are going to beat the crap out of it :) . Be gentle, please, but I'm looking forward to some meaty insight. Thanks.

areListsEqual :: (Eq a) => [a] -> [a] -> Bool

areListsEqual [] [] = True
areListsEqual [] _  = False
areListsEqual _ []  = False

areListsEqual xs ys = (head xs == head ys)  && (areListsEqual (tail xs) (tail ys))

charlieSort :: (Eq a) => [[a]] -> [[a]]

charlieSort [] = []
charlieSort (x:xs) | null xs = [x]
charlieSort xs | (length xs) >= 2 = if(not (areListsEqual xs wip))
                    then charlieSort wip 
                    else wip
                    where
                      first = head xs
                      second = head (tail xs)
                      theRest = drop 2 xs
                      swapPairIfNeeded a b = if(length a >= length b) 
                          then [second, first]
                          else [first, second]
                      modifiedPair = swapPairIfNeeded first second
                      wip = (take 1 modifiedPair) ++ charlieSort ( (drop 1 modifiedPair) ++ theRest)

Answer 1

Charlie: I'll confine myself to a single critique: never use head, tail, or length if you can use pattern matching:

areListsEqual [] [] = True
areListsEqual (x:xs) (y:ys) = x == y && areListsEqual xs ys
areListsEqual _ _   = False

I can't follow your sort algorithm (and it would be courteous of you to reformat your question so as to eliminate the horizontal scroll bar), but I'd rewrite the first three lines like this:

charlieSort []  = []
charlieSort [x] = x
charlieSort (x1:x2:xs) = if ...

(P.S. All uses of head and tail can be rewritten using pattern matching, and beginners should do so. Not all uses of length can be replaced by pattern matching, but common noob codes like length xs == 0 or length xs >= 2 can and should be rewritten.)

(P.P.S. Even experienced Haskell programmers seldom use 'head'. Less than two-tenths of one percent of source lines in the Glasgow Haskell compiler mention 'head', and eyeballing those mentions, roughly half are in string literals or comments. That's approximately one use of 'head' for every 1500 lines of code.)

Answer 2

You don't need the areListsEqual function. You can compare lists with the (==) function. And I'd use a quicksort rather than bubblesort. Here's a solution that I think uses only what you should have learned so far.

charlieSort :: (Eq a) => [[a]] -> [[a]]
charlieSort []     = []
charlieSort (x:xs) = charlieSort (filter (cmpLen (>) x) xs) ++ [x] ++
                     charlieSort (filter (cmpLen (<=) x) xs)
   where filter _ [] = []
         filter p (x:xs) = (if (p x) then (x:) else id) (filter p xs)
         cmpLen f x y = f (length x) (length y)

Answer 3

I'm on chapter 8, so I'm no old hand, but I'd prefer

areListsEqual x:xs y:ys = (x == y) && (areListsEqual xs ys)
areListsEqual [] [] = True
areListsEqual _ _ = False

It seems a bit more in line with Haskell style.

Similarly,

charlieSort [] = []
charlieSort (x:[]) = [x]
charlieSort (x1:x2:xs) = blah blah

swapPairIfNeed works as is because you only call it with first and second as its arguments (in that order), but you probably meant

swapPairIfNeed a b = if (length a >= length b)
    then [b, a]
    else [a, b]

In fact, I prefer the third case of charlieSort to look like

charlieSort (x1:x2:xs) = if not (areListsEqual x1:x2:xs wip)
                         then charlieSort wip
                         else wip
    where swapPairIfNeeded a b = if (length a >= length b)
                                 then (b, a)
                                 else (a, b)
          wip = f (swapPairIfNeeded first second)
          f (a, b) = a : (charlieSort b:xs)

I think this was all covered by chapter 3.

Now, let's examine the algorithm. Even holding ourselves to bubble sort, there's no need to check the whole list after sorting. Instead, we can swap the first two elements if necessary, then sort the tail of the list. If the head is shorter than the head of the sorted tail, we're done.

charlieSort (x1:x2:xs) = if (length a <= length (head sortedTail))
                         then a : sortedTail
                         else charlieSort (a : sortedTail)
    where sortedTail = charlieSort (b:xs)
          (a, b) = if (length x1 >= length x2)
                   then (x2, x1)
                   else (x1, x2)

Answer 4

You claim that bubble sort is the easiest sorting algorithm, but that's not quite the case here. Bubble sort is great for arrays, where you index into them linearly. For Haskell's linked lists, insertion sort is actually much prettier to look at.

Let's start with the insert function:

winsert :: [a] -> [[a]] -> [[a]]
winsert x [] = [x]
winsert x (y:ys)
    | length x < length y = x : y : ys
    | otherwise = y : winsert x ys

• If the list is empty, put x into it
• If the list isn't empty:
  • If x < y, then x belongs at the front of the list
  • Otherwise, the head of the list is y, and the tail is made of up x being inserted somewhere into ys.

Next, we have the actual sorting function:

wsort :: [[a]] -> [[a]]
wsort [] = []
wsort [x] = [x]
wsort (x:xs) = winsert x (wsort xs)

• If the list is empty, return it
• If the list has only one item, it doesn't need to be sorted
• If the list is longer than that, sort xs, then insert x into the now sorted xs

Interestingly, by modifying winsert to take a function as an argument (in place of length), wsort could be used to sort based on all kinds of criteria. Try making one that sort a list of lists based on the sum of each sublist.