(co)递归定义如何在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'更有趣:它是corecursive(点击,点击).给定初始段,通过递归地指定下一个值来定义整个无限三角数序列,而不是通过将第n个数减少到较小输入的值来计算第n个数.

Haskell如何处理这样的核心运行？当它遇到您的定义时,实际上没有执行任何计算,它将被推迟到需要进一步计算的结果.当您访问列表中的特定元素时triag',Haskell会根据定义开始计算列表的元素,直到访问的元素为止.欲了解更多的细节,我发现这个文章对懒惰的评价有帮助.总之,除非您需要预测内存使用情况,否则延迟评估很有用.

这是一个类似的SO问题,逐步解释fibs = 0 : 1 : zipWith (+) fibs (tail fibs)了Fibonacci序列的一个核心定义的评估.