根据文件夹定义文件夹 [英] Defining foldl in terms of foldr

问题描述

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.我不跟随.

I am currently reading a book on Haskell. And in it, it wrote its own version of the foldl function, but in terms of foldr. I do not follow.

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

推荐答案

当扩展foldr step id xs z的表达式时，事情将变得显而易见:

The thing will be become obvious when to expand the expression of foldr step id xs z:

如亚当·斯密(Adam Smith)在评论中所说:

As Adam Smith said in the comments:

文件夹步骤ID xs z =(文件夹步骤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一起应用，即

Now, apply above function with argument z, i.e.

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

然后让

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

给予

(x1 `step` g) z

即

(step x1 g) z

现在应用foldl的where部分:

and now apply the where part of foldl:

其中步骤x g a = g(f a x)

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))

重复相同的步骤，最后我们有了

repeats the same steps, finally we have,

(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函数.最后，看看为什么

and now, it is obvious that why use id function. finally, see why

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

与上述相同.

这篇关于根据文件夹定义文件夹的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！