haskell - (共)递归定义如何在 Haskell 中工作？

Question

我正在玩弄这种语言来开始学习，我对递归定义的工作原理感到困惑。

例如，让我们采用三角形数的序列(TN n = sum [1..n])

提供的解决方案是:

triangularNumbers = scanl1 (+) [1..]

到目前为止，一切都很好。

但我确实想出的解决方案是:

triangularNumbers = zipWith (+) [1..] $ 0 : triangularNumbers

这也是正确的。

现在我的问题是:这如何转化为较低级别的实现？当满足这样的递归定义时，幕后究竟会发生什么？

Answer 1

这是一个简单的递归函数，可以为您提供第 n 个三角形数:

triag 0 = 0
triag n = n + triag (n-1)

您的解决方案 triag' = zipWith (+) [1..] $ 0 : triag'更花哨的东西:它是核心的( click ， click )。不是通过将第 n 个数字减少到较小输入的值来计算第 n 个数字，而是通过在给定初始段的情况下递归指定下一个值来定义整个无限三角形数序列。

Haskell 如何处理这样的 corecursion？当它遇到您的定义时，实际上不会执行任何计算，它会延迟到需要结果进行进一步计算。当您访问列表中的特定元素时 triag' , Haskell 开始根据定义计算列表的元素，直到被访问的元素。有关更多详细信息，我找到了 this关于惰性评估的文章很有帮助。总之，惰性求值非常有用，除非您需要预测内存使用情况。

Here是一个类似的 SO 问题，对 fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 的评估进行了分步说明，斐波那契数列的核心递归定义。