Haskell Фибоначи Обяснение

Аз съм съвсем нов в Haskell и се опитвам да обясня как работи мързеливият израз на последователностите на Фибоначи.

Знам, че това е задавано и преди, но нито един от отговорите не адресира проблем, който имам с визуализирането на резултата.

Кодът е каноничният, използващ zipWith

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

Разбирам следното:

  1. zipWith буквално закопчава два списъка заедно
  2. tail грабва всички елементи от списъка освен първия
  3. Haskell препраща към изчислените данни „предстоящи“ като thunks.

Доколкото разбирам, първо добавя [0,1,<thunk>] и [1,<thunk>], използвайки zipWith (+), за да даде [1,<thunk>]. Така че сега имате

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

Много препратки, които съм търсил в Google, след това продължиха да „визуализират“ реда по-горе като

fibs = 0 : 1 : 1 : zipWith (+) [1,1,<thunk>] ([1,<thunk>]).

Въпросът ми е следният:

Защо компонентът fibs в горния ред съответства само на [1,1,<thunk>] вместо на [0,1,1,<thunk>]?

Не трябва ли fibs да съдържа целия списък плюс <thunk>?


functional-programming thunk lazy-evaluation haskell fibonacci
person MikamiHero    schedule 10.11.2014    source източник
comment
добър начин да разберете такива дефиниции е да именувате междинните стойности, които възникват, когато прогресивно имаме достъп до тях (напр. в take 3 fibs) . По този начин няма объркване между една и съща част от данните, достъпна два пъти (чрез едно и също име), или две равни части от данни (всеки със собствено име).   -  person Will Ness    schedule 11.11.2014
comment
ето отговор с хубави снимки, илюстриращи работата на това определение.   -  person Will Ness    schedule 03.09.2019
comment
така че сега имате грешен код. трябва да е fibs = 0 : 1 : 1 : zipWith (+) (drop 1 $ fibs) (drop 1 $ tail fibs), защото в този момент сме напреднали с една стъпка по списъка. и в това се крие отговорът на въпроса ти.   -  person Will Ness    schedule 03.09.2019

Отговори (2)


arrow_upward
13
arrow_downward

Тази междинна стъпка е грешна, защото zipWith вече е обработил първата двойка елементи:

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

Спомнете си какво прави zipWith в общия случай:

zipWith f (x:xs) (y:ys) = (f x y) : zipWith f xs ys

Ако приложите дефиницията директно, ще получите това разширение:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)                # fibs=[0,1,...]
     = 0 : 1 : zipWith (+) [0,1,...] (tail [0,1,...])      # tail fibs=[1,...]
     = 0 : 1 : zipWith (+) [0,1,...] [1,...]               # apply zipWith
     = 0 : 1 : (0+1 : zipWith (+) [1,0+1,...] [0+1,...])   
     = 0 : 1 : 1 : zipWith (+) [1,1,...] [1,...]           # apply zipWith
     = 0 : 1 : 1 : (1+1 : zipWith (+) [1,1+1,...] [1+1,...])
     = 0 : 1 : 1 : 2 : zipWith (+) [1,2,...] [2,...]       # apply zipWith
     = 0 : 1 : 1 : 2 : (1+2 : zipWith (+) [2,1+2,...] [1+2,...])
     = 0 : 1 : 1 : 2 : 3 : zipWith (+) [2,3...] [3,...]    # apply zipWith
     :
person Joni    schedule 10.11.2014
comment
+1 Благодаря ти за обяснението, @Joni. Мисля, че сега започвам да го разбирам, но все още имам още един въпрос, който е свързан с първоначалния ми въпрос. Във вашия четвърти ред, където имате fibs = 0 : 1 : 1 : zipWith(+) [1,1,...] [1,...], как така списъкът след zipWith(+) има само [1, 1,...] вместо целия списък? - person MikamiHero; 10.11.2014
comment
zipWith взема взема двойка елементи, прилага функция към тях и рекурсира към опашките на входните списъци.. може би трябва да разширя това допълнително - person Joni; 10.11.2014
comment
ако нямате нищо против да разширите това, ще съм много благодарен! Аз съм много нов в Haskell и това ме забърка в главата (без каламбур). - person MikamiHero; 10.11.2014
comment
благодаря ви много, че разяснихте отговора си. Оценявам го! За съжаление, нямам 15 репутация, така че не мога да гласувам за отговора ви :( - person MikamiHero; 10.11.2014
comment
@MikamiHero Дадох подобно обяснение преди, което може да ви даде малко по-различна гледна точка за това, за да подобрите разбирането си. Отговорът на Джони обаче е доста добър. - person bheklilr; 10.11.2014
comment
@bheklir Благодаря ти, че ме свърза. Ще го проверя :) - person MikamiHero; 10.11.2014

arrow_upward
2
arrow_downward

Как да си представим какво се случва.

  1 1 2 3  5  8 13 21 ...   <----fibs
  1 2 3 5  8 13 21 ...      <----The tail of fibs
+_________________________  <----zipWith (+) function
  2 3 5 8 13 21 34 ...

 Finally, add [1, 1] to the beginning
 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
person Nick Ziebert    schedule 29.01.2017