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

116

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?

Mistertim
la source
2
sumn'est pas assez bon?
JBernardo
3
Je ne sais pas si c'est un bon exemple pour votre question. Cela peut être facilement réalisé avec sum, vous voudrez peut-être fournir différents types d'exemples.
jamylak
14
Hey JBernardo - La somme sur une liste de nombres était un exemple plutôt dégénéré, je suis plus intéressé par l'idée générale d'accumuler les éléments d'une liste en utilisant une opération binaire et une valeur de départ, sans additionner spécifiquement les entiers.
mistertim
1
@mistertim: sum()fournit en fait des fonctionnalités limitées avec cela. sum([[a], [b, c, d], [e, f]], [])renvoie [a, b, c, d, e, f]par exemple.
Joel Cornett
Bien que le faire avec des listes soit une bonne démonstration des choses à surveiller avec cette technique - +sur les listes est une opération temporelle linéaire à la fois dans le temps et dans la mémoire, ce qui rend l'appel quadratique. L'utilisation list(itertools.chain.from_iterable([a], [b,c,d],[e,f],[]])est globalement linéaire - et si vous n'avez besoin de l'itérer qu'une seule fois, vous pouvez abandonner l'appel à listpour le rendre constant en termes de mémoire.
lvc

Réponses:

115

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.

Fred Foo
la source
4
@JBernardo: vous dites que tout ce qui n'est pas dans le module intégré n'est pas pythonique?
Fred Foo
4
Non, ce serait stupide de dire. Mais donnez-moi une seule raison pour laquelle pensez-vous que GvR détesterait tant la fonction de réduction au point de la supprimer des fonctions intégrées?
JBernardo
6
@JBernardo: parce que les gens essaient de jouer des tours trop intelligents avec. Pour citer ce billet de blog, «l'applicabilité de reduce()est à peu près limitée aux opérateurs associatifs, et dans tous les autres cas, il est préférable d'écrire explicitement la boucle d'accumulation». Son utilisation est donc limitée, mais même GvR a apparemment dû l'admettre suffisamment utile pour le conserver dans la bibliothèque standard.
Fred Foo
13
@JBernardo, cela signifie-t-il que chaque utilisation de fold dans Haskell et Scheme est également mauvaise? C'est juste un style de programmation différent, l'ignorer et mettre vos doigts dans vos oreilles et dire que ce n'est pas clair ne le fait pas. Comme la plupart des choses qui sont d'un style différent, il faut de la pratique pour s'y habituer . L'idée est de classer les choses dans des catégories générales pour qu'il soit plus facile de raisonner sur les programmes. "Oh, je veux faire ça, hmm, ça ressemble à un pli" (ou une carte, ou un dépliage, ou un dépliage puis un pli dessus)
Wes
3
Lambda en Python ne peut pas contenir plus d'une expression. Vous ne pouvez pas rendre les choses complexes même si vous essayez dur. Ainsi, les pythonistes qui ne les aiment pas ne sont probablement pas habitués et n'aiment donc pas le style de programmation fonctionnel.
golem
16

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.

argile
la source
12
les plis sont utiles à plus que des "puristes" fonctionnels. Ce sont des abstractions à usage général. Les problèmes récursifs sont omniprésents en informatique. Les plis offrent un moyen de supprimer le passe-partout et un moyen de sécuriser les solutions récursives dans des langages qui ne prennent pas en charge la récursivité de manière native. Donc une chose très pratique. Les préjugés de GvR dans ce domaine sont malheureux.
itsbruce
12

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
Kyr
la source
8
reducen'a pas été supprimé de la bibliothèque standard Python 3. reducedéplacé vers le functoolsmodule que vous montrez.
terre battue
@clay, je viens de prendre la phrase des notes de publication de Guido, mais vous avez peut-être raison :)
Kyr
6

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
Xavier Guihot
la source
5

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)
Frédéric
la source
Vous échangez les arguments fdans votre cas récursif.
KayEss
7
Parce que Python n'a pas de récursivité de queue, cela se cassera sur des listes plus longues et est inutile. De plus, il ne s'agit pas vraiment de la fonction «fold», mais simplement d'un pli gauche, c'est-à-dire foldl, c'est-à-dire exactement ce reducequi offre déjà (notez que la signature de la fonction de réduction est reduce(function, sequence[, initial]) -> value- elle inclut également la fonctionnalité de donner une valeur initiale accumulateur).
cemper93
5

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
Mehdi Nellen
la source
2
Je pense que cela est une meilleure façon d'écrire votre foldr: reduce(lambda y, x: x**y, reversed(a)). Il a maintenant une utilisation plus naturelle, fonctionne avec des itérateurs et consomme moins de mémoire.
Mateen Ulhaq
2

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

JBernardo
la source
5
Cela ne serait pas considéré comme pythonique pour un exemple comme celui-ci.
jamylak
7
Les boucles Python sont notoirement lentes. Utiliser (ou abuser) reduceest un moyen courant d'optimiser un programme Python.
Fred Foo
2
@larsmans S'il vous plaît, ne venez pas dire que réduire est plus rapide qu'une simple boucle ... Il y aura toujours une surcharge d'appel de fonction pour chaque itération. De plus, encore une fois, Pypy peut optimiser les boucles à la vitesse C
JBernardo
1
@JBernardo: oui, c'est ce que je prétends. Je viens de profiler ma version de productcontre un dans votre style, et c'est plus rapide (marginalement, cependant).
Fred Foo
1
@JBernardo En supposant une fonction intégrée (comme operator.add) comme argument à réduire: cet appel supplémentaire est un appel C (qui est beaucoup moins cher qu'un appel Python), et cela évite de distribuer et d'interpréter quelques instructions de bytecode, ce qui peut facilement provoquer des dizaines de appels de fonction.
1

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.
rq_
la source
Salut rq_! Je pense que votre réponse serait améliorée et ajouterait beaucoup si vous donniez un exemple non trivial de ce foldqui est difficile à faire proprement en Python, puis " fold" cela en Python :-)
Scott Skiles
0

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

Haleter
la source