Bin ich mit Ton equational Argumentation über eine Definition der Filter in Bezug auf foldr?

Question

gut, das ist die Definition der Filterfunktion foldr mit:

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

so zum Beispiel lassen Sie uns sagen, ich habe diese Funktion:

myFilter odd [1,2,3,4]

so wird es sein:

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

und dies wird

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

und dies wird

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

und dies wird

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

und dies wird

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

und foldr step [] [] ist [] so:

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

Jetzt bekommen wir tatsächlich in die step Funktion.
hier ist die Definition von step innerhalb der myFilter Funktion, von oben:

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

Auch ich Sie daran erinnern, dass p ist eigentlich die odd Funktion in unserem Beispiel.

gut, wieder, wir sind hier:

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

und

x = 4 in der innersten step und 4 ungerade ist nicht, so dass wir ys Rückkehr, die [] ist

wir dies so jetzt bekommen:

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

Jetzt, in der innersten step, x = 3 und 3 ungerade ist, so dass wir x:ys zurückkehren, was 3 : [] ist, die [3] ist, und wir bekommen:

step 1 (step 2 [3])

und jetzt, in dem inneren step, x = 2 und 2 nicht ungerade ist, so dass wir ys zurückkehren, die [3] ist, so jetzt werden wir bekommen:

step 1 [3]

und jetzt, x = 1 und 1 ungerade ist, so dass wir x : ys zurückkehren, was 1 : [3] ist, was [1,3] ist.

Das Ende: -).

bin ich recht in allen meinen Bewegungen?
Dank viel: -)

.

P. S. die Definition von myFilter ist aus dem Buch Real World Haskell , in Kapitel 4.

Answer 1

Das sieht richtig für mich auf den ersten Lese.

Das Wichtigste allerdings zu bedenken, dass, um faul Auswertung zu erreichen, wird Haskell sieht die Dinge tatsächlich in der anderen Richtung. Mit anderen Worten, ist die eigentliche Folge mehr wie

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

wird

step 1 <block1>

das wird

[1, <block1>]

dann, wenn Sie versuchen, das nächste Element aus dieser Liste zu ziehen, wird es bewerten

[1, step 2 <block2>]

das wird

[1, <block2>]

und dann zu bewerten versuchen

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

verwandelt sich in

[1, step 3 <block3>]

das wird

[1, 3, <block3>]

usw. Das dauerte eine Weile zu verstehen. Es war nicht eingängig mir, dass seit foldr scheint von „innen heraus“ bewertet wurde, sondern foldl „von außen in“, dass foldr ausgewertet wäre faul (was es ist), während foldl streng. Aber wenn Sie es so, wie ich glaube, oben dargelegt, ist es sinnvoll (für mich jedenfalls).

Answer 2

Nur auf der faulen Auswertung zu erweitern. Grundsätzlich Haskell wertet immer die Funktion zunächst nicht auf die Argumente suchen, bis es hat

Wenn das Ergebnis des Aufrufs zu myFilter verwendet wird (zB gedruckt), wird die Funktion in der folgenden Reihenfolge ausgewertet werden:

myFilter odd [1,2,3,4]

Zuerst wird die myFilter Funktion ausgewertet:

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

Jetzt foldr ist die äußerste Funktion und wird ausgewertet:

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

Jetzt wird step ausgewertet, um ein 1 Herstellung, da 1 ungerade ist:

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

Nun ist das erste Element der Ergebnisliste ist verfügbar und kann von der rufenden Funktion verwendet werden. Wenn die anrufende Funktion auch die Auswertung folgende Elemente verwendet weiter mit dem foldr:

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

Die Auswertung von step hat nun keine neue Elemente produzieren, da 2 ist auch:

1 : foldr step [] [3,4]

So foldr wieder:

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

Jetzt Auswertung step produziert 3:

1 : 3 : foldr step [] [4]

Auswertung foldr;

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

Und step einmal mehr:

1 : 3 : foldr step [] []

Schließlich foldr auswertet auf eine leere Liste:

1 : 3 : []

Answer 3

Auf den ersten Blick sind die Schritte, die Sie in Ihrem speziellen Beispiel Blick genommen haben korrigieren einzeln. Ich möchte jedoch darauf hinweisen, dass beide filter und foldr kann nutzbringend auf unendliche Listen angewendet werden. - die, dass die Reihenfolge der Schritte so weit falsch ist wie Haskell betrifft angeben sollte