Sto usando il ragionamento equazionale del suono su una definizione di filtro in termini di foldr?

Question

bene, questa è la definizione della funzione filtro utilizzando foldr:

myFilter p xs = foldr step [] xs 
    where step x ys | p x  = x : ys 
        | otherwise = ys 

così per esempio diciamo che ho questo funzione:

myFilter odd [1,2,3,4] 

quindi sarà:

foldr step [] [1,2,3,4] 

e questo sarà

step 1 (foldr step [] [2,3,4]) 

.210

e questo sarà

step 1 (step 2 (foldr step [] [3,4])) 

e questo sarà

step 1 (step 2 (step 3 (foldr step [] [4]))) 

e questo sarà

step 1 (step 2 (step 3 (step 4 (foldr step [] [])))) 

e foldr step [] [] è [] così:

step 1 (step 2 (step 3 (step 4 []))) 

ora entreremo nella funzione step.
Ecco la definizione della step all'interno della funzione myFilter, dall'alto:

step x ys | p x  = x : ys 
      | otherwise = ys 

anche, vi ricordo che p è in realtà la funzione odd nel nostro esempio.

bene, ancora una volta, siamo qui:

step 1 (step 2 (step 3 (step 4 []))) 

e

x = 4 nella zona più interna step, e 4 non è strano, così abbiamo tornando ys, che è []

così ora otteniamo questo:

step 1 (step 2 (step 3 [])) 

ora, nella più interna step, x = 3, e 3 è dispari, così torniamo x:ys, che è 3 : [], che è [3], e ora otteniamo:

step 1 (step 2 [3]) 

e ora, in quello interno step, x = 2, e 2 non è strano, così torniamo ys, che è [3], così ora noi otterrà:

step 1 [3] 

e ora, x = 1 e 1 è dispari, quindi restituiamo x : ys, che è 1 : [3], che è [1,3].

Fine :-).

ho ragione in tutte le mie mosse?
grazie mille :-).

p.s. la definizione di myFilter proviene dal libro Real World Haskell, nel capitolo 4.

Answer 1

Questo mi sembra giusto in prima lettura.

La cosa importante da ricordare è che, al fine di ottenere una valutazione lenta, Haskell guarderà effettivamente le cose dall'altra parte. In altre parole, la vera sequenza è più simile a

step 1 (step 2 (step 3 (step 4 []))) 

diventa

step 1 <block1> 

che diventa

[1, <block1>] 

allora se si tenta di tirare il successivo elemento da tale elenco, si valuterà

[1, step 2 <block2>] 

che diventa

[1, <block2>] 

e poi cercando di valutare

[1, step 3 (step 4 [])] 

si trasforma in

[1, step 3 <block3>] 

che diventa

[1, 3, <block3>] 

ecc Questo mi ha portato un po 'per capire. E 'stato controintuitivo per me che da quando foldr sembra essere valutati dal "dentro e fuori", ma foldl viene valutata dal "fuori" che foldr sarebbe pigro (che è), mentre foldl è rigorosa. Ma se ci pensi come ho descritto sopra, ha senso (per me, comunque).

Answer 2

A prima vista, i passaggi che hai seguito nel tuo esempio specifico sembrano corretti singolarmente. Tuttavia, vorrei far notare che sia filter e foldr può essere utilmente applicato a infinite liste --che dovrebbe indicare che l'ordine delle fasi non è corretta per quanto Haskell è interessato.

Answer 3

Solo per espandere l'ordine di valutazione pigro: Fondamentalmente Haskell valuta sempre la funzione di prima, senza guardare gli argomenti fino a quando non deve.

Se si utilizza il risultato della chiamata a myFilter (per esempio stampato), la funzione sarà valutata nel seguente ordine:

myFilter odd [1,2,3,4] 

Prima la funzione myFilter viene valutata:

foldr step [] [1,2,3,4] 

Ora la foldr è la funzione più esterna e viene valutata:

step 1 (foldr step [] [2,3,4]) 

Ora step viene valutato producendo un 1, dal momento che 1 è dispari:

1 : foldr step [] [2,3,4] 

Ora, il primo elemento della lista dei risultati è disponibile e può essere utilizzato dalla funzione chiamante. Se la funzione chiamante utilizza anche la seguente valutazione: elementi prosegue con la foldr:

1 : step 2 (foldr step [] [3,4]) 

La valutazione dei step ora non produce alcun elemento nuovo, dal momento che 2 è anche:

1 : foldr step [] [3,4] 

Così foldr ancora:

1 : step 3 (foldr step [] [4]) 

Ora valutare step produce 3:

1 : 3 : foldr step [] [4] 

Valutare foldr;

1 : 3 : step 4 (foldr step [] []) 

E step ancora:

1 : 3 : foldr step [] [] 

Infine foldr viene valutato come una lista vuota:

1 : 3 : []