使用 foldr 编写 foldl [英] Writing foldl using foldr

问题描述

在 真实世界 Haskell 中，第 4 章.函数式编程:

用foldr写foldl:

-- 文件:ch04/Fold.hsmyFoldl :: (a -> b -> a) ->->[b] ->一个myFoldl f z xs = foldr step id xs z其中步骤 x g a = g (f a x)

上面的代码让我很困惑，有个叫dps的人用有意义的名字重写了它，让它更清晰一点:

myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL其中 stepR lastL accR accInitL = accR (stepL accInitL lastL)

其他人 Jef G 通过提供示例并逐步展示底层机制做得非常出色:

myFoldl (+) 0 [1, 2, 3]= (foldR 步骤 id [1, 2, 3]) 0= (步骤 1 (步骤 2 (步骤 3 id))) 0= (步骤 1 (步骤 2 (a3 -> id ((+) a3 3)))) 0= (步骤 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

但我仍然不能完全理解，这里是我的问题:

1. id 函数有什么用?有什么作用?为什么我们需要它?
2. 在上面的例子中，id 函数是 lambda 函数中的累加器?
3. foldr 的原型是 foldr :: (a -> b -> b) ->b->[a] ->b，第一个参数是一个需要两个参数的函数，但是myFoldl实现中的step函数使用了3个参数，我完全糊涂了！

解决方案

一些说明是有条理的！

id 函数有什么用?有什么作用?为什么我们需要它?

id 是身份函数，id x = x，并在使用 构建函数链时用作零的等价物函数组合，(.).你可以找到它在前奏.

在上面的例子中，id函数是lambda函数中的累加器?

累加器是通过重复函数应用构建的函数.没有明确的 lambda，因为我们将累加器命名为 step.如果需要，您可以使用 lambda 编写它:

foldl f a bs = foldr ( g x -> g (f x b)) id bs a

或者如Graham Hutton 会写:

<块引用>

5.1 foldl 操作符

现在让我们从 suml 示例中进行概括，并考虑使用函数 foldl 按从左到右的顺序处理列表元素的标准运算符 f 组合值，一个值 v 作为起始值:

foldl :: (β → α → β) → β → ([α] → β)foldl f v [ ] = vfoldl f v (x : xs) = foldl f (f v x) xs

使用这个运算符，suml 可以简单地由suml = foldl (+) 0 重新定义.许多其他函数可以使用 foldl 以简单的方式定义.例如，标准函数 reverse 可以使用 foldl 重新定义如下:

反向:: [α] → [α]反向 = foldl (λxs x → x : xs) [ ]

这个定义比我们使用 fold 的原始定义更有效，因为它避免了对列表使用低效的附加运算符 (++).

对上一节中函数 suml 的简单计算，展示了如何根据 fold 重新定义函数 foldl:

foldl f v xs = fold (λx g → (λa → g (f a x))) id xs v

相比之下，根据 foldl 重新定义 fold 是不可能的，因为foldl 在其列表参数的尾部是严格的，但 fold 不是.有许多关于 fold 和 foldl 的有用对偶定理"，以及一些用于决定哪个运算符最适合特定应用程序的指南(Bird，1998 年).

foldr 的原型是 foldr :: (a -> b -> b) -> b -> [a] -> b

Haskell 程序员会说 foldr 的 type 是 (a -> b -> b) ->b->[a] ->b.

而且第一个参数是一个需要两个参数的函数，但是myFoldl的实现中的step函数使用了3个参数，我完全糊涂了

这是令人困惑和神奇的！我们玩了个小把戏，用一个函数替换了累加器，然后将其应用于初始值以产生结果.

Graham Hutton 在上面的文章中解释了将 foldl 转换为 foldr 的技巧.我们首先写下 foldl 的递归定义:

foldl :: (a -> b -> a) ->->[b] ->一个foldl f v [] = vfoldl f v (x : xs) = foldl f (f v x) xs

然后通过 f 上的静态参数转换重构它:

foldl :: (a -> b -> a) ->->[b] ->一个foldl f v xs = g xs v在哪里g [] v = vg (x:xs) v = g xs (f v x)

现在让我们重写 g 以使 v 向内浮动:

foldl f v xs = g xs v在哪里g [] = v ->vg (x:xs) = v ->g xs (f v x)

这与将 g 视为一个参数的函数一样，返回一个函数:

foldl f v xs = g xs v在哪里g [] = idg (x:xs) = v ->g xs (f v x)

现在我们有了g，一个递归遍历列表的函数，应用一些函数f.最终值是恒等函数，每一步也产生一个函数.

但是，我们已经有一个非常相似的列表递归函数，foldr！

<块引用>

2 折叠运算符

fold 运算符起源于递归理论 (Kleene, 1952)，而使用fold 作为编程语言中的一个中心概念可以追溯到 APL 的归约算子(Iverson，1962)，然后是 FP 的插入算子(Backus，1978).在 Haskell 中，列表的 fold 运算符可以定义如下:

fold :: (α → β → β) → β → ([α] → β)折叠 f v [ ] = v折叠 f v (x : xs) = f x (折叠 f v xs)

也就是说，给定一个 α → β → β 类型的函数 f 和一个 β 类型的值 v代码>，函数fold f v 处理一个 [α] 类型的列表，通过替换 nil 给出一个 β 类型的值构造函数 [] 在列表的末尾由值 v 和每个 cons 构造函数 (:) 在列表中由函数 >f.通过这种方式，fold 运算符封装了一个简单的递归处理列表模式，其中列表的两个构造函数简单地替换为其他值和函数.列表中许多熟悉的函数都使用 fold 进行了简单的定义.

这看起来与我们的 g 函数非常相似.现在的诀窍是:使用手头所有可用的魔法(又名 Bird、Meertens 和 Malcolm)，我们应用一个特殊规则，折叠的通用属性，它是函数的两个定义之间的等价g 处理列表，表示为:

<块引用>

g [] = vg (x:xs) = f x (g xs)

当且仅当

g = 折叠 f v

因此，折叠的通用属性指出:

 g = foldr k v

其中 g 必须等价于两个等式，对于某些 k 和 v:

 g [] = vg (x:xs) = k x (g xs)

从我们早期的 foldl 设计中，我们知道 v == id.对于第二个方程，我们需要计算k的定义:

 g (x:xs) = k x (g xs)<=>g (x:xs) v = k x (g xs) v -- 函数的累加器<=>g xs (f v x) = k x (g xs) v -- foldl 的定义<= g' (f v x) = k x g' v -- 将 (g xs) 推广到 g'<=>k = x g' ->(a -> g' (f v x)) -- 展开 k.在 g' 中捕获的递归

其中，替换我们对 k 和 v 的计算定义产生一个foldl 的定义为:

foldl :: (a -> b -> a) ->->[b] ->一个折叠 f v xs =文件夹(x g -> (a -> g (f v x)))IDxsv

递归的 g 被 foldr 组合子替换，并且累加器变成了一个函数，通过在列表的每个元素上的 f 组合链构建，反过来顺序(所以我们向左折叠而不是向右折叠).

这绝对有点高级，所以要深入理解这种转换，折叠的普遍属性，使转换成为可能，我推荐 Hutton 的教程，链接如下.

<小时>

参考资料

• Haskell Wiki:Foldl 作为文件夹
• 关于折叠的普遍性和表现力的教程，格雷厄姆Hutton, J. 函数式编程 9 (4):355–372，1999 年 7 月.
• Malcolm, G. 代数数据类型和程序转换.，博士论文，格罗宁根大学.

In Real World Haskell, Chapter 4. on Functional Programming:

Write foldl with foldr:

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

The above code confused me a lot, and somebody called dps rewrote it with a meaningful name to make it a bit clearer:

myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL
where stepR lastL accR accInitL = accR (stepL accInitL lastL)

Somebody else, Jef G, then did an excellent job by providing an example and showing the underlying mechanism step by step:

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

But I still cannot fully understand that, here are my questions:

1. What is the id function for? What is the role of? Why should we need it here?
2. In the above example, id function is the accumulator in the lambda function?
3. foldr's prototype is foldr :: (a -> b -> b) -> b -> [a] -> b, and the first parameter is a function which need two parameters, but the step function in the myFoldl's implementation uses 3 parameters, I'm complelely confused!

解决方案

Some explanations are in order!

What is the id function for? What is the role of? Why should we need it here?

id is the identity function, id x = x, and is used as the equivalent of zero when building up a chain of functions with function composition, (.). You can find it defined in the Prelude.

In the above example, id function is the accumulator in the lambda function?

The accumulator is a function that is being built up via repeated function application. There's no explicit lambda, since we name the accumulator, step. You can write it with a lambda if you want:

foldl f a bs = foldr ( g x -> g (f x b)) id bs a

Or as Graham Hutton would write:

5.1 The foldl operator

Now let us generalise from the suml example and consider the standard operator foldl that processes the elements of a list in left-to-right order by using a function f to combine values, and a value v as the starting value:

foldl :: (β → α → β) → β → ([α] → β)
foldl f v [ ] = v
foldl f v (x : xs) = foldl f (f v x) xs

Using this operator, suml can be redefined simply by suml = foldl (+) 0. Many other functions can be defined in a simple way using foldl. For example, the standard function reverse can redefined using foldl as follows:

reverse :: [α] → [α]
reverse = foldl (λxs x → x : xs) [ ]

This definition is more efficient than our original definition using fold, because it avoids the use of the inefficient append operator (++) for lists.

A simple generalisation of the calculation in the previous section for the function suml shows how to redefine the function foldl in terms of fold:

foldl f v xs = fold (λx g → (λa → g (f a x))) id xs v

In contrast, it is not possible to redefine fold in terms of foldl, due to the fact that foldl is strict in the tail of its list argument but fold is not. There are a number of useful ‘duality theorems’ concerning fold and foldl, and also some guidelines for deciding which operator is best suited to particular applications (Bird, 1998).

foldr's prototype is foldr :: (a -> b -> b) -> b -> [a] -> b

A Haskell programmer would say that the type of foldr is (a -> b -> b) -> b -> [a] -> b.

and the first parameter is a function which need two parameters, but the step function in the myFoldl's implementation uses 3 parameters, I'm complelely confused

This is confusing and magical! We play a trick and replace the accumulator with a function, which is in turn applied to the initial value to yield a result.

Graham Hutton explains the trick to turn foldl into foldr in the above article. We start by writing down a recursive definition of foldl:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v []       = v
foldl f v (x : xs) = foldl f (f v x) xs

And then refactor it via the static argument transformation on f:

foldl :: (a -> b -> a) -> a -> [b] -> a    
foldl f v xs = g xs v
    where
        g []     v = v
        g (x:xs) v = g xs (f v x)

Let's now rewrite g so as to float the v inwards:

foldl f v xs = g xs v
    where
        g []     = v -> v
        g (x:xs) = v -> g xs (f v x)

Which is the same as thinking of g as a function of one argument, that returns a function:

foldl f v xs = g xs v
    where
        g []     = id
        g (x:xs) = v -> g xs (f v x)

Now we have g, a function that recursively walks a list, apply some function f. The final value is the identity function, and each step results in a function as well.

But, we have handy already a very similar recursive function on lists, foldr!

2 The fold operator

The fold operator has its origins in recursion theory (Kleene, 1952), while the use of fold as a central concept in a programming language dates back to the reduction operator of APL (Iverson, 1962), and later to the insertion operator of FP (Backus, 1978). In Haskell, the fold operator for lists can be defined as follows:

fold :: (α → β → β) → β → ([α] → β)
fold f v [ ] = v
fold f v (x : xs) = f x (fold f v xs)

That is, given a function f of type α → β → β and a value v of type β, the function fold f v processes a list of type [α] to give a value of type β by replacing the nil constructor [] at the end of the list by the value v, and each cons constructor (:) within the list by the function f. In this manner, the fold operator encapsulates a simple pattern of recursion for processing lists, in which the two constructors for lists are simply replaced by other values and functions. A number of familiar functions on lists have a simple definition using fold.

This looks like a very similar recursive scheme to our g function. Now the trick: using all the available magic at hand (aka Bird, Meertens and Malcolm) we apply a special rule, the universal property of fold, which is an equivalence between two definitions for a function g that processes lists, stated as:

g [] = v
g (x:xs) = f x (g xs)

if and only if

g = fold f v

So, the universal property of folds states that:

    g = foldr k v

where g must be equivalent to the two equations, for some k and v:

    g []     = v
    g (x:xs) = k x (g xs)

From our earlier foldl designs, we know v == id. For the second equation though, we need to calculate the definition of k:

    g (x:xs)         = k x (g xs)        
<=> g (x:xs) v       = k x (g xs) v      -- accumulator of functions
<=> g xs (f v x)     = k x (g xs) v      -- definition of foldl
<=  g' (f v x)       = k x g' v          -- generalize (g xs) to g'
<=> k = x g' -> (a -> g' (f v x))      -- expand k. recursion captured in g'

Which, substituting our calculated definitions of k and v yields a definition of foldl as:

foldl :: (a -> b -> a) -> a -> [b] -> a    
foldl f v xs =
    foldr
        (x g -> (a -> g (f v x)))
        id
        xs
        v

The recursive g is replaced with the foldr combinator, and the accumulator becomes a function built via a chain of compositions of f at each element of the list, in reverse order (so we fold left instead of right).

This is definitely somewhat advanced, so to deeply understand this transformation, the universal property of folds, that makes the transformation possible, I recommend Hutton's tutorial, linked below.

---

References

• Haskell Wiki: Foldl as foldr
• A tutorial on the universality and expressiveness of fold, Graham Hutton, J. Functional Programming 9 (4): 355–372, July 1999.
• Malcolm, G. Algebraic data types and program transformation., PhD thesis, Groningen University.

这篇关于使用 foldr 编写 foldl的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！