È questo un modo corretto di scrivere la funzione di foldr Haskell?

Question

stavo facendo gli esercizi da sezione di yaht ricorsivo Tipo di dati , e ha trovato la scrittura della funzione un po 'impegnativo (soprattutto perché non ho capito davvero la differenza tra listFoldr e foldl in un primo momento) foldr. Quando ho finalmente capito esattamente come la funzione listFoldl ha funzionato, ho deciso che un semplice scambio di argomenti di funzione sarebbe tutto che sarebbe necessario per cambiare il mio <=> funzione per una funzione <=>:

listFoldl f i [] = i
listFoldl f i (x:xs) = listFoldl f (f i x) xs

listFoldr f i [] = i
listFoldr f i (x:xs) = listFoldr f (f x i) xs

Questo sembra funzionare (ho fatto più prove di questo):

Main> foldr (-) 4 [1, 2, 3]
-2
Main> listFoldr (-) 4 [1, 2, 3]
-2

Ma le href="http://en.wikibooks.org/wiki/Haskell/YAHT/Type_basics/Solutions#Recursive_Datatypes" dato per l'esercizio è molto più diversa dalla mia. La loro <=> è esattamente uguale al mio, ma guardare il loro <=>:

listFoldr f i [] = i
listFoldr f i (x:xs) = f x (listFoldr f i xs)

Quale soluzione è meglio, mia o la loro? È uno di loro non corretta? (Nel mio test, entrambi finiscono con lo stesso identico risultato ...)

Answer 1

Credo che si stanno elaborando gli elementi nel 'ordine inverso', e così la tua non è giusto.

Si dovrebbe essere in grado di dimostrare con un esempio in cui 'ordine è importante'. Ad esempio, qualcosa come

listfoldr f "" ["a", "b", "c"]

dove 'f' è una funzione lungo le linee di

f s1 s2 = "now processing f(" @ s1 @ "," @ s2 @ ")\n"

dove '@' è un operatore di stringa-append (ho dimenticato che cosa è in Haskell). Il punto è solo quello di 'strumento' la funzione in modo da poter vedere quale ordine è sempre chiamato con i vari argomenti.

(Si noti che questo non si è presentata nel tuo esempio, perché la matematica "4-1-2-3" dà la stessa risposta "4-3-2-1".)

Answer 2

La vostra soluzione è sicuramente corretto. Hai semplicemente implementato un foldl in cui la funzione f prende argomenti in ordine inverso. Ad esempio di ciò che è sbagliato, foldr (:) [] si suppone sia una funzione di identificare sulle liste, ma la funzione inverte la lista. Ci sono un sacco di altri motivi per cui la funzione non è foldr, come come 3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4)) funziona su liste infinite e il vostro non lo fa. Si tratta di una pura coincidenza che loro sono gli stessi nel tuo esempio, perché <=>. Penso che si dovrebbe iniziare da zero e guardare come <=> dovrebbe funzionare.

Answer 3

Il tuo è rotto. Da provare con qualcosa che non finisce con un unico risultato numerico.

eg: listFoldr (++) "a" ["b", "c", "d"]

Stai elaborazione nella direzione sbagliata.

Answer 4

In un elenco [x1, x2, ..., xk], i tuoi listFoldr calcola

 f xk (... (f x2 (f x1 i)) ...)

mentre foldr dovrebbe calcolare

 f x1 (f x2 (... (f xk i) ...))

(In confronto, foldl calcola

f (... (f (f i x1) x2) ...) xk

In sostanza, listFoldr f = foldl (flip f)).

Sei test case è un peccato, perché

3 - (2 - (1 - 4)) = 1 - (2  - (3 - 4))

Quando si funzioni come questi testando, accertati di passare in un f che è non-commutativo e non associativo (cioè, l'argomento e ordine di applicazione materia), in modo da poter essere sicuro l'espressione viene valutata correttamente. Naturalmente, la sottrazione non è commutativa e non associativa e ha ottenuto appena sfortunati.