Haskell Fibonacci Spiegazione

Sono abbastanza nuovo per Haskell e sto cercando di capire come funziona l'espressione pigra delle sequenze di Fibonacci.Haskell Fibonacci Spiegazione

So che questo è stato chiesto prima, ma nessuna delle risposte ha risolto un problema che sto riscontrando nel visualizzare il risultato.

Il codice è quella canonica utilizzando zipWith

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

ho capito quanto segue:

zipWith cerniere letteralmente due liste insieme
tail palio tutti, ma il primo elemento di una lista
I riferimenti Haskell 'to-be' dati calcolati come thunks.

Dalla mia comprensione, in primo luogo aggiunge [0,1,<thunk>] e [1,<thunk>] utilizzando zipWith (+) per dare [1,<thunk>]. Così ora avete

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

Un sacco di riferimenti Googled hanno poi proceduto a "visualizzare" la riga sopra come

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

mia domanda è questa:

Perché è lafibscomponente nella riga sopra solo corrispondente a[1,1,<thunk>]anziché[0,1,1,<thunk>]?

Non dovrebbe fibs contenere l'intero elenco più <thunk>?

fonte

2014-11-10 MikamiHero

buon modo per comprendere tali definizioni è quello di [nome dei valori intermedi] (http://stackoverflow.com/a/20978114/849891) che entrano in esistenza come abbiamo progressivamente loro l'accesso (ad esempio, in 'prendere 3 fibs'). In questo modo non c'è confusione tra lo stesso pezzo di dati a cui si accede due volte (attraverso lo stesso nome), o due pezzi di dati uguali (ognuno con il proprio nome). –

Questa fase intermedia è sbagliato perché zipWith ha già elaborato la prima coppia di elementi:

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

ricordare ciò zipWith fa nel caso generale:

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

Se si applica la definizione direttamente voi ottenere questa espansione:

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 
    :

fonte

2014-11-10 12:28:41 Joni

+1 Grazie per la spiegazione, @Joni. Penso di iniziare a capirlo adesso, ma ho ancora una domanda in più che tipo di link alla mia domanda originale. Nella quarta riga in cui hai fib = 0: 1: 1: zipWith (+) [1,1, ...] [1, ...], come mai la lista dopo zipWith (+) ha solo [1,1, ...] invece dell'intera lista? – MikamiHero

zipWith richiede un paio di elementi, applica loro una funzione e ricorre sulle * code * degli elenchi di input. Forse dovrei espandere ulteriormente – Joni

se non ti dispiacerebbe espanderci, lo apprezzerei molto ! Sono molto nuovo per Haskell e questo ha la mia testa in loop (nessun gioco di parole). – MikamiHero

come visualizzare wha Sta succedendo.

1 1 2 3 5 8 13 <----fibs 
    1 2 3 5 8 13  <----The tail of fibs 
+________________ <----zipWith (+) function 
    2 3 5 8 13 21  <----New fibs. 13 drops out --nothing to zip with 

finally, add [1, 1] to beginning 
1, 1, 2, 3, 5, 8, 13, 21

fonte

2017-01-29 02:48:26

risposta

Problemi correlati