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 步骤 id xs z = (foldr 步骤 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 部分：

其中步骤 xga = g（传真）

给

(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

和上面一样。

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)。处理的每个b值都会goFold添加一个额外的值。函数的“零”当然id来自 Prelude：

id :: a -> a
id x = x

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