用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函数是做什么用的？

- Bear Bile Farms is Torture

---

这对我来说很难理解，但长话短说，foldr 没有 4 个参数。这是 (foldr step id xs) $ z，其中 foldr 构建了一系列函数相互应用的链。 - Adam Smith

没问题，这是 Haskell。一个接收4个参数的函数和返回一个接收1个参数的函数的3个参数函数没有区别。 - Carl

id函数是foldr的初始情况，也就是说，当xs为[]时，给我一个id函数。 - assembly.jc

将以下与编程有关的内容从英语翻译成中文。仅返回翻译后的文本：相同问题：https://dev59.com/8m025IYBdhLWcg3wLilX - peeyush singh

可能是使用foldr编写foldl的重复问题。 - Jorge Adriano Branco Aires

Answer 1

当展开表达式foldr step id xs z时，事情将变得明显起来:

如Adam Smith在评论中所说：

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

where

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

即（i.e.）

(step x1 g) z

现在应用foldl的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

和上面的一样。

- assembly.jc

Answer 2

正如亚当·斯密在评论中所说，foldr只有三个参数。问题所在的这一行被解析为：

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

当然还有其他隐式的括号，但这些是重要的。

这是一个带有类型注释的重写，假设有作用域的类型变量（即在此定义中，a和b表示相同的类型）。

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs =  goFold z
   where
      goFold :: a -> a
      goFold = foldr step id xs
      step :: b -> (a -> a) -> (a -> a)  -- Last brackets are redundant
      step x g a = g (f a x)

我已经将foldr的调用移入一个单独的值goFold中，这样您就可以看到它的类型以及如何应用于z值。 step函数将b值累积为类型为(a -> a)的函数。每个由goFold处理的b值都会增加一个额外的函数。函数的“零”当然是来自Prelude的id：

id :: a -> a
id x = x

在类型中，-> 函数运算符是右结合的，因此 step 类型中的最后一对括号是多余的。但我之所以这样写是因为它突出了 step 的使用方式；它接受一个值和一个函数，并返回一个新函数。

- Paul Johnson