haskell - 根据 foldr 定义 foldl

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 方面。我不跟。

为什么 foldr 有 4 个参数？

id 函数有什么作用？

最佳答案

当展开 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

IE。

(step x1 g) z

现在应用 foldl 的 where 部分:



给

(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

和上面一样。

关于haskell - 根据 foldr 定义 foldl，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53057923/