Welcome to the Fold

Katie Miller (@codemiller)OpenShift Developer Advocate at Red Hat

0

+3

+1

+7

+13

+5

+11

+2

var list = [3, 1, 7, 13, 5, 11, 2];

var acc = 0;

for (var i = 0; i < list.length; i++) { 
  acc = acc + list[i];
}

console.log(acc); // 42

var sum = function (list) {
  var acc = 0;
  for (var i = 0; i < list.length; i++) {
    acc = acc + list[i];
  }
  return acc;
};
sum(list); // 42

var reverse = function (list) {
  var acc = [];
  for (var i = 0; i < list.length; i++) {
    acc = [list[i]].concat(acc);
  }
  return acc;
};
reverse(list); // [2, 11, 5, 13, 7, 1, 3]

var reverse = function (list) {
  var acc = [];
  for (var i = 0; i < list.length; i++) {
    acc = [list[i]].concat(acc);
  }
  return acc;
};
reverse(list); // [2, 11, 5, 13, 7, 1, 3]

var sum = function (acc, list) {
  if (list.length == 0) { return acc; }
  return sum(list.slice(1),
             acc + list[0]);
};

sum(list, 0); 
// 42

var reverse = function (acc, list) {
  if (list.length == 0) { return acc; }
  return reverse(list.slice(1),
                 [list[0]].concat(acc));
};

reverse(list, []); 
// [2, 11, 5, 13, 7, 1, 3]

var fold = function (func, acc, list) {
  for(var i = 0; i < list.length; i++) {
    acc = func(acc, list[i]);
  }
  return acc;
};

var fold = function (func, acc, list) {
  if (list.length == 0) { return acc; }
  return fold(func, func(acc, list[0]), 
              list.slice(1));
};

var sum = function (list) {
  return fold(function (acc, elem) { return acc + elem; }, 0, list);
};

var reverse = function (list) {
  return fold(function (acc, elem) { return [elem].concat(acc); }, [], list);
};

Higher-Order Function (HOF)

Map

var map = function (func, list) {
  return fold(function (acc, elem) {  
    return acc.concat([func(elem)]); 
  }, [], list);
};

map(function (elem) { return elem + 1; }, [1, 2, 3]); 
// [2, 3, 4]

Filter

var filter = function (pred, list) {
  return fold(function (acc, elem) {  
    return pred(elem) ? acc.concat([elem]) : acc; 
  }, [], list);
};

filter(function (elem) { return elem % 2 == 0; }, [1, 2, 3]); 
// [2]

Fold

aka Reduce, Compress, Inject, Accumulate, Aggregate

Applies a combining function to each element of a listrecursive data structure and a partial result to build a single value

Our Fold Function:

• Requires a starting value for the accumulator
• Is left associative (rather than right associative)
• Is strictly evaluated (as opposed to lazily)

Initial Accumulator Value

• Some folds use first element to be processed as starting value
• Only works for non-empty lists
• Means return value must be same type as list elements

Associativity

• Fold left combines the result of recursively combining all elements but the last one, with the last element in the listeg: ((((0 + 1) + 2) + 3) + 4) + 5
• Fold right combines the first element with the result of recursively combining the rest of the listeg: 1 + (2 + (3 + (4 + (5 + 0))))

Fold Left versus Right refers to associativity, not processing order

fold(function (func, elem) {
  return function (acc) {
    return func([elem].concat(acc));
  };
}, identity, [1, 2, 3])([]); // [1, 2, 3] 

var identity = function (value) { return value; };

Some view Fold Left as "the fundamental list iterator", and Fold Right as "the fundamental list recursion operator".

It can be useful to view Fold Right as a structural transformation on a list:

Where to Find Fold

• JavaScript 1.8: Array.prototype.reduce(callback[, initialValue]); Array.prototype.reduceRight(callback[, initialValue])
• JS libraries: FKit, fn.js, Functional JavaScript, functional.js, Lazy.js, Lo-Dash, Udon, Underscore.js, etc.
• Other languages: including Haskell, Scala, Clojure, Common Lisp, Ruby, Python, Java 8, C#, C++, and many others

Related Functions

• Scan functions return all the intermediate accumulator values
• Unfolds are used for constructing, rather than processing, recursive values

Summary

Image Credits

• David Hasselhoff (Georges Biard, CC-BY-SA-3.0)
• Open Clip Art Library
• Paper Dolls [Colorized, Cropped] (Chris Jones, CC BY-NC 2.0)

References and Resources

• Foldl.com and Foldr.com
• Functional JavaScript
• Haskell Wiki: Fold Overview, Foldr, Foldl, Foldl'
• Higher-Order Fun
• Learn You A Haskell
• Stack Overflow: Fold Left vs Fold Right, Foldl v Foldr on Infinite Lists
• Tutorial on the Universality and Expressiveness of Fold
• Wikipedia

Welcome to the Fold

http://fold.codemiller.com

Katie Miller (@codemiller)OpenShift Developer Advocate at Red Hat