corecursion和codata [英] corecursion and codata
问题描述
fibs = 0:1:zipWith (+)fibs(tail fibs)
据我所知,fibs一般是lazy ,所以下一个项目将被按需计算,但是我不确定tail函数如何在无限列表中工作。
所以说明它适用于一些中间数据将有所帮助。
开始时,评估是这样的:
fibs = 0:1:zipWith(+)fibs(tail fibs)
如果我们用它的评估来替换 fibs
,它看起来像这样:
fibs = 0:1:zipWith(+)(0:1:?)(1:?)
其中?
表示未评估的thunk。让我们来评估 fibs
的下一个元素:
fibs = 0:1 :zipWith(+)(0:1:?)(1:?)==>
fibs = 0:1:1:zipWith(+)(1:?)(?)
每个 zipWith
参数列表的第一个元素被占用。现在,当我们评估它时,我们也知道,下一个thunk的价值是什么,我们可以填充它。这使我们可以评估下一个单元格,等等。
fibs = 0:1:1:zipWith(+)(1:?)(?)==>
fibs = 0:1:1:zipWith(+)(1:1:?)(1:?)==>
fibs = 0:1:1:2:zipWith(+)(1:?)(?)==>
fibs = 0:1:1:2:zipWith(+)(1:2:?)(2:?)==>
fibs = 0:1:1:2:3:zipWith(+)(2:?)(?)==>
...
Would like to get step-by-step explanation of the following function in Haskell
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
I understand that the "fibs" in general is "lazy", so next item would be calculated "on demand", however I'm not sure how the "tail" function would work on infinite list.
So the illustration of how it works with some intermediate data would help.
At the beginning, the evalution is like this:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
If we replace fibs
by its evaluation, it looks like this:
fibs = 0 : 1 : zipWith (+) (0 : 1 : ?) (1 : ?)
Where ?
denotes the unevaluated thunk. Let's evaluate the next element of fibs
:
fibs = 0 : 1 : zipWith (+) (0 : 1 : ?) (1 : ?) ==>
fibs = 0 : 1 : 1 : zipWith (+) (1 : ?) (?)
The first element of each of the argument lists of zipWith
is consumed. Now, when we evaluated it, we also know, what the value of the next thunk is and we can fill it in. That allows us to evaluate the next cell, and so on:
fibs = 0 : 1 : 1 : zipWith (+) (1 : ?) (?) ==>
fibs = 0 : 1 : 1 : zipWith (+) (1 : 1 : ?) (1 : ?) ==>
fibs = 0 : 1 : 1 : 2 : zipWith (+) (1 : ?) (?) ==>
fibs = 0 : 1 : 1 : 2 : zipWith (+) (1 : 2 : ?) (2 : ?) ==>
fibs = 0 : 1 : 1 : 2 : 3 : zipWith (+) (2 : ?) (?) ==>
...
这篇关于corecursion和codata的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!