debugging - 你能追踪这个 Haskell foldl lambda 函数是如何工作的吗？

Question

myReverse :: [a] -> [a]
myReverse = foldl (\a x -> x:a) []

foldl is (a -> b -> a) -> a -> [b] -> a

lambda 函数显然在括号中。在哪里 foldl获取它的初始值？什么是 [b]在这种情况下？

Answer 1

我们可以逐步完成对 myReverse [1,2,3] 的评估。 .我们需要foldl的定义

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

所以我们有

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]

与 [1] 中的重要警告以及对于每个 Beta 减少步骤，这种 Beta 减少实际上仅在某些检查结果时才会发生。如 foldl正在进步， f的重复应用建立为 thunk，所以我们真正得到的(如果 f = \a x -> x:a )是:

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))))))

这就是为什么我们有 foldl' ，这在其累加器中很严格，可以防止这种 thunk 积累。

初始值为 [] . [b]在这种情况下与 a 相同在 foldl ，这是 [a]在 myReverse .