标签归档:fold

函数式编程中的“ pythonic”等同于“ fold”函数是什么?

问题:函数式编程中的“ pythonic”等同于“ fold”函数是什么?

在Haskell中,实现以下目标的最惯用的方法是:

foldl (+) 0 [1,2,3,4,5]
--> 15

或等效的Ruby:

[1,2,3,4,5].inject(0) {|m,x| m + x}
#> 15

显然,Python提供了reduce与fold完全相同的功能,但实际上是如上所述的fold的实现,但是,有人告诉我,“ pythonic”编程方式是避免使用lambda术语和高阶函数,并尽可能使用列表理解。因此,有没有一种首选的方式来折叠列表或不是Python reduce函数的类似列表的结构,或者是reduce惯用的方式来实现此目的?

What is the most idiomatic way to achieve something like the following, in Haskell:

foldl (+) 0 [1,2,3,4,5]
--> 15

Or its equivalent in Ruby:

[1,2,3,4,5].inject(0) {|m,x| m + x}
#> 15

Obviously, Python provides the reduce function, which is an implementation of fold, exactly as above, however, I was told that the ‘pythonic’ way of programming was to avoid lambda terms and higher-order functions, preferring list-comprehensions where possible. Therefore, is there a preferred way of folding a list, or list-like structure in Python that isn’t the reduce function, or is reduce the idiomatic way of achieving this?


回答 0

用Python方式对数组求和的方法是使用sum。为了其他目的,有时可以使用reduce(来自functools模块)和operator模块的某种组合,例如:

def product(xs):
    return reduce(operator.mul, xs, 1)

请注意,reduce实际上这是一个foldl用Haskell表示的。没有执行折叠的特殊语法,没有内置函数foldr,实际上reduce与非关联运算符一起使用被认为是不良样式。

使用高阶函数是相当Python的;它很好地利用了Python的原理,即一切都是对象,包括函数和类。没错,lambda被某些Pythonista所反对,但这主要是因为它们变得复杂时往往不太可读。

The Pythonic way of summing an array is using sum. For other purposes, you can sometimes use some combination of reduce (from the functools module) and the operator module, e.g.:

def product(xs):
    return reduce(operator.mul, xs, 1)

Be aware that reduce is actually a foldl, in Haskell terms. There is no special syntax to perform folds, there’s no builtin foldr, and actually using reduce with non-associative operators is considered bad style.

Using higher-order functions is quite pythonic; it makes good use of Python’s principle that everything is an object, including functions and classes. You are right that lambdas are frowned upon by some Pythonistas, but mostly because they tend not to be very readable when they get complex.


回答 1

哈斯克尔

foldl (+) 0 [1,2,3,4,5]

Python

reduce(lambda a,b: a+b, [1,2,3,4,5], 0)

显然,这是一个说明问题的简单例子。在Python中,您只需要这样做sum([1,2,3,4,5]),甚至Haskell纯粹主义者通常也会更喜欢sum [1,2,3,4,5]

对于没有明显便利函数的非平凡场景,惯用的pythonic方法是显式写出for循环并使用可变变量分配,而不是使用reduceor fold

那根本不是功能样式,而是“ pythonic”方式。Python并非为功能纯正者设计。了解Python如何支持流控制的异常,以了解非功能性惯用python的情况。

Haskell

foldl (+) 0 [1,2,3,4,5]

Python

reduce(lambda a,b: a+b, [1,2,3,4,5], 0)

Obviously, that is a trivial example to illustrate a point. In Python you would just do sum([1,2,3,4,5]) and even Haskell purists would generally prefer sum [1,2,3,4,5].

For non-trivial scenarios when there is no obvious convenience function, the idiomatic pythonic approach is to explicitly write out the for loop and use mutable variable assignment instead of using reduce or a fold.

That is not at all the functional style, but that is the “pythonic” way. Python is not designed for functional purists. See how Python favors exceptions for flow control to see how non-functional idiomatic python is.


回答 2

在Python 3中,reduce已被删除:版本说明。不过,您可以使用functools模块

import operator, functools
def product(xs):
    return functools.reduce(operator.mul, xs, 1)

另一方面,文档表达了对for-loop而不是的偏好reduce,因此:

def product(xs):
    result = 1
    for i in xs:
        result *= i
    return result

In Python 3, the reduce has been removed: Release notes. Nevertheless you can use the functools module

import operator, functools
def product(xs):
    return functools.reduce(operator.mul, xs, 1)

On the other hand, the documentation expresses preference towards for-loop instead of reduce, hence:

def product(xs):
    result = 1
    for i in xs:
        result *= i
    return result

回答 3

您也可以重新发明轮子:

def fold(f, l, a):
    """
    f: the function to apply
    l: the list to fold
    a: the accumulator, who is also the 'zero' on the first call
    """ 
    return a if(len(l) == 0) else fold(f, l[1:], f(a, l[0]))

print "Sum:", fold(lambda x, y : x+y, [1,2,3,4,5], 0)

print "Any:", fold(lambda x, y : x or y, [False, True, False], False)

print "All:", fold(lambda x, y : x and y, [False, True, False], True)

# Prove that result can be of a different type of the list's elements
print "Count(x==True):", 
print fold(lambda x, y : x+1 if(y) else x, [False, True, True], 0)

You can reinvent the wheel as well:

def fold(f, l, a):
    """
    f: the function to apply
    l: the list to fold
    a: the accumulator, who is also the 'zero' on the first call
    """ 
    return a if(len(l) == 0) else fold(f, l[1:], f(a, l[0]))

print "Sum:", fold(lambda x, y : x+y, [1,2,3,4,5], 0)

print "Any:", fold(lambda x, y : x or y, [False, True, False], False)

print "All:", fold(lambda x, y : x and y, [False, True, False], True)

# Prove that result can be of a different type of the list's elements
print "Count(x==True):", 
print fold(lambda x, y : x+1 if(y) else x, [False, True, True], 0)

回答 4

并不是真正回答这个问题,而是折叠和折叠的一线:

a = [8,3,4]

## Foldl
reduce(lambda x,y: x**y, a)
#68719476736

## Foldr
reduce(lambda x,y: y**x, a[::-1])
#14134776518227074636666380005943348126619871175004951664972849610340958208L

Not really answer to the question, but one-liners for foldl and foldr:

a = [8,3,4]

## Foldl
reduce(lambda x,y: x**y, a)
#68719476736

## Foldr
reduce(lambda x,y: y**x, a[::-1])
#14134776518227074636666380005943348126619871175004951664972849610340958208L

回答 5

开始Python 3.8并引入赋值表达式(PEP 572):=运算符),这使您可以为表达式的结果命名,我们可以使用列表推导来复制其他语言称为fold / foldleft / reduce的操作:

给定一个列表,一个约简函数和一个累加器:

items = [1, 2, 3, 4, 5]
f = lambda acc, x: acc * x
accumulator = 1

我们可以折叠itemsf在为了获得所得accumulation

[accumulator := f(accumulator, x) for x in items]
# accumulator = 120

或以压缩形式形成:

acc = 1; [acc := acc * x for x in [1, 2, 3, 4, 5]]
# acc = 120

请注意,这实际上也是“ scanleft”操作,因为列表理解的结果表示每个步骤的累加状态:

acc = 1
scanned = [acc := acc * x for x in [1, 2, 3, 4, 5]]
# scanned = [1, 2, 6, 24, 120]
# acc = 120

Starting Python 3.8, and the introduction of assignment expressions (PEP 572) (:= operator), which gives the possibility to name the result of an expression, we can use a list comprehension to replicate what other languages call fold/foldleft/reduce operations:

Given a list, a reducing function and an accumulator:

items = [1, 2, 3, 4, 5]
f = lambda acc, x: acc * x
accumulator = 1

we can fold items with f in order to obtain the resulting accumulation:

[accumulator := f(accumulator, x) for x in items]
# accumulator = 120

or in a condensed formed:

acc = 1; [acc := acc * x for x in [1, 2, 3, 4, 5]]
# acc = 120

Note that this is actually also a “scanleft” operation as the result of the list comprehension represents the state of the accumulation at each step:

acc = 1
scanned = [acc := acc * x for x in [1, 2, 3, 4, 5]]
# scanned = [1, 2, 6, 24, 120]
# acc = 120

回答 6

对这个(减少)问题的实际答案是:只需使用一个循环!

initial_value = 0
for x in the_list:
    initial_value += x #or any function.

这将比reduce更快,而PyPy之类的东西可以优化循环。

顺便说一句,总和的情况应该用sum函数来解决

The actual answer to this (reduce) problem is: Just use a loop!

initial_value = 0
for x in the_list:
    initial_value += x #or any function.

This will be faster than a reduce and things like PyPy can optimize loops like that.

BTW, the sum case should be solved with the sum function


回答 7

我相信这个问题的一些回答者错过了该fold功能作为抽象工具的广泛含义。是的,sum可以对整数列表执行相同的操作,但这是不重要的情况。fold更通用。当您具有一系列形状各异的数据结构并想要清晰地表达聚合时,此功能很有用。因此,不必for每次都用一个聚合变量建立一个循环并手动重新计算它,fold函数(或reduce似乎对应的Python版本)允许程序员通过简单地提供以下内容来更清楚地表达聚合的意图:两件事情:

  • 聚合的默认起始值​​或“种子”值。
  • 该函数采用聚合的当前值(以“种子”开头)和列表中的下一个元素,并返回下一个聚合值。

I believe some of the respondents of this question have missed the broader implication of the fold function as an abstract tool. Yes, sum can do the same thing for a list of integers, but this is a trivial case. fold is more generic. It is useful when you have a sequence of data structures of varying shape and want to cleanly express an aggregation. So instead of having to build up a for loop with an aggregate variable and manually recompute it each time, a fold function (or the Python version, which reduce appears to correspond to) allows the programmer to express the intent of the aggregation much more plainly by simply providing two things:

  • A default starting or “seed” value for the aggregation.
  • A function that takes the current value of the aggregation (starting with the “seed”) and the next element in the list, and returns the next aggregation value.

回答 8

我参加聚会可能已经很晚了,但是我们可以foldr使用简单的lambda演算和curried函数创建自定义项。这是我在python中实现的foldr。

def foldr(func):
    def accumulator(acc):
        def listFunc(l):
            if l:
                x = l[0]
                xs = l[1:]
                return func(x)(foldr(func)(acc)(xs))
            else:
                return acc
        return listFunc
    return accumulator  


def curried_add(x):
    def inner(y):
        return x + y
    return inner

def curried_mult(x):
    def inner(y):
        return x * y
    return inner

print foldr(curried_add)(0)(range(1, 6))
print foldr(curried_mult)(1)(range(1, 6))

即使实现是递归的(可能很慢),它也会分别打印值15120

I may be quite late to the party, but we can create custom foldr using simple lambda calculus and curried function. Here is my implementation of foldr in python.

def foldr(func):
    def accumulator(acc):
        def listFunc(l):
            if l:
                x = l[0]
                xs = l[1:]
                return func(x)(foldr(func)(acc)(xs))
            else:
                return acc
        return listFunc
    return accumulator  


def curried_add(x):
    def inner(y):
        return x + y
    return inner

def curried_mult(x):
    def inner(y):
        return x * y
    return inner

print foldr(curried_add)(0)(range(1, 6))
print foldr(curried_mult)(1)(range(1, 6))

Even though the implementation is recursive (might be slow), it will print the values 15 and 120 respectively