haskell - 在 Haskell 中合并有限排序列表

Question

我是 Haskell 的新手。我想知道如何在 Haskell 中编写一个接受有限排序的整数列表并将它们合并（排序）的函数。任何代码表示赞赏！

Answer 1

如果您的目标只是合并两个列表，这并不复杂

merge :: Ord a => [a] -> [a] -> [a]

这表示merge需要两个列表并为具有已定义排序关系的任何类型生成一个列表

merge [] x = x
merge x [] = x

这表示如果你将空列表与任何东西合并，你就会得到任何东西

merge (x:xs) (y:ys) | y < x     = y : merge (x:xs) ys
merge (x:xs) (y:ys) | otherwise = x : merge xs (y:ys)

这表示if当您合并两个列表时，第二个列表的第一个元素较低，应该放在新列表的前面，否则您应该使用第一个列表的第一个元素。

编辑：请注意，与其他一些解决方案不同，上面的合并既稳定O(n)又稳定。如果您不知道这意味着什么，请查阅维基百科。

如果您的目标是合并列表列表，您通常希望通过一次合并两个列表来做到这一点

mergePairs :: Ord a => [[a]] -> [[a]]
mergePairs [] = []
mergePairs [ls] = [ls]
mergePairs (x:y:ls) = (merge x y):mergePairs ls

merges :: Ord a => [[a]] -> [a]
merges [] = []
merges [x] = x
merges ls = merges $ mergePairs ls

可以证明，如果所有初始列表的长度相同，则这是渐近最优的（O(m n log n)其中m是排序列表的长度，是排序列表n的数量）。

这可以导致渐近有效的合并排序

mergeSort :: Ord a => [a] -> [a]
mergeSort ls = merges $ map (\x -> [x]) ls

Answer 2

这应该这样做，而不要求列表是有限的：

merge :: Ord a => [a] -> [a] -> [a]
merge (x:xs) (y:ys) = if x < y
                        then x:(merge xs (y:ys))
                        else y:(merge (x:xs) ys)
merge [] xs = xs
merge xs [] = xs

在英语中，检查每个列表的第一个元素，并将较小的元素作为下一个元素，然后合并剩余的列表。

Answer 3

(sort . concat) [[30..32],[1..3]] == [1,2,3,30,31,32]