Haskell合并多个列表

Question

我想编写一个合并函数，它采用多个x排序列表，并通过增量值（从最小到最大）将它们合并到一个排序列表中。我想我可以做两个列表并合并为一个，但不能找出多个列表的基本情况并组合成一个排序。

merge :: [[a]] -> [a] 

Answer 1

@ sepp2k的回答是不错的，但它只能在有限多输入列表。如果你给它无限多的列表，它将永远试图找到最小的起始元素。

我们可以通过要求输入列表已经通过提高第一要素来分类的解决这个问题。然后我们知道我们可以产生“左上角”元素（第一个列表的第一个元素），因为它将是所有事物的下界，这给了我们足够的信息来递归地使用并产生完整的合并。

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

写作merge2仍然留下作为练习读者:-)

Answer 2

如果你可以定义两个列表的功能，那么你就可以概括它任意多个列表，只需通过每个子列表会与当前结果合并，直到你已经合并所有的名单。这可以表示为这样一个方面：

merge = foldr merge2 [] 

Answer 3

也许更快的实现：

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 x y):(mergePairs tail)) 

mergeAll :: Ord a => [[a]] -> [a] 
mergeAll [] = [] 
mergeAll x = head $ mergePairs x 

mergeTwo刚刚合并两个列表。 mergeAll只运行mergePairs并返回头部，如果有的话。魔术发生在mergePairs中，该过程需要列表和合并对，而不是等等，而至少有两个列表。

这可能会更快，想像你正在运行

merge = foldl merge2 [] 

它需要一个长长的名单，并合并和合并。如果你在运行[1,2,3]，[4,5,6]，[7,8,9]，[10,11,12]，它结合了：

[]与[ 1,2,3]

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

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

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

但你要保持大约相同lenght的名单。所以，你要合并：

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

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

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

你也可以考虑并联机器人实现mergePairs的，也可能是在多核处理器上是有用的。但是我对这个没有经验：/

Answer 4

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 

要真正享受哈斯克尔，好好看看，并通过心脏的Prelude和Data.List学习。他们是每个Haskell程序员的面包和黄油。

Answer 5

如果您首先将列表与concat然后sort合并，则会更容易。

import Data.List(sort) 

mergeSort = sort . concat