corecursion и codata

Question

Хотел бы получить пошаговое объяснение следующей функции в Haskell

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Я понимаю, что "fibs" вообще "ленивый", поэтому следующий элемент будет рассчитываться "по требованию", однако я не уверен, как функция "tail" будет работать с бесконечным списком.

Так что поможет иллюстрация того, как это работает с некоторыми промежуточными данными.

Answer 1

В начале оценка выглядит так:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Если мы заменим fibs по своей оценке это выглядит так:

fibs = 0 : 1 : zipWith (+) (0 : 1 : ?) (1 : ?)

куда ? обозначает недооцененный гром. Давайте оценим следующий элемент fibs:

fibs = 0 : 1 : zipWith (+) (0 : 1 : ?) (1 : ?) ==>
fibs = 0 : 1 : 1 : zipWith (+) (1 : ?) (?)

Первый элемент каждого из списков аргументов zipWith потребляется. Теперь, когда мы оценили его, мы также знаем, каково значение следующего блока и можем его заполнить. Это позволяет нам оценить следующую ячейку и так далее:

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 : ?) (?) ==>
...

Answer 2

Начиная с задней части:

• tail возвращает содержимое списка без заголовка, например tail [1,2,3] -> [2,3]
• zipWith применяет функцию попарно к содержимому двух списков, например zipWith (+) [1,2] [10,20] -> [11,22]
• fibs определяется как список, который начинается с 0 и 1, а затем результат zipWith операция

Вот схема, которая объясняет, что происходит в zipWith

       v-searching the third value of fibs
fibs: [0,1,...]
tail: [1,.....]
--------------
sum:  [1,.....]

now fibs is sum together with the leading 0 and 1:

         v-searching the fourth value of fibs
fibs: [0,1,1,.....]
tail: [1,1,.......]
-------------------
sum:  [1,2,.......] 

now fibs is sum together with the leading 0 and 1:

           v-searching the fifth value of fibs
fibs: [0,1,1,2,.....] 
tail: [1,1,2,.......] 
----------------------
sum:  [1,2,3,.......] 

now fibs is sum together with the leading 0 and 1:

             v-searching the sixth value of fibs
fibs: [0,1,1,2,3,.....] 
tail: [1,1,2,3,.......] 
------------------------
sum:  [1,2,3,5,.......]

Таким образом, вы можете видеть, что вы можете получить весь список, если будете действовать "шаг за шагом", что возможно из-за ленивого поведения Хаскелла.

Answer 3

tail В бесконечном списке это очень просто: сгенерируйте первый аргумент, если необходимо, затем выбросьте его.

Так

fibs       =  0 : 1 : fibs'
tail fibs  =      1 : fibs'

а также

tail fibs         =  1 : 1 : fibs''
tail (tail fibs)  =      1 : fibs''

а также

tail (tail fibs)         =  1 : 2 : fibs'''
tail (tail (tail fibs))  =      2 : fibs'''

и т.п.