What is the pythonic equivalent to the fold function from functional programming

Question

What is the most idiomatic way to achieve something like the following  in Haskell   foldl     0  1 2 3 4 5  -- gt  15   Or its equivalent in Ruby    1 2 3 4 5  inject 0    m x  m   x    gt  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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

[python] What is the 'pythonic' equivalent to the 'fold' function from functional programming?

Examples related to python

Examples related to list

Examples related to functional-programming

Examples related to reduce

Examples related to fold