Archived

This topic is now archived and is closed to further replies.

Crispy

Merge sorting a list of lists in Haskell

Recommended Posts

First off this is a homework assignment, but we''re slightly stumped. So, without further ado here''s the code:
msort :: [[Int]] -> [Int]
msort xs | n <= 1        = xs
         | otherwise     = merge (msort us) (msort vs)
           where   n       = length xs
                   us      = take (n `div` 2) xs
                   vs      = drop (n `div` 2) xs                 
                   merge []     ys     = ys
                   merge xs     []     = xs
                   merge (x:xs) (y:ys) | x < y     = x : merge xs (y:ys)
                                       | otherwise = y : merge (x:xs) ys
The problem lies with line 3 (the one with "otherwise" in t). The error it produces is: "Type error in guarded expression; Type: [Int]; Does not match [[Int]];". Evidently this suggests that the type of the returned data type is a list of lists while it should be a list. Can anyone spot a mistake in here? This is actually pretty urgent so any suggestions would be very welcome.

Share this post


Link to post
Share on other sites
The first line is correct: the function expects a list of lists and returns a sorted list of all of the elements in the input. For instance: [[2, 3, 4], [3, 4, 2, 5]] should return [2, 2, 3, 3, 4, 4, 5]

Share this post


Link to post
Share on other sites
I don''t know why you would think that this code merges a list of lists. Merge clearly takes a list of some ordered type, and msort clearly partitions the list of an ordered type into two parts, then merges that list. Nowhere in your code do you take a list and return an element that is a list. You''ll probably need to add head somewhere. I''ll play with it and see what I can do.

Share this post


Link to post
Share on other sites
Really changeing the first line makes it sort an undorded list, trust me. If you want to sort multiple lists just use concatenate to first create a single list.

Also your spliting functions is wildly innefficent.
this is slightly more to write (but can be reduced this is done for clarity) but here the spltting in it self is 3times faster than your version.


msort :: [a] -> [a]
msort [xs] = [xs]
msort xs = merge (msort a) (msort b)
where
(a,b) = split xs
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x < y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys

split:: [a] -> ([a],[a])
split x = accum0 x [] []
where
accum0 :: [a] -> [a] -> [a] -> ([a],[a])
accum0 [] acc0 acc1 = (acc0, acc1)
accum0 (h:t) acc0 acc1 = accum1 t (acc0 ++ [h]) acc1
accum1 :: [a] -> [a] -> [a] -> ([a],[a])
accum1 [] acc0 acc1 = (acc0, acc1)
accum1 (h:t) acc0 acc1 = accum0 t acc0 (acc1 ++ [h])

Share this post


Link to post
Share on other sites
I''d like to thank you for the reply and the code, Digital. We''re only learning functional programming for the second month just now, so the solutions we come up with aren''t generally very elegant. I personally am having a lot of trouble alienating myself from the more traditional imperative thinking model. True, I haven''t yet quite understood your code 100%, but hopefully a little bit of staring at it will help. Once again, cheers!

Share this post


Link to post
Share on other sites
The split function uses a technique called "accumulation in parameter" it's very usefull and can solve quite many performance problems. Basicly what the split function does is that it creates a tuple of lists where each component contains half of the elemnts from the original list. It does this by taking one element from the list and inserting it into the tuple list alternating what component to add to.

A shorter faster split is given below also this version uses only recursion to solve the problem.

split :: [a] -> ([a],[a])
split [] = ([],[])
split (a:[]) = ([a],[])
split (a:b:t) = (a:x, b:y)
where (x,y) = split t


[edited by - DigitalDelusion on October 24, 2003 1:29:14 PM]

Share this post


Link to post
Share on other sites