fold as a 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 recursion can give rise to errors (stack overflow). Something not true for pure functional programming languages such as Haskell, using the built-in lazy evaluation.

It is 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. Hutton shows that this is not only true for map and filter but also for many other functions, 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; foldl and foldr in Haskell, synonymous with reduce).

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 functions, only using reduce (and reduceRight) in JavaScript. Hutton uses Haskell in his text, I thought it would be interesting to use JavaScript, but also to expand the list of functions we can express by use of fold.

How does fold work?

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 behave very similiar to the JavaScript reduce. If we would have attached it to the prototype of Array, it would be almost identical in terms of behaviour.

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 ('data last').

/*
 * 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]));
});

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]);
    });
  });

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);
  });
});

some

test('#some', () => {
  const numbers = [3, 6, 9];
  const isNumberGreaterThan5 = (number) => number > 5;
  expect(
    some(numbers, isNumberGreaterThan5)
  ).toEqual(numbers.some(isNumberGreaterThan5));
});

function some(list, fn) {
  return list.reduce(
    (isSomeElementTrue, element) => (
      !isSomeElementTrue 
        ? fn(element) 
        : true
      ),
    false
  );
}

every

test('#every', () => {
  const numbers = [3, 6, 9];
  const isNumberGreaterThan5 = (number) => number > 5;
  expect(
    every(numbers, isNumberGreaterThan5)
  ).toEqual(numbers.every(isNumberGreaterThan5));
});

function every(list, fn) {
  return list.reduce(
    (isSomeElementTrue, element) => (
      isSomeElementTrue 
        ? fn(element) 
        : false
      ),
    true,
  );
}

find

test('#find', () => {
  const linuxCharacters = [{ name: 'Tux' }, { name: 'Nolok' }];
  const isCharacterNamedTux = (character) => character.name === 'Tux';
  expect(find(
    linuxCharacters,
    isCharacterNamedTux,
  )).toEqual(linuxCharacters.find(isCharacterNamedTux));
});

function find(list, fn) {
  return list.reduce(
    (firstFound, element) => (!firstFound && fn(element) ? element : firstFound)
  );
}

findIndex

test('#findIndex', () => {
  const linuxCharacters = [{ name: 'Tux' }, { name: 'Nolok' }];
  const isCharacterNamedTux = (character) => character.name === 'Tux';
  expect(findIndex(
    linuxCharacters,
    isCharacterNamedTux,
  )).toEqual(linuxCharacters.findIndex(isCharacterNamedTux));
});

function findIndex(list, fn) {
  return list.reduce(
    (firstFound, element, index) => (firstFound === -1 && fn(element) 
      ? index 
      : firstFound),
    -1
  );
}