Come funziona (co) la definizione ricorsiva in Haskell?

Question

Sto giocando con il linguaggio per iniziare l'apprendimento e sono perplesso oltre la mia intelligenza su come funziona una definizione ricorsiva.

Per esempio, prendiamo la sequenza dei numeri triangolari (TN n = sum [1..n])

La soluzione fornita era:

triangularNumbers = scanl1 (+) [1..] 

Fin qui, tutto bene.

Ma la soluzione sono venuto su con era:

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

che è anche corretto.

Ora la mia domanda è: come si traduce in un'implementazione di livello inferiore? Cosa succede esattamente dietro la scena quando viene soddisfatta una definizione ricorsiva?

Answer 1

Ecco una semplice funzione ricorsiva che ti dà il numero triangolare n-esimo:

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

La soluzione triag' = zipWith (+) [1..] $ 0 : triag' è qualcosa di più di fantasia: E 'corecursive (click, click). Invece di calcolare l'ennesimo numero riducendolo al valore di input più piccoli, si definisce l'intera sequenza infinita di numeri triangolari specificando ricorsivamente il valore successivo, dato un segmento iniziale.

In che modo Haskell gestisce tale corecursion? Quando incontra la tua definizione, nessun calcolo viene effettivamente eseguito, viene posticipato fino a quando i risultati sono necessari per ulteriori calcoli. Quando si accede a un particolare elemento dell'elenco triag', Haskell inizia a calcolare gli elementi dell'elenco in base alla definizione, fino all'elemento a cui si accede. Per ulteriori dettagli, ho trovato utile l'articolo this sulla valutazione lazy. In breve, la valutazione lenta è ottima, a meno che non sia necessario prevedere l'utilizzo della memoria.

Here è una domanda SO simile, con una spiegazione passo passo della valutazione di fibs = 0 : 1 : zipWith (+) fibs (tail fibs), una definizione corecisiva della sequenza di Fibonacci.