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,3,4,5,6] 与 [7,8,9]

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

但是您想保留大约相同长度的列表。所以你想合并:

[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 的并行实现，它在多核处理器上可能很有用。但我没有这方面的经验:/