使用foldr编写foldl

Question

在Real World Haskell中,第4章.函数式编程

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

上面的代码让我很困惑,有人打电话给dps用一个有意义的名字重写它,使它更清晰:

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

其他人,Jef G,通过提供一个例子并逐步展示基础机制,做得非常出色:

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

但我还是不能完全理解,这是我的问题:

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

有没有人可以帮助我？非常感谢!

Answer 1

一些解释是有序的!

什么是id函数？有什么作用？我们为什么要在这里需要它？

id是恒等函数,id x = x以及建立与功能的链时被用作零的等效功能的组合物,(.).您可以在Prelude中找到它.

在上面的例子中,id函数是lambda函数中的累加器？

累加器是通过重复功能应用构建的功能.没有明确的lambda,因为我们将累加器命名为step.如果你愿意,可以用lambda编写它:

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

或者像Graham Hutton写的那样:

5.1 foldl运营商

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

foldl :: (? ? ? ? ?) ? ? ? ([?] ? ?)
foldl f v [ ] = v
foldl f v (x : xs) = foldl f (f v x) xs

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

reverse :: [?] ? [?]
reverse = foldl (?xs x ? x : xs) [ ]

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

在上一节的功能在计算的简单概括suml显示了如何重新定义函数foldl在以下方面fold:

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

相反,它是不可能重新定义fold来讲foldl,由于这样的事实, foldl在其列表参数的尾部严格,但fold并非如此.有许多有用的"二元性定理"涉及fold和foldl,以及一些决定哪个算子最适合特定应用的指南(Bird,1998).

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

哈斯克尔程序员会说型的foldr是(a -> b -> b) -> b -> [a] -> b.

并且第一个参数是一个需要两个参数的函数,但myFoldl实现中的step函数使用了3个参数,我完全混淆了

这令人困惑和神奇!我们玩一个技巧并用一个函数替换累加器,然后将函数应用于初始值以产生结果.

格雷厄姆赫顿解释的伎俩转foldl成foldr以上文章.我们首先写下递归定义foldl:

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

然后通过静态参数转换重构它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)

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

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

这与作为g一个参数的函数的思考相同,它返回一个函数:

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

现在我们有g一个递归遍历列表的函数,应用一些函数f.最终值是身份函数,每个步骤也会产生一个函数.

但是,我们在列表上已经有了一个非常类似的递归函数foldr!

2折叠操作员

该fold运营商有其递归论(克莱尼,1952年)的起源,而采用fold作为编程语言的一个核心概念可以追溯到APL的减少运营商(艾弗森,1962年),后来到FP的插入操作符(巴克斯,1978).在Haskell中,fold列表的运算符可以定义如下:

fold :: (? ? ? ? ?) ? ? ? ([?] ? ?)
fold f v [ ] = v
fold f v (x : xs) = f x (fold f v xs)

即,给定的函数f类型的? ? ? ? ?和值v类型?,函数 fold f v处理类型的列表[?],得到类型的值?通过更换零构造[]在列表由所述值的末尾v,并且每个缺点的构造(:)通过在列表中功能f.以这种方式,fold运算符封装了一个简单的递归模式,用于处理列表,其中列表的两个构造函数简单地被其他值和函数替换.列表上的一些熟悉的函数使用简单的定义fold.

这看起来像是一个非常类似于我们g函数的递归方案.现在的诀窍是:使用所有可用的魔法(又名Bird,Meertens和Malcolm),我们应用一个特殊规则,即fold的通用属性,这是g处理列表的函数的两个定义之间的等价,声明如下:

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

当且仅当

g = fold f v

因此,折叠的普遍属性表明:

    g = foldr k v

这里g必须等同于两个方程,对于一些k和v:

    g []     = v
    g (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      -- 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'

其中,替换我们的计算定义k并v得出foldl的定义为:

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

递归g替换为foldr组合器,累加器变为通过f列表的每个元素的组合链构建的函数,以相反的顺序(因此我们向左折叠而不是向右折叠).

这肯定有点先进,所以要深入理解这种转换,折叠的通用属性,使转换成为可能,我推荐Hutton的教程,链接如下.

参考

• Haskell Wiki:Foldl as foldr
• 关于fold的普遍性和表现性的教程,Graham Hutton,J.Functional Programming 9(4):355 - 343,1999年7月.
• Malcolm,G.代数数据类型和程序转换.,博士论文,格罗宁根大学.

Answer 2

考虑以下类型foldr:

foldr :: (b -> a -> a) -> a -> [b] -> a

而类型step是类似的b -> (a -> a) -> a -> a.由于步骤已经过去foldr,我们可以得出结论,在这种情况下,折叠具有类似的类型(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)

这样可以更容易地看到发生了什么吗？它需要一个额外的参数,因为它返回一个函数,并且它的两种写入方式是等价的.还要注意后,多余的参数foldr:(foldr step id xs) z.括号中的部分是折叠本身,它返回一个函数,然后应用于该函数z.

Answer 3

这是我foldl可以用 表示的证明，foldr除了step函数引入的意大利面名称之外，我发现它非常简单。

命题foldl f z xs是等价于

myfoldl f z xs = foldr step_f id xs z
        where step_f x g a = g (f a x)

这里要注意的第一件重要的事情是第一行的右手边实际上被评估为

(foldr step_f id xs) z

因为foldr只需要三个参数。这已经暗示 the foldrwill 不是计算值而是计算一个柯里化函数，然后将其应用于z. 有两种情况需要调查以确定是否myfoldl为foldl：

1. 基本情况：空列表

     myfoldl f z []
   = foldr step_f id [] z    (by definition of myfoldl)
   = id z                    (by definition of foldr)
   = z
   
     foldl f z []
   = z                       (by definition of foldl)
   

2. 非空列表

     myfoldl f z (x:xs)
   = foldr step_f id (x:xs) z          (by definition of myfoldl)
   = step_f x (foldr step_f id xs) z   (-> apply step_f)
   = (foldr step_f id xs) (f z x)      (-> remove parentheses)
   = foldr step_f id xs (f z x)
   = myfoldl f (f z x) xs              (definition of myfoldl)
   
     foldl f z (x:xs)
   = foldl f (f z x) xs
   

由于在 2. 中第一行和最后一行在两种情况下具有相同的形式，因此可用于将列表向下折叠直到xs == []，在这种情况下 1. 保证相同的结果。所以通过归纳，myfoldl == foldl.

Answer 4

^{(快速浏览我的答案[1],[2],[3],[4]以确保你理解Haskell的语法,高阶函数,currying,函数组合,$运算符,中缀/前缀运算符,section和lambdas )}

折叠的普遍性

一折只是一个特定类型的递归的编纂.普遍性属性简单地说明,如果你的递归符合某种形式,它可以根据一些正式规则转换成折叠.相反,每个折叠都可以转换成这种递归.再一次,一些递归可以转换为折叠,给出完全相同的答案,并且一些递归不能,并且有一个确切的过程来做到这一点.

基本上,如果您的递归函数的工作列表上的一个看起来像在左边,你可以将它折叠一个正确的,替代f和v对实际存在的东西.

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

例如:

sum []     = 0   {- recursion becomes fold -}
sum (x:xs) = x + sum xs   ?     sum = foldr 0 (+)

这里v = 0和sum (x:xs) = x + sum xs相当于sum (x:xs) = (+) x (sum xs),因此f = (+).还有2个例子

product []     = 1
product (x:xs) = x * product xs  ?  product = foldr 1 (*)

length []     = 0
length (x:xs) = 1 + length xs    ?  length = foldr (\_ a -> 1 + a) 0

行使:

1. 实行map,filter,reverse,concat和concatMap递归,就像在上述功能左侧.

2. 转换这些5个功能FOLDR 根据上面的公式,也就是,替换f和v在折叠式中右边.

通过折叠器折叠

如何编写一个从左到右对数字求和的递归函数？

sum [] = 0     -- given `sum [1,2,3]` expands into `(1 + (2 + 3))`
sum (x:xs) = x + sum xs

找到的第一个递归函数在开始累加之前完全展开,这不是我们需要的.一种方法是创建一个具有累加器的递归函数,它会立即在每一步上加上数字(阅读尾递归以了解有关递归策略的更多信息):

suml :: [a] -> a
suml xs = suml' xs 0
  where suml' [] n = n   -- auxiliary function
        suml' (x:xs) n = suml' xs (n+x)

好吧,停!在GHCi中运行此代码并确保您了解它的工作原理,然后仔细并仔细地继续.suml不能用折叠重新定义,但suml'可以.

suml' []       = v    -- equivalent: v n = n
suml' (x:xs) n = f x (suml' xs) n

suml' [] n = n从功能定义来看,对吗？并v = suml' []从通用属性公式.这给v n = n了一个函数,它立即返回它收到的任何东西:v = id.我们算一下f:

suml' (x:xs) n = f x (suml' xs) n
-- expand suml' definition
suml' xs (n+x) = f x (suml' xs) n
-- replace `suml' xs` with `g`
g (n+x)        = f x g n

因此,suml' = foldr (\x g n -> g (n+x)) id因此,suml = foldr (\x g n -> g (n+x)) id xs 0.

foldr (\x g n -> g (n + x)) id [1..10] 0 -- return 55

现在我们只需要+通过变量函数进行泛化,替换:

foldl f a xs = foldr (\x g n -> g (n `f` x)) id xs a
foldl (-) 10 [1..5] -- returns -5

结论

现在阅读Graham Hutton 关于折叠的普遍性和表现力的教程.得到一些笔和纸,试着找出他写的所有东西,直到你自己得到大部分的折叠.如果你不理解某些东西,不要流汗,你可以随时回来,但也不要拖延太多.