Geek Answers Handbook

Haskell Merging Multiple Lists

I want to write a merge function that takes several sorted lists of x and combines them into only one sorted list using incremental values ​​(from minimum to largest). I think that I can make two lists and combine them into one, but I can’t determine the base case for several lists and combine them into one sorted one.

merge :: [[a]] -> [a]
+4
source share
5 answers
Answer to

@ sepp2k is good, but it only works on a finite number of input lists. If you give an infinite number of lists, you will always find the minimum initial element.

We can fix this by requiring that the input lists are already sorted by increasing the first elements. Then we know that we can get the “top left” element (the first element of the first list), because it will be the lower border for everything that gives us enough information to use recursively and create a complete merge.

 merge :: (Ord a) => [[a]] -> [a] merge [] = [] merge ([]:xss) = merge xss merge ((x:xs):xss) = x : merge2 xs (merge xss)

Writing merge2 is still left as an exercise for the reader merge2

+6
source

Perhaps a faster implementation:

 mergeTwo :: Ord a => [a] -> [a] -> [a] mergeTwo x [] = x mergeTwo [] x = x mergeTwo (x:xs) (y:ys) = if x < y then x:(mergeTwo xs (y:ys)) else y:(mergeTwo (x:xs) ys) mergePairs :: Ord a => [[a]] -> [[a]] mergePairs [] = [] mergePairs (x:[]) = [x] mergePairs (x:y:tail) = mergePairs ((mergeTwo xy):(mergePairs tail)) mergeAll :: Ord a => [[a]] -> [a] mergeAll [] = [] mergeAll x = head $ mergePairs x

mergeTwo simply combines two lists. mergeAll just launches mergePairs and returns the head, if any. The magic happens in mergePairs, which takes a list of lists and combines pairs, than does it again and so on, while there are at least two lists.

It may be faster, imagine that you are working

 merge = foldl merge2 []

It takes one long list and merges and merges. If you run it in [[1,2,3], [4,5,6], [7,8,9], [10,11,12]], it combines:

[] with [1,2,3]

[1,2,3] s [4,5,6]

[1,2,3,4,5,6] s [7,8,9]

[1,2,3,4,5,6,7,8,9] with [10,11,12]

But you want to keep lists about the same length. So you want to combine:

[1,2,3] s [4,5,6]

[7,8,9] s [10,11,12]

[1,2,3,4,5,6] s [7,8,9,10,11,12]

You can also consider the parallel implementation of mergePairs, this can be useful for multi-core processors. But I have no experience with this: /

+9
source

If you can define a function for two lists, you can generalize it to arbitrarily many lists by simply going through each sublist and combining it with the current result until you combine all the lists. This can be expressed as a crease:

 merge = foldr merge2 []
+7
source

This is much simpler if you combine the lists first with concat and then sort .

 import Data.List(sort) mergeSort = sort . concat
+3
source 
 import Data.List ( sort ) sortLists :: (Ord a) => [[a]] -> [a] sortLists cs = concatMap sort cs test = [ [3,1,2], [5,4], [6,8,9,7] ] main = print $ sortLists test

To truly enjoy the hackell, take a close look and memorize Prelude and Data.List . This is the bread and butter of every Haskell programmer.

-3
source

More articles:


All Articles