haskell - 根据 foldr 定义 foldl

Question

myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

我目前正在阅读一本关于 Haskell 的书。在其中，它编写了自己版本的 foldl 函数，但在 foldr 方面。我不跟。

1. 为什么 foldr 有 4 个参数？
2. id 函数有什么作用？

Answer 1

当扩展foldr step id xs z的表达式时，事情会变得很明显:

正如亚当斯密在评论中所说:

foldr step id xs z = (foldr step id xs) z

首先考虑foldr step id xs

foldr step id xs
= x1 `step` (foldr step id xs1)
= x1 `step` (x2 `step` (foldr step id xs2))
...
= x1 `step` (x2 `step` ... (xn `step` (foldr step id []))...)
= x1 `step` (x2 `step` ... (xn `step` id)...)

在哪里

xs = (x1:xs1)
xs1 = (x2:xs2), xs = (x1:x2:xs2) 
....
xsn = (xn:[]), xs = (x1:x2...xsn) respectively 

现在，应用带有参数 z 的上述函数，即

(x1 `step` (x2 `step` ... (xn `step` id)...)) z

让

g = (x2 `step` ... (xn `step` id)...) 

给予

(x1 `step` g) z

即

(step x1 g) z

现在应用 foldl 的 where 部分:

where step x g a = g (f a x)

给予

(step x1 g) z = step x1 g z = g (step z x1)

在哪里

g (step z x1) = (x2 `step` (x3 step ... (xn `step` id)...) (step z x1)

让

g' = (x3 step ... (xn `step` id)...)

给予

(x2 `step` g') (step z x1)
= step x2 g' (step z x1)
= g' (step (step z x1) x2))
= (x3 step ... (xn `step` id)...) (step (step z x1) x2))

重复同样的步骤，终于有了，

(xn `step` id) (step ....(step (step z x1) x2)....)
= step xn id (step ....(step (step z x1) x2)....)
= id (step (step ....(step (step z x1) x2)....) xn)
= (step (step ....(step (step z x1) x2)....) xn)
= foldl step z xs

现在，很明显为什么要使用 id 函数。最后，看看为什么

foldl step z xs = (step (step ....(step (step z x1) x2)....) xn)

初始案例:

foldl step z' [] = z'

递归情况:

foldl step z (x1:xs1) 
= foldl step (step z x1) xs1
= foldl step (step (step z x1) x2) xs2
...
= foldl step (step (step ....(step (step z x1) x2)....) xn) []
= (step (step ....(step (step z x1) x2)....) xn)

在哪里

z' = (step (step ....(step (step z x1) x2)....) xn) in initial case

同上。