myReverse :: [a] -> [a]
myReverse = foldl (\a x -> x:a) []
foldl is (a -> b -> a) -> a -> [b] -> a
Die Lambda-Funktion ist offensichtlich in den Klammern. Woher erhält foldl seinen Anfangswert? Und was ist [b] in diesem Fall?Können Sie verfolgen, wie diese Haskell-Faltlambda-Funktion funktioniert?
Wir können durch die Auswertung von sagen, myReverse [1,2,3]. Wir müssen die Definition von foldl
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
wir
myReverse [1,2,3,4]
-- definition of myReverse
= foldl (\a x -> x:a) [] [1,2,3]
-- definition of foldl (x:xs case)
= foldl (\a x -> x:a) ((\a x -> x:a) [] 1) [2,3]
-- beta reduction [1]
= foldl (\a x -> x:a) [1] [2,3]
-- definition of foldl
= foldl (\a x -> x:a) ((\a x -> x:a) [1] 2) [3]
-- beta reduction
= foldl (\a x -> x:a) [2,1] [3]
-- definition of foldl
= foldl (\a x -> x:a) ((\a x -> x:a) [2,1] 3) []
-- beta reduction
= foldl (\a x -> x:a) [3,2,1] []
-- definition of foldl ([] case)
= [3,2,1]
mit dem wichtigen Vorbehalt So haben bei [1] und für jeden Beta-Reduktionsschritt, der diese Beta-Reduktion tatsächlich geschieht nur, wenn etwas das Ergebnis mustert. Als foldl voran ist, bauen die wiederholten Anwendungen von f als Thunks, also was wir bekommen wirklich (wenn f = \a x -> x:a) ist:
foldl f [] [1,2,3]
foldl f (f [] 1) [2,3]
foldl f ((f 2 (f [] 1))) [3]
foldl f (((f 3 ((f 2 (f [] 1)))))) []
(((f 3 ((f 2 (f [] 1))))))
diesem Grund haben wir foldl' haben, der in seinem Akkumulator streng ist und verhindert, dass diese Thunk aufbauen. Der erste Wert ist []. Die [b] ist in diesem Fall die gleiche wie die a in foldl, die die [a] in myReverse ist.
myReverse :: [a] -> [a]
myReverse = foldl (\a x -> x:a) []
kann äquivalent als
myReverse :: [a] -> [a]
myReverse xs = foldl (\a x -> x:a) [] xs
daher umgeschrieben werden, die Faltungsfunktion ist das Lambda \a x -> x:a, ist der Ausgangswert [], und die Liste umklappen xs.