Fold Function

The FoldFunction is one of the CommonHigherOrderFunctions. It generally takes a sequence, a function of two arguments, and an initial value (often the "identity" value of the function--i.e. 0 for addition, 1 for multiplication, false for boolean OR, negative infinity for maximum, etc.) and combines the sequence by applying the function to the sequence's end element and the result of recursively folding the function over the rest of the sequence. Folds can be left-associative (foldl) or right-associative (foldr) -- can start at either end of the list.

That's not a terribly clear definition. Here's some code for right fold: 

 -- If the list is empty, return the initial value.
 foldr f initial []            = initial
 -- Otherwise, use f to combine the first element of the list
 -- with the fold of the rest of the list.
 foldr f initial [x1, x2, ...] = f x1 (fold f initial [x2, ...])


 foldr (+) 0 [1,2,3] => 6
 foldr (*) 1 [4,5,6] => 120
There are also alternate versions of the left and right folds which do not take an initial value. They use the first element as the initial value. Here's some code for right fold with no initial value: 

 -- If the list has one element, return it.
 foldr1 f [x]           = x
 -- Otherwise, use f to combine the first element of the list
 -- with the fold of the rest of the list.
 foldr1 f [x1, x2, ...] = f x1 (fold f initial [x2, ...])
 -- Note: it is an error to use this on an empty list


 foldr1 (\x y -> x ++ "|" ++ y) ["foo","bar","baz"] => "foo|bar|baz"

HaskellLanguage obviously comes with fold functions in Prelude: 

  foldl (+) 0 numbers
  foldr (+) 0 numbers
  foldl1 (+) numbers
  foldr1 (+) numbers

OcamlLanguage comes with left and right fold functions in the List and Array modules; also many other modules like Set, Map also have fold functions. 

 # List.fold_left (+) 0 [4; 5; 6];;
 - : int = 15
 # List.fold_right min [4; 5; 6; 3; 5] max_int;;
 - : int = 3
Note that fold-left takes the initial value before the list, whereas fold-right takes the initial value after the list.

FsharpLanguage (OcamlLanguage for DotNet): 

 > List.fold_left (+) 0 [4; 5; 6];;
 val it : int = 15
 > Seq.fold (+) 0.0 [4.0; 5.0; 6.0];;
 val it : float = 15.0
 > List.fold_right min [4; 5; 6; 3; 5] System.Int32.MaxValue;;
 val it : int = 3

SmlLanguage comes with left and right fold functions in the List, Array, Vector, and many other modules. The functions for lists are already exported to the top-level: 

 - foldl op+ 0 [4, 5, 6];
 val it = 15 : int
 - foldr Int.min (valOf Int.maxInt) [4, 5, 6, 3, 5];
 val it = 3 : int
One peculiarity is that the function specified in fold-left takes its arguments in the opposite order than usual, so notice: 
 - foldl op^ "" ["foo", "bar", "baz"];
 val it = "bazbarfoo" : string

In SmalltalkLanguage: #inject:into: 

  #(1 2 3 4) inject: 0 into: [:sum :total | sum + total]

The PerlLanguage <s>doesn't have a fold function</s> (see List::Util::reduce() below), though the effect can be had via map. 

  map { $sum += $_ } @arrayofnumbers;
For this case, yes. I can't see anything in perlfunc(1) guaranteeing the order in which it processes the list, though, so can we depend on it in general? Yes. Much would break if map didn't process the list in order. The description of map in perlfunc(1) is overly succinct.

Except that the map operator returns a list. If you aren't going to use that list, you should use the "foreach" operator instead. Here's a much more specific interpretation, in PerlLanguage, of the definition given at the top of the page: 

  #!/usr/bin/perl -w


  use strict;


  sub foldr {


    my ($fold_func, $initial, @args) = @_;
    die "usage: code, initial, list" unless
      ref $fold_func eq "CODE" and defined $initial;


    my $intermediate = $initial;
    foreach my $arg (reverse @args) {
      $intermediate = &$fold_func($intermediate, $arg);
    }


    return $intermediate;
  }


  my $add_sub = sub { return $_[0] + $_[1] };  
  my $mult_sub = sub { return $_[0] * $_[1] };
  my @list = (1 .. 10);
  my $add_init = 0;
  my $mult_init = 1;


  my $result = foldr( $add_sub, $add_init, @list );
  print "Result of right side fold (add): $result\n";
  $result = foldr( $mult_sub, $mult_init, @list); 
  print "Result of right side fold (mult): $result\n";
  print "--JeffBay\n";
Perl's List::Util core module contains a function called "reduce", which can be used like Haskell's foldl or foldl1. The function is given as a block whose inputs are bound to "$a" and "$b". The block is followed by the list of things to fold over. If you want to give an initial argument, then provide it as the first element in the list. This is easy in Perl because lists are flattened in list context, so there is no difference between passing an array argument, or passing its elements individually, or passing the first element and an array of the rest, etc. 

  use List::Util qw(reduce);
  reduce {"$a|$b"} ("foo","bar","baz"); #=> "foo|bar|baz"; used like foldl1
  reduce {[@$a, $b]} [], (1, 2, 3, 4);  #=> [1, 2, 3, 4];  used like foldl, with initial argument first in the list

The PythonLanguage calls it reduce; this is a left fold: 

  reduce(operator.add, [1,2,3,4])
  reduce(lambda x,y: x+y, [1,2,3,4])
You can get the effect of the parameter called initial above by giving an optional third argument.

In Python 3.x it has been moved to "functools.reduce".

CommonLisp has reduce too: 

  (reduce #'+ (list 1 2 3 4))
As one might expect, this is hairier than inject:into: or Python reduce. In particular, it can start at either end of the sequence (so it subsumes the things sometimes called foldl and foldr) and can be told to act on a proper subsequence of the sequence it's given. See chapter 17 of the CommonLispHyperSpec.

In CsharpLanguage 3.0 or greater, one can either use the built-in Sum|Max|Min|Avg operators or the more general Aggregate operator that takes a seed and a lambda: 

 int[] numbers = { 1, 2, 3, 4 };


 int sum = numbers.Sum();
 int sum2 = numbers.Aggregate(0, (s, n) => s + n);
 int product = numbers.Aggregate(1, (s, n) => s * n);
These operators work over any IEnumerable-based sequence. When used against RDMBS-backed sequences, the AST gets rewritten to SQL for remote evaluation where possible.

Prior to CsharpLanguage 3.0, writing Aggregate is trivial but needed to be done by the user: 

 delegate T Function<T1, T2, T>(T1 a1, T2 a2);
 static T Aggregate<T1, T>(IEnumerable<T1> s, Function<T, T1, T> proc) {
   return Aggregate(s, default(T), proc);
 }
 static T Aggregate<T1, T>(IEnumerable<T1> s, T initialValue, Function<T, T1, T> proc) {
   T result = initialValue;
   foreach (T1 e in s) 
     result = proc(result, e);
   return result;
 }
With this in place, we can write the program like this: 

 int[] numbers = { 1, 2, 3, 4 };
 int sum = Aggregate(numbers, 0, (s, n) => s + n);
 int product = Aggregate(numbers, 1, (s, n) => s*n);

In CeePlusPlus (C++) using the StandardTemplateLibrary; this is in header <numeric> 

   int a[4] = {1, 2, 3, 4};
   int sum = accumulate( a, a+4, 0 ); // plus() is implied
   int product = accumulate( a, a+4, 1, times<int>() );
(or a.begin() and a.end() if you instead used a vector for 'a')

In JavaScript 1.8, arrays have methods called "reduce" (left fold) and "reduceRight" (right fold). The initial value is an optional second argument: 

  var sum = numbers.reduce(function(x,y){return x + y;});

In the not-yet standardized R<sup>6</sup>RS SchemeLanguage, there are functions called fold-left and fold-right: 

  (fold-left + 0 numbers)

RubyLanguage provides inject: 

  [1,2,3,4,5].inject(0) do |result, value|
    result + value
  end
  # 15
As of Ruby 1.8.7 (and upcoming versions like 1.9), reduce is a valid name for this method as well.

In PhpLanguage there is a left fold function: 

  array_reduce(array(1,2,3,4), function($x, $y) { return $x + $y; })
You can also give it an initial argument: 

  array_reduce(array(1,2,3,4), function($x, $y) { return $x + $y; }, 0)
When the initial value is not given, it assumes an initial value of NULL; instead of what it does in other languages, which is use the first element as the initial value and fold on the rest of the list. This works okay on addition, as above, because NULL gets treated as 0 when used in arithmetic. But it won't work for, say, multiplication (you would have to use an explicit initial value of 1), or anything else, unless you make a function specifically check for NULL, and have it use the initial value instead.

Prior to PHP 5.3, the initial value must be an integer. So you couldn't use it to accumulate a string or list or something like that. So you were stuck with an initial value of either an integer, or NULL, which was not very useful.

(Above example updated 2010-08-30 to use new anonymous function syntax in PHP 5.3)

SwiftLanguage provides reduce: 

  [1,2,3,4,5].reduce(0) {$0 + $1} // 15

FoldFunction is the fundamental iterator. All other InternalIterators can be built from FoldFunction.

But surely FoldFunction can be built from other iterators, as well. Why is it so fundamental? -- DanielKnapp, CommonLisp advocate who still doesn't understand most of the statements of SmugLispWeenies.

Well fold combines the elements it ranges over in an arbitrary way. Therefore it is fundamental. Try defining map and reduce in terms of fold. Now do the reverse.

Another way to explain it is that foldr makes an expression where the fundamental constructors of a list are replaced with arbitrary operations - cons with f, nil with initval. i.e. 

 foldr (foo : (bar : (baz : []))) f initval ==
    foo `f` (bar `f` (baz `f` initval))
As such, foldr is the simplest operation from which every other operation on lists can be made. As a consequence, a function (foldr list) actually is a feasible representation for the list. (You need not understand this last statement.)

Similarly, for a binary tree, there is a general operation "reducetree" which maps every tree constructor to some operation: 

 data Tree a =
   | Branch (Tree a, a, Tree a)
   | Leaf


 reducetree f leafval (Branch (left, val, right)) =
   f (reducetree f leafval left) val (reducetree f leafval right)
 reducetree f leafval Leaf = leafval
Or, for a tree that only has data in leaves: 

 data Tree a =
   | Branch (Tree a, Tree a)
   | Leaf a


 reducetree f g (Branch (left, right)) =
   f (reducetree f g left) (reducetree f g right)
 reducetree f g (Leaf v) = g v
I hope you can easily see the correspondence between the constructors and the "reduce" operation. -- PanuKalliokoski

Why is fold called reduce in some languages? This seems counter intuitive to me. inject makes the most sense to me, but I can live with fold. Does anyone know the rationale behind reduce? TIA -- RobertDiFalco

It is called reduce because you are reducing a collection to a single element. The only language that I know that calls it inject is Smalltalk, where it is called inject:into:. What other languages call this inject?

I've never heard any other call it inject. [RubyLanguage does, following SmallTalk]. However, it seems more intuitive. Are you saying in most implementations they actually remove all the elements so that there is only one left? That seems odd. I guess in that case it should be called reduce instead of inject or accumulate -- RobertDiFalco

In most languages fold reduces a collection to a single value, leaving the original collection unchanged. The final result is returned to the caller, rather than inserted into another collection.

It's not that reduce reduces a collection by making it smaller (e.g., array of integer to single integer); it's that it reduces a collection to a single return value, which may itself be another collection. A couple RubyLanguage examples of using reduce/inject/fold to build a Hash or Array: 

 histogram = scores.inject(Hash.new(0)) { |h, score| h[score] += 1 ; h }
 # and
 (0...25).inject([]) { |a, n| a << n**2 if (n % 3).zero? ; a }  # ListComprehension
You need to watch out in Ruby, though, in that it's easy to forget to return the collection at the end of the block.

fold is called the ListCatamorphism? in CategoryTheory.

Inject is positively strange to me. It's name, I think, derives from the medical practice, where you use a needle to deposit chemicals into living tissue. Likewise, "injection" of a function into a sequence kinda sorta surgically places operators or functions in between sequence items. The analogy is quite a stretch for me, though.

I never would consider "inject" for the name. Fold is just as bizarre to me -- what does folding have to do with the reduction of a sequence? To me, fold is a geometric operation (fold along like AB), not an arithmetic operation.

Reduce makes more sense; for starters, it's the name you use since gradeschool (people do still learn arithmetic in gradeschool, right?) -- I can't tell you how many times I've been given problems like, "Using addition, reduce 1, 3, 5, 7, and 9," or, "Is 120 a reduction of the sequence of integers 1, 2, 3, 4, and 5, and if so, with what operator?"

IokeLanguage calls this operation fold, reduce AND inject! (They're all defined by the same macro.)

CategoryFunctionalProgramming CategoryInManyProgrammingLanguages CategoryObjectFunctionalPatterns

EditText of this page (last edited June 15, 2014) or FindPage with title or text search