fold as universal form

Recursion and imperative solutions can express the same computations. To some extent, what solution you choose is a matter of taste in many languages. However, if we express our abstractions using a multi-paradigm language such as JavaScript or Python usually recursion comes with issues (stack overflow). Something not true for pure functional programming languages such as Scheme or Haskell (they are implemented in other ways).

If the solution to the problem involves many recursive calls, we should not use recursion in JavaScript and Python. Python even has a limit (999) for how many calls to other frames that are possible. If you exceed this limit an error is thrown. In both languages, there are patterns that can be used to delay issues.

The advantage (if any) with multi-paradigm languages is that we can use the abstraction and paradigm that fits us best, at least for most cases. Sometimes recursion makes our code more readable, sometimes recursion makes our code impossible to read.

After ES5 (but more so after ES6 and fat arrows) map, filter and reduce seems to increase in use. It is often said that reduce is a superfunction that can replace map and filter, and I want to reflect on this by recapitulating a point from a text by Graham Hutton, who shows that this is not only true for map and filter but also for many other functions that can be given a simple recursive pattern.

The main purpose of Hutton's text is not to hint on what functions that we can express by use of reduce (in Hutton's text called fold, which together with foldr are synonymous with reduce and more used in functional programming languages).

Hutton makes two important points.

Firstly, any recursive solution using reduce in most cases doesn't need inductive proofs since they use the same form. (We would still need to prove the function used in the recursion of fold.)

Secondly, in a language supporting function as first-class values and tuples (arrays in JavaScript), fold can find surprisingly many expressions and used in a wide variety of contexts.

We will give simple, but fully functional implementations of commonly known function, only using reduce (and reduceRight) in JavaScript. Hutton uses Haskell in his text, I thought it would be fun to use JavaScript but also to expand the list of functions we can express by use of fold because of its universal form. The list could be longer.

Two implementations of fold

Each call to fold uses the classic pattern of car and cdr of Lisp, separating the head from its tail. As long as the tail contains list members, we recursively call fold. The initial value and head are passed as arguments to the passed function producing a new initial value. We also append the tail. If there is no tail, we return from fold with a final call to the passed function.

The first version is behave very similiar to the JavaScript reduce. If we would have attached it to the prototype of Array, it would be almost identical.

function fold(fn, initial, v) {
  const [head, ...tail] = v;
  const result = fn(initial, head);
  return tail.length > 0
    ? fold(fn, result, tail)
    : fn(initial, head);
}

// Jest test
describe('#fold', () => {
  test('[1, 2, 3, 4, 5] => 15', 
    () => {
      const add2Numbers = (a, b) => a + b;
      const numbers = [1, 2, 3 ,4, 5];
      const sumOfNumbers = fold(add2Numbers, 0, numbers);
      expect(sumOfNumbers).toEqual(15);
    });
});

This version behaves slightly different from the reduce of Javascript, since we feed the data in a second, separate call.

/*
 * fold2
 */
function fold2(fn) {
  return function f(acc, v) {
    const [head, ...tail] = acc;
    const result = fn(v, head);
    return tail.length > 0
      ? f(tail, result)
      : fn(v, head);
  }
}

// Jest test
describe('#fold2', () => {
  test('[1, 2, 3, 4, 5] => 15', 
    () => {
      const add2Numbers = (a, b) => a + b;
      const numbers = [1, 2, 3 ,4, 5];
      const sumNumbers = fold2(add2Numbers);
      expect(sumNumbers(numbers, 0)).toEqual(15);
    });
});

len

const len = (list) => list.reduce(
  (listLength) => listLength + 1,
  0
);

// Jest test
describe('#len', () => {
  test('[] => 0', 
    () => expect(len([])).toEqual(0));

  test('[1, 2, 3] => 3', 
    () => expect(len([1, 2, 3])).toEqual(3));
});

reverse

const reverse = (list) => list.reduce(
  (acc, v) => [v, ...acc],
  []
);

// Jest test
describe('#reverse', () => {
  test('[] => []', 
    () => expect(reverse([])).toEqual([]));

  test('[1, 2, 3] => [3, 2, 1]', 
    () => expect(reverse([1, 2, 3])).toEqual([3, 2, 1]));

  test(`['A', 'B', 'C'] => ['C', 'B', 'A']`, 
    () => expect(reverse(['A', 'B', 'C'])).toEqual(['C', 'B', 'A']));
});

zip

const zip = (list1, list2) => list1.reduce(
  (acc, v, i) => [...acc, [v, list2[i]]],
  []
);

// Jest test
describe('#zip', () => {
  test(`[1, 2, 3], ['A', 'B', 'C'] => [[1, 'A'], [2, 'B'], [3, 'C']]`, 
    () => expect(zip([1, 2, 3], ['A', 'B', 'C'])).toEqual([[1, 'A'], [2, 'B'], [3, 'C']]));
});

map

const map = (fn, list) => list.reduce(
  (acc, x, i, arr) => [...acc, fn(x, i, arr)],
  []
);

// Jest test
describe('#map', () => {
  test('[] => []', 
    () => expect(map((x) => x + 1, [])).toEqual([]));

  test('[1, 2, 3] => [2, 3, 4]', 
    () => {
      const add1 = (x) => x + 1;
      const add1ToList = map(add1, [1, 2, 3]);
      expect(add1ToList).toEqual([2, 3, 4]);
    });

  test('[1, 2, 3, 4] => [1, 2, 4, 4]', 
    () => {
      const add1ToEvenIndex = (x, i) => i % 2 === 0
        ? x + 1
        : x;
      const add1ToEvenIndexToList = map(add1ToEvenIndex, [1, 2, 3, 4]);
      expect(add1ToEvenIndexToList).toEqual([2, 2, 4, 4]);
    });

  test('Make object names uppercase',
    () => {
      const upperCaseCharacterName = (character) => ({
        ...character,
        name: character.name.toUpperCase()
      });
      const listOfCharactersInLOTR = [
        { name: 'Gandalf' },
        { name: 'Eowyn'   }
      ];
      const allNamesUpperCase = map(
        upperCaseCharacterName,
        listOfCharactersInLOTR
      );
      expect(allNamesUpperCase).toEqual([
        { name: 'GANDALF' },
        { name: 'EOWYN'   }
      ]);
  });

filter

const filter = (fn, list) => list.reduce(
  (acc, x, i, arr) => fn(x, i, arr)
    ? [...acc, x]
    : [...acc],
  []
);

// Jest test
describe('#filter', () => {
  test('[] => []', 
    () => expect(filter((x) => x !== 1, [])).toEqual([]));

  test('[1, 2, 3, 4, 5] => [2, 4]', 
    () => {
      const isEven = (x) => x % 2 === 0;
      expect(filter(isEven, [1, 2, 3, 4, 5])).toEqual([2, 4]);
    });
});

compose

function compose(...fns) {
  return (initial) => fns.reduceRight(
    (a, b) => b(a),
    initial);
}

// Jest test
describe('#compose', () => {
  test('compose data: right -> left', 
    () => {
      addA = (s) => s + 'A';
      addB = (s) => s + 'B';
      const result = compose(addA, addB)('');
      expect(result).toEqual('BA');

    });
});

pipe

function pipe(...fns) {
  return (initial) => fns.reduce(
    (a, b) => b(a),
    initial);
}

// Jest test
describe('#pipe', () => {
  test('pipe data: left -> right', 
    () => {
      addA = (s) => s + 'A';
      addB = (s) => s + 'B';
      const result = pipe(addA, addB)('');
      expect(result).toEqual('AB');
    });
});

includes

function includes(list, pattern) {
  const regExPattern = new RegExp(pattern);
  return list.reduce((isFound, v) => {
    return regExPattern.test(v)
      ? true
      : isFound;
  }, 
  false
  );
}

// Jest test
describe('#includes', () => {
  test('[1, 2, 3] includes 1 => true', 
    () => {
      expect(includes([1, 2, 3], 1)).toEqual(true);
  });

  test('[1, 2, 3] includes 4 => false', 
    () => {
      expect(includes([1, 2, 3], 4)).toEqual(false);
  });
});

join

function join(list, delimiter='') {
  return list.reduce(
    (acc, v) => `${acc}${delimiter}${v}`,
    ''
  );
}

// Jest test
describe('#join', () => {
  test(`['Hello', ' world', '!'] => 'Hello world!`, 
    () => {
      expect(join(['Hello', ' world', '!'])).toEqual('Hello world!');
  });

  test('[1, 2, 3] includes 4 => false', 
    () => {
      expect(includes([1, 2, 3], 4)).toEqual(false);
  });
});

You can visit my project at GitHub.