myReverse :: [a] -> [a]
myReverse = foldl (\a x -> x:a) []
foldl is (a -> b -> a) -> a -> [b] -> a
Hàm lambda rõ ràng nằm trong dấu ngoặc vuông. Trường hợp nào foldl nhận giá trị ban đầu của nó từ đâu? Và [b] trong trường hợp này là gì?Bạn có thể theo dõi chức năng lambda Haskell foldl này hoạt động như thế nào không?
Chúng tôi có thể duyệt qua đánh giá, ví dụ: myReverse [1,2,3]. Chúng ta cần định nghĩa của foldl
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
Vì vậy, chúng tôi có
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]
với sự báo trước quan trọng [1] và cho từng bước giảm beta mà giảm beta này thực sự chỉ xảy ra khi một cái gì đó thấu kết quả. Như foldl là tiến triển, các ứng dụng lặp đi lặp lại của f xây dựng như thunks, vì vậy những gì chúng ta thực sự có được (nếu f = \a x -> x:a) là:
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))))))
Đây là lý do tại sao chúng tôi có foldl', đó là nghiêm ngặt trong ắc nó và ngăn ngừa thunk này xây dựng lên.
Giá trị ban đầu là []. [b] trong trường hợp này giống với số a trong foldl, là [a] trong myReverse.
myReverse :: [a] -> [a]
myReverse = foldl (\a x -> x:a) []
có thể được viết lại như tương đương
myReverse :: [a] -> [a]
myReverse xs = foldl (\a x -> x:a) [] xs
Do đó, chức năng gấp là lambda \a x -> x:a, giá trị khởi đầu là [], và danh sách để gấp hơn là xs.