在无限列表列表上使用foldr

Question

我试图在Haskell中编写一个函数，它可以做以下操作：输入一个整数列表，对于这些整数，使用map，有一个函数应用于它们，返回一个无限的整数列表。然后，我想使用union将foldr应用于列表，这样结果将是列表中这些列表的union。

现在的问题是，当我以10‘函数’[1,2]为例进行计算时，它会首先计算1的无限列表，因为它是一个无限列表，它永远不会对2进行计算。因此，它只返回输入列表中第一个元素的无限列表中的前10个元素，并应用union，这是同一个列表。

我的问题是：有没有一种方法可以同时为输入列表中的所有元素创建无限列表，这样当我以10个“函数”[1,2]为例时，它将返回无限列表中1和2并集的前10个元素。（我不知道输入列表中的元素数）

这是我的代码，让它更清楚：

pow :: Integer -> [Integer]
pow n = map (^n) [1, 2..]

function :: [Integer] -> [Integer]
function xs = foldr union [] (map pow xs)

Answer 1

如果您想要对输入和输出列表进行排序，请检查data-ordlist。如果您只想要所有的元素，但不关心顺序，请尝试concat。转置。

Answer 2

Union函数适用于任意列表并删除重复项，因此它必须首先完全评估其中一个参数，然后才能继续处理另一个参数。

我认为您希望明确引入列表已排序的假设，然后您可以编写一个高效的函数来合并（就像合并排序中的合并一样）输入列表并计算联合，而不需要在另一个列表之前评估其中一个列表。

我不知道库中是否存在这样的合并函数，但您可以很容易地自己定义它：

-- | Computes the union of two sorted lists
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x <= y    = x : merge (dropWhile (== x) xs) (dropWhile (== x) (y:ys))
  | otherwise = y : merge (x:xs) (dropWhile (== y) ys)

然后，您的原始折叠与这个新的合并函数应该表现为所需的：

ghci> pow n = map (^n) [1..]
ghci> function xs = foldr merge [] (map pow xs)
ghci> take 10 (function [2,3])
[1,4,8,9,16,25,27,36,49,64]