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.
Merge sorting a list of lists in Haskell
First off this is a homework assignment, but we''re slightly stumped. So, without further ado here''s the code:
replace the first line with the correct:
[edited by - DigitalDelusion on October 23, 2003 12:43:15 PM]
msort :: [Int] -> [Int] or even better for generalitymsort :: Ord a => [a] -> [a]
[edited by - DigitalDelusion on October 23, 2003 12:43:15 PM]
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]
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.
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.
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])
a quick hack to solve your troubles would be changeing the first line and then adding a function like
merge_sort :: [[a]] -> [a]merge_sort x = msort (concat x)
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!
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.
[edited by - DigitalDelusion on October 24, 2003 1:29:14 PM]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement