Quel est l'équivalent «pythonique» de la fonction «replier» de la programmation fonctionnelle?

Quelle est la manière la plus idiomatique de réaliser quelque chose comme ce qui suit, dans Haskell:

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

Ou son équivalent en Ruby:

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

De toute évidence, Python fournit la reducefonction, qui est une implémentation de fold, exactement comme ci-dessus, cependant, on m'a dit que la méthode de programmation `` pythonique '' était d'éviter les lambdatermes et les fonctions d'ordre supérieur, préférant les compréhensions de listes lorsque cela était possible. Par conséquent, existe-t-il un moyen préféré de plier une liste, ou une structure de type liste en Python qui n'est pas la reducefonction, ou est-ce reducela manière idiomatique d'y parvenir?

La manière pythonique de sommer un tableau utilise sum. À d'autres fins, vous pouvez parfois utiliser une combinaison de reduce(du functoolsmodule) et du operatormodule, par exemple:

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

Sachez que reducec'est en fait un foldl, en termes Haskell. Il n'y a pas de syntaxe spéciale pour effectuer des replis, il n'y a pas de fonction intégrée foldret l'utilisation reduceavec des opérateurs non associatifs est considérée comme un mauvais style.

L'utilisation de fonctions d'ordre supérieur est assez pythonique; il fait bon usage du principe de Python selon lequel tout est un objet, y compris les fonctions et les classes. Vous avez raison de dire que les lambdas sont désapprouvés par certains pythonistes, mais surtout parce qu'ils ont tendance à ne pas être très lisibles lorsqu'ils deviennent complexes.

Haskell

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

Python

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

De toute évidence, c'est un exemple trivial pour illustrer un point. En Python, vous le feriez sum([1,2,3,4,5])et même les puristes de Haskell préféreraient généralement sum [1,2,3,4,5].

Pour les scénarios non triviaux où il n'y a pas de fonction de commodité évidente, l'approche pythonique idiomatique consiste à écrire explicitement la boucle for et à utiliser l'affectation de variable mutable au lieu d'utiliser reduceou a fold.

Ce n'est pas du tout le style fonctionnel, mais c'est la manière «pythonique». Python n'est pas conçu pour les puristes fonctionnels. Découvrez comment Python favorise les exceptions pour le contrôle de flux pour voir à quel point python idiomatique est non fonctionnel.

Dans Python 3, le reducea été supprimé: Notes de version . Néanmoins, vous pouvez utiliser le module functools

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

D'autre part, la documentation exprime une préférence pour for-loop au lieu de reduce, d'où:

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

En commençant Python 3.8, et en introduisant des expressions d'affectation (PEP 572) ( :=opérateur), qui donne la possibilité de nommer le résultat d'une expression, nous pouvons utiliser une compréhension de liste pour répliquer ce que les autres langages appellent les opérations fold / foldleft / reduction:

Étant donné une liste, une fonction réductrice et un accumulateur:

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

on peut se plier itemsavec fpour obtenir le résultat accumulation:

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

ou sous forme condensée:

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

Notez qu'il s'agit en fait également d'une opération "scanleft" car le résultat de la compréhension de liste représente l'état de l'accumulation à chaque étape:

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

Vous pouvez également réinventer la roue:

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)

Pas vraiment de réponse à la question, mais des one-liners pour foldl et foldr:

a = [8,3,4]

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

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

La vraie réponse à ce problème (de réduire) est: Utilisez simplement une boucle!

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

Ce sera plus rapide qu'une réduction et des choses comme PyPy peuvent optimiser des boucles comme ça.

BTW, le cas de somme doit être résolu avec la sumfonction

Je crois que certains des répondants à cette question n'ont pas compris l'implication plus large de la foldfonction en tant qu'outil abstrait. Oui, sumon peut faire la même chose pour une liste d'entiers, mais c'est un cas trivial. foldest plus générique. Il est utile lorsque vous avez une séquence de structures de données de forme variable et que vous souhaitez exprimer proprement une agrégation. Ainsi, au lieu d'avoir à construire une forboucle avec une variable d'agrégation et à la recalculer manuellement à chaque fois, une foldfonction (ou la version Python, qui reducesemble correspondre à) permet au programmeur d'exprimer beaucoup plus clairement l'intention de l'agrégation en fournissant simplement deux choses:

• Une valeur de départ ou "de départ" par défaut pour l'agrégation.
• Une fonction qui prend la valeur actuelle de l'agrégation (en commençant par la "graine") et l'élément suivant dans la liste, et renvoie la valeur d'agrégation suivante.

Je suis peut-être assez en retard à la fête, mais nous pouvons créer une personnalisation en foldrutilisant un simple calcul lambda et une fonction curry. Voici mon implémentation de foldr en 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))

Même si l'implémentation est récursive (peut être lente), elle affichera les valeurs 15et 120respectivement