为什么我的 Haskell 函数不支持无限列表？

Question

我不明白为什么我在教程练习中实现这个函数失败了。运行时失败take 4 (chunks 3 [0..])。请告诉我要改变什么。

我没有做任何我认为会导致评估无限列表的事情：

• 无长度函数
• 列表中没有需要计算的模式匹配
• 无尾部功能
• 没有右侧计算

--   chunks 2 [1,2,3,4] ==> [[1,2],[2,3],[3,4]]
--   take 4 (chunks 3 [0..]) ==> [[0,1,2],[1,2,3],[2,3,4],[3,4,5]]

chunks :: Int -> [a] -> [[a]]
chunks len input = chunks' len input []

chunks' :: Int -> [a] -> [[a]] -> [[a]]
chunks' _ [] output = output
chunks' len input@(input1:inputTail) output
    | lengthAtLeast len input = chunks' len inputTail (output++[take len input])
    | otherwise               = output
    where 
        lengthAtLeast len list = length (take len list) >= len

Answer 1

这是一个问题：

chunks' len input@(input1:inputTail) output
    | lengthAtLeast len input = chunks' len inputTail (output++[take len input])

请注意，对于无限列表，该条件lengthAtLeast ...始终为真。因此，我们总是遇到这种情况——它会递归而不产生任何输出部分。仅当我们遇到其他情况时才会返回输出，但这种情况永远不会发生。

相反，请确保在递归之前生成结果：

chunks' len input@(input1:inputTail) output
    | lengthAtLeast len input = take len input : chunks' len inputTail output

当然，这样修改后output永远是空列表，我们可以去掉这个参数，进一步简化代码。

经验法则是：在处理无限列表时，尾递归将导致无限循环。您希望在递归之前生成至少部分结果。一般来说，当你的输出是一个像列表这样的大型数据结构时，尾递归是错误的方法，它应该逐渐生成，这样我们就可以从懒惰中受益。