foldl 和 foldr 的变换

栏目: Python · 发布时间: 5年前

内容简介:foldl 和 foldr 的类型签名为:.. code:: haskell可以看出来他们接受的参数为:一个函数,一个initial value,一个列表, 然后把整个列表变成和列表类型相同的value。举个例子:

foldl 和 foldr 的类型签名为:

.. code:: haskell

Prelude> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
Prelude> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

可以看出来他们接受的参数为:一个函数,一个initial value,一个列表, 然后把整个列表变成和列表类型相同的value。举个例子:

.. code:: haskell

foldl (+) 0 [1..5]
-- 展开成
= ((((1 + 2) + 3) + 4) + 5)
= 15

foldr (+) 0 [1..5]
-- 展开成
= (1 + (2 + (3 + (4 + 5))))
= 15

从结果来看foldl和foldr似乎可以相互替换,但并不是这样的,上例结果相同只是因为 加法(+)满足结合律,同样是这么几个数,从左往右加和从右往左加结果是一样的。 但对于减法就不是这样了,我们继续看代码:

.. code:: haskell

Prelude> foldl (-) 0 [1..5]
-15
Prelude> foldr (-) 0 [1..5]
3

那么foldl和foldr长得那么像,能不能互相实现呢?我们来用foldl实现foldr, 首先我们从类型签名看起。

  • foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

  • foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

可以看出来,首先接受的第一个函数的参数是相反的,所以对于 foldr func init alist 首先要把函数的参数反过来,所以我们用了 flip, foldl (flip func) init alist (flip 的类型为 flip :: (a -> b -> c) -> b -> a -> c )。 但是这还不够,foldl是从左边向右两个两个处理,而foldr是从右向左,我们需要将 alist反转,所以我们用了 reverse,他的类型是 reverse :: [a] -> [a] :

.. code:: haskell

foldr func init alist = foldl (flip func) init (reverse alist)
-- 可以化简成:
foldr func init = (foldl (flip func) init) . reverse

python中的foldl

python中有reduce,作用相当于Haskell中的foldl:

.. code:: python

>>> import operator
>>> from functools import reduce
>>> reduce(operator.add, list(range(1, 6)), 0)
15

参考资料:

.. [#] <https://wiki.haskell.org/Foldr_Foldl_Foldl'> _


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

以匠心,致设计:网易 UEDC 用户体验设计

以匠心,致设计:网易 UEDC 用户体验设计

网易用户体验设计中心 / 电子工业出版社 / 2018-8 / 95.00元

为什么网易云音乐的体验流畅细腻、富有温度?为什么网易严选App的UI设计让人感到温馨、舒适?为什么网易蜗牛读书App的界面设计让用户爱不释手…… 《以匠心,致设计:网易 UEDC 用户体验设计》是网易用户体验设计团队对自身过去的设计思考的精心总结,最大程度还原了网易产品背后的设计故事,内容涵盖设计基础、设计实践、方法思考、成长指南四章,借助网易产品设计的实际案例具体讲述了设计师日常工作中不可......一起来看看 《以匠心,致设计:网易 UEDC 用户体验设计》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试