myReverse :: [a] -> [a]
myReverse = foldl (\a x -> x:a) []
foldl is (a -> b -> a) -> a -> [b] -> a
Funkcja lambda jest oczywiście w nawiasach. Skąd foldl otrzymuje wartość początkową? A co w tym przypadku jest [b]?Czy możesz prześledzić, jak działa ta składana funkcja lambda Haskella?
Możemy przejść przez ocenę, powiedzmy, myReverse [1,2,3]. Musimy definicję foldl
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
Więc mamy
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]
z ważnym ostrzeżeniem w [1] i dla każdego etapu redukcji beta że redukcja ta beta rzeczywiście dzieje się tylko wtedy, gdy coś bada wynik. Jak foldl postępuje, że powtarzane zastosowania f budować jak łącznikami, więc to, co naprawdę się (jeśli f = \a x -> x:a) wynosi:
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))))))
To dlatego mamy foldl', który jest surowy w akumulatorze i zapobiega to thunk build-up.
Początkowa wartość to []. Numer [b] w tym przypadku jest taki sam, jak a w foldl, który jest [a] w myReverse.
myReverse :: [a] -> [a]
myReverse = foldl (\a x -> x:a) []
można równoważnie zapisać jako
myReverse :: [a] -> [a]
myReverse xs = foldl (\a x -> x:a) [] xs
Stąd funkcja folding lambda \a x -> x:a wartość początkowa jest [], a lista zaginanie jest xs.