myReverse :: [a] -> [a]
myReverse = foldl (\a x -> x:a) []
foldl is (a -> b -> a) -> a -> [b] -> a
lambda函数显然在括号中。 foldl
从哪里获得初始值?在这种情况下,[b]
是什么?
我们可以逐步评估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]的重要警告和每个β减少步骤中,这种β减少实际上只有在仔细检查结果时才会发生。随着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
中的myReverse :: [a] -> [a]
myReverse = foldl (\a x -> x:a) []
。
myReverse :: [a] -> [a]
myReverse xs = foldl (\a x -> x:a) [] xs
可以等同地重写为
\a x -> x:a
因此,折叠函数是lambda []
,起始值是xs
,折叠的列表是qazxswpoi。