Sto usando un valido ragionamento equazionale su una definizione di filtro in termini di foldr?

Question

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

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

quindi per esempio diciamo che ho questa 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])

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 effettivamente nel vivo step funzione.
ecco la definizione di step dentro il myFilter funzione, dall'alto:

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

inoltre, te lo ricordo p è in realtà il odd funzione nel nostro esempio.

beh, ancora una volta, siamo qui:

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

E

x = 4 nel più interiore step, E 4 non è strano, quindi torniamo ys, che è []

quindi ora otteniamo questo:

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

ora, nel più interiore step, x = 3, E 3 è strano, quindi torniamo x:ys, che è 3 : [], che è [3], e ora otteniamo:

step 1 (step 2 [3])

e ora, nell'interno step, x = 2, E 2 non è strano, quindi torniamo ys, che è [3], quindi ora otterremo:

step 1 [3]

e adesso, x = 1, E 1 è strano, quindi torniamo x : ys, che è 1 : [3], che è [1,3].

Fine :-).

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

p.s.la definizione di myFilter è tratto dal libro Haskell del mondo reale, nel capitolo 4.

Answer 1

Questo mi sembra giusto alla prima lettura.

La cosa importante da ricordare, però, è che per ottenere una valutazione pigra, Haskell guarderà effettivamente le cose dall'altra parte.In altre parole, la sequenza reale è più simile

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

diventa

step 1 <block1>

che diventa

[1, <block1>]

quindi se provi a estrarre l'elemento successivo da quell'elenco, verrà valutato

[1, step 2 <block2>]

che diventa

[1, <block2>]

e poi provare a valutare

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

diventa

[1, step 3 <block3>]

che diventa

[1, 3, <block3>]

eccetera.Mi ci è voluto un po' per capirlo.Per me è stato controintuitivo da allora foldr sembra essere valutato "dall'interno verso l'esterno" ma foldl viene valutato dal "fuori dentro" quello foldr sarebbe pigro (e lo è), mentre foldl è severo.Ma se la pensi nel modo in cui l’ho delineata sopra, ha senso (per me, almeno).

Answer 2

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

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

myFilter odd [1,2,3,4]

In primo luogo la funzione myFilter viene valutata:

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

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

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

Ora step viene valutata la produzione di 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 valutazione elementi seguenti continua con la foldr:

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

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

1 : foldr step [] [3,4]

Quindi foldr ancora:

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

Ora valutare step produce 3:

1 : 3 : foldr step [] [4]

Valutazione foldr;

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

E step una volta di più:

1 : 3 : foldr step [] []

a valutare Infine foldr ad una lista vuota:

1 : 3 : []

Answer 3

A prima vista, i passi che hai preso nel tuo esempio specifico aspetto correggere singolarmente. Tuttavia, vorrei far notare che sia filter e foldr possono essere utilmente applicate a infinite liste -. Che dovrebbe indicare che l'ordine dei tuoi passi non è corretta per quanto Haskell concerne