Jak działa (co) definicja rekursywna w Haskell?

Question

Używam języka, aby rozpocząć naukę i jestem zdziwiony ponad moje rozumienie tego, jak działa definicja rekursywna.

Na przykład, weźmy kolejność Liczba trójkątna (TN n = sum [1..n])

Rozwiązanie dostarczone brzmiała:

triangularNumbers = scanl1 (+) [1..] 

Tak daleko, tak dobrze.

Ale rozwiązanie I nie było wymyślić:

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

który jest również poprawna.

Teraz moje pytanie brzmi: w jaki sposób przekłada się to na implementację na niższym poziomie? Co dzieje się dokładnie za sceną, gdy taka rekurencyjna definicja zostanie spełniona?

Answer 1

Oto prosty rekurencyjna funkcja, która daje ntą Liczba trójkątna:

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

Twoje rozwiązanie triag' = zipWith (+) [1..] $ 0 : triag' jest coś bardziej wyszukane: To corecursive (click, click). Zamiast obliczać n-tą liczbę, redukując ją do wartości mniejszych danych wejściowych, definiujesz całą nieskończoną sekwencję liczb trójkątnych, rekursywnie określając następną wartość, biorąc pod uwagę początkowy segment.

W jaki sposób Haskell obsługuje takie operacje rdzenia? Gdy napotyka twoją definicję, żadne obliczenia nie są wykonywane, jest odroczona, aż wyniki będą potrzebne do dalszych obliczeń. Po uzyskaniu dostępu do określonego elementu z listy, Haskell rozpoczyna obliczanie elementów listy w oparciu o definicję, aż do elementu, do którego uzyskiwany jest dostęp. Aby uzyskać więcej szczegółów, znalazłem pomocny artykuł na temat leniwego oceniania this. Podsumowując, leniwka ocena jest świetna, chyba że musisz przewidzieć użycie pamięci.

Here jest podobnym pytaniem SO, z wyjaśnieniem krok po kroku oceny fibs = 0 : 1 : zipWith (+) fibs (tail fibs), definicją corecursive sekwencji Fibonacciego.