Haskell Problem

Write a function  merge :: (Ord a) => [[a]] -> [a] that
takes a finite list of sorted finite lists and merges them into a single sorted
list. A “sorted list” means a list sorted in increasing order (using <); you
may assume that the sorted lists are finite. For example
merge ([[]]::[[Int]]) = [] :: [Int]
merge [[1, 2, 3]] = [1, 2, 3]
merge [[1, 3, 5, 7], [2, 4, 6]] = [1,
2, 3, 4, 5, 6, 7]
merge [[1,3,5,7], [2,4,6],
[3,5,9,10,11,12]] =
[1,2,3,3,4,5,5,6,7,9,10,11,12]
take 8 (merge [[1, 3, 5, 7],
[1,2,3,4,5,6,7,8]]) = [1, 1, 2, 3, 3,
4, 5, 5]

merge = sort.concat

mhmmm

>>2

This doesn't take advantage of the fact that the lists are already sorted.

See this question on SO: http://stackoverflow.com/questions/941699/merge-sorted-inputs-in-haskell

>>4
but that doesn't take advantage of abstraction already in place. It took me literally 10 seconds to come up with merge = sort.concat, but there's no telling how long the other solutions took. It all depends on whether that tiny boost in optimization is worth the time it took to code it

>>5

Of course. I fully admit that your solution is a lot prettier.

Uh so... solve the merge step of the merge sort? Why not just say "write a merge sort"?

HURR DURR HASKELL

>>8
HURR DURR
Stop that.


merge [l] = l
merge ls = merge (mergeStep [] ls)

mergeStep acc [] = acc
mergeStep acc [l] = l : acc
mergeStep acc (l1 : l2 : ls) = mergeStep acc' ls
  where acc' = mergeTwo l1 l2 : acc

mergeTwo xs [] = xs
mergeTwo [] ys = ys
mergeTwo (x:xs) (y:ys) = a : mergeTwo as bs
  where a = min x y
        (as, bs) = if a == x then (xs, y:ys) else (ys, x:xs)

Maybe something like this?

>>7
Pretty much.

>>9
fuck you fag