Haskell合并多个列表

Question

我想编写一个合并函数,它接受多个x排序列表,并通过增量值(从最小到最大)将它们合并到一个排序列表中.我想我可以做两个列表并合并为一个,但无法弄清楚多个列表的基本情况并合并为一个排序.

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

Answer 1

也许更快的实施:

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并返回head(如果有的话).魔术发生在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,8,4,5,6]与[7,8,9]

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

但是你想要保持大致相同长度的列表.所以你要合并:

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

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

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

您还可以考虑使用mergePairs的并行实现,它可能对多核处理器很有用.但我没有这方面的经验:/

Answer 2

如果您可以为两个列表定义函数,那么您可以通过简单地浏览每个子列表并将其与当前结果合并,直到您合并所有列表,将其推广到任意多个列表.这可以表示为这样的折叠:

merge = foldr merge2 []

Answer 3

@ sepp2k的答案很好,但它只适用于有限的输入列表.如果你给它无限多的列表,它将永远尝试找到最小的起始元素.

我们可以通过要求输入列表已经通过增加第一个元素进行排序来解决这个问题.然后我们知道我们可以产生"左上角"元素(第一个列表的第一个元素),因为它将是所有内容的下限,这为我们提供了足够的信息来递归使用并产生完整的合并.

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

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