使用foldr书写foldl？
使用foldr书写foldl？
提问于 2018-05-07 01:47:24
用foldr写下foldl：
-- file: ch04/Fold.hs
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)
上面的代码让我很困惑。
myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL
where stepR lastL accR accInitL = accR (stepL accInitL lastL)
有人通过提供一个例子，并逐步显示潜在的机制：
myFoldl (+) 0 [1, 2, 3]
= (foldR step id [1, 2, 3]) 0
= (step 1 (step 2 (step 3 id))) 0
= (step 1 (step 2 (\a3 -> id ((+) a3 3)))) 0
= (step 1 (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2))) 0
= (\a1 -> (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (\a3 -> (+) a3 3) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (+) ((+) a2 2) 3) ((+) a1 1)) 0
= (\a1 -> (+) ((+) ((+) a1 1) 2) 3) 0
= (+) ((+) ((+) 0 1) 2) 3
= ((0 + 1) + 2) + 3
但我仍然不能完全理解，这是我的问题：
- 什么是id功能？什么是角色？我们为什么需要这里？
- 在上面的例子中，id函数是lambda函数中的累加器吗？
- foldr的原型是foldr ::（a→b→b→b→a→b），第一个参数是需要两个参数的函数，但myFoldl实现中的step函数使用3个参数。
有没有人可以帮助我？
Stack Overflow用户
发布于 2018-05-07 11:11:06
考虑以下类型foldr：
foldr :: (b -> a -> a) -> a -> [b] -> a
而类型step是类似的b -> (a -> a) -> a -> a。由于步骤已经过去了foldr，我们可以得出结论，在这种情况下，fold的类型就像(b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a)。
不要被a不同签名的不同含义混淆; 它只是一个类型变量。另外，请记住，函数箭头是正确的关联，所以a -> b -> c与a -> (b -> c)相同。
所以，是的，累加器的值foldr是类型的函数，a -> a初始值是id。这是有道理的，因为它id是一个不起任何作用的函数 ，当添加列表中的所有值时，你将以零作为初始值开始的原因是相同的。
至于step接受三个参数，请尝试像这样重写它：
step :: b -> (a -> a) -> (a -> a)
step x g = \a -> g (f a x)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/-100003331
复制相关文章
相似问题
腾讯云开发者
