在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

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