list - 如何在 Haskell 中合并有限数量的无限列表？

Question

对于分配，我需要编写一些 Haskell 代码，该代码具有一个由无限整数列表组成的有限列表作为输入，每个列表单调递增。

现在，我需要将它们合并到一个对整数进行排序的列表中。此外，一些整数可能出现在多个列表中:在输出列表中，每个整数可能只在列表中出现一次。

因此，如果输入例如 [ [1, 2, 6, 10, 28, 40, ...] [3, 4, 10, 28, 100, ...] , [any number of lists] ] 那么输出应该是 [1, 2, 3, 4, 6, 10, 28, 40, 100, ...]

我有点卡在这里。不知道怎么用foldr有效地合并列表。我认为我应该比较每个列表的标题，并从中制作一个新列表。

Answer 1

您可以通过考虑合并两个无限排序列表来稍微简化问题，然后尝试泛化。该合并的骨架将如下所示:

mergeSorted :: Ord a => [a] -> [a] -> [a]
mergeSorted [] ys = ys
mergeSorted xs [] = xs
mergeSorted (x:xs) (y:ys) = ???

您必须比较 x 和 y，并做一些明智的事情，可能涉及对 mergeSorted 的递归调用:这看起来还不错，对吧？

现在，让我们想象一下 mergeSorted 可以工作，您可以将两个无限排序的列表变成一个无限排序的列表。如何将 N 个无限排序列表转换为单个排序列表？为什么，这是一个简单的折叠!只需将两个列表合并在一起，然后将第三个与那个合并，第四个与那个合并，依此类推。

mergeAll :: Ord a => [[a]] -> [a]
mergeAll xss = foldr ???