# 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) {
return tail.length > 0
? fold(fn, result, tail)
}

// 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) {
return tail.length > 0
? f(tail, result)
}
}

// Jest test
describe('#fold2', () => {
test('[1, 2, 3, 4, 5] => 15',
() => {
const add2Numbers = (a, b) => a + b;
const numbers = [1, 2, 3 ,4, 5];
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;
});
});
``````

## 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';
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';
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
);
}
``````