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 list
    eg: ((((0 + 1) + 2) + 3) + 4) + 5
  • Fold right combines the first element with the result of recursively combining the rest of the list
    eg: 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

Related Functions

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

Summary

Image Credits

References and Resources

Welcome to the Fold

http://fold.codemiller.com

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