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

对于一个任务，我需要编写一些Haskell代码，其中有一个由无限的整数列表组成的有限列表，每个列表单调递增。如何在Haskell中合并有限数量的无限列表？

现在，我需要将这些合并到一个列表中，以整数排序。另外，有些整数可能出现在多个列表中：在输出列表中，每个整数只能在列表中出现一次。因此，如果输入是例如[[1,2,6,10,28,40，...] [3,4,10,28,100，...]，[任意数量的列表]]那么输出应该是[1,2,3,4,6,10,28,40,100，...]

我有点卡在这里。我不知道如何有效地使用foldr来合并列表。我想我应该比较每个列表的头部，并从那个列表中创建一个新列表。

来源

2014-10-01 surfer1311

排序无限列表通常不是很容易。如果我有输入'[[1,3,4,5,6，...]，[1,3,5,7，...]]，我开始排序他们得到'[1，3 ，4，5，6，7，...]，我怎么知道2在这两个输入列表中没有出现？ – bheklilr 2014-10-01 20:29:11

这是不可能的，除非你知道列表单调增加，我猜测是在作业中说明的。你能确认并告诉我们你曾尝试过什么吗？这里的人通常更有帮助，如果你不只是说“告诉我如何”。 – 2014-10-01 20:30:05

我怀疑样本数据中的每个输入列表已经排序，并且合并是所有必需的。 – AndrewC 2014-10-01 20:30:44

您可以通过考虑合并两个无限排序列表来简化问题，然后试图推广。该合并的骨架会是这个样子：

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 ???

来源

2014-10-01 22:12:20 amalloy

我会咬，我看不出你如何与foldr相似解析'[[1]，[7]，[3]，[2]' – mhitza 2014-10-01 23:31:05

@mhitza（**注到OP合并* *，你可能会认为这是一个**扰流器**）：简单。 'mergeAll = foldr mergeSorted []; mergeAll [[1]，[7]，[3]，[2]]'然后按照预期评估为[[1,2,3,7]]。 – amalloy 2014-10-01 23:33:55

哇，我觉得自己像个白痴，想象别的东西:) – mhitza 2014-10-01 23:39:55

我们可以通过反复牵拉最小元件从名单中任一个，通过unfoldr pull（unfoldr是Data.List），与

合并任何对无限单调递增的列表（如您有）

pull (x:xs,y:ys) | x<y = Just (x, (xs,y:ys)) 
       | x>y = Just (y, (x:xs,ys)) 
       | x==y = Just (x, (xs, ys)) -- pull same from both (NB!)

，我们可以处理由对任何有限列表，其减半长度：

pairs f (x:y:t) = f (x,y) : pairs f t 
pairs _ t  = t

要重复，直到条件被满足的步骤，是until工作：

uniquelyMerge xs = ... (until (...) (pairs (unfoldr pull)) xs) 
.....

不要忘了处理空列表情况。

来源

2014-10-02 16:39:04

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

回答

相关问题