您能否跟踪此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的重复应用程序堆积为Thunks，因此我们真正得到的（如果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'，它在其蓄能器中严格并防止这种堆积。

初始值是[]。在这种情况下，[b]与foldl中的a相同，即myReverse中的[a]。

Answer 2

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

可以等效地重写为

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

因此，折叠功能是lambda a x -> x:a，起始值是 []，折叠的列表为 xs。