tail-call-optimisation-utilities.js

/* --------------------------------------------------------------------------- *
        Recursive list utilities, taking advantage of Tail Call Elimination
* --------------------------------------------------------------------------- */

// Tail call elimination is a technique used by modern browsers to optimize recursive
// functions. It's not yet implemented in every browsers but part of the ES6 specs.
// Basically, the browser gets rid of the call stack while a recursive function
// is still being executed.

// To make it possible for browsers to optimize such functions, we have to directly
// return the function's result, without doing any other operation on it.

// For more information, read the excellent "Functional Programming in Elm" article
// https://evancz.gitbooks.io/functional-programming-in-elm/recursion/tail-call-elimination.html

// head :: [a] -> a
export const head = ([x]) => x

// tail :: [a] -> [a]
export const tail = ([x, ...rest]) => rest

// last :: [a] -> a
export const last = xs => xs[xs.length - 1]

// drop :: number -> [a] -> [a]
export const drop = (n, xs) =>
  n
    ? drop(n - 1, tail(xs))
    : xs

// take :: number -> [a] -> Optional [a] -> [a]
export const take = (n, [x, ...rest], output = []) =>
  n
    ? take(n - 1, rest, [...output, x])
    : output

// reverse :: [a] -> Optional [a] -> [a]
export const reverse = ([x, ...rest], output = []) =>
  rest.length
    ? reverse(rest, [x, ...output])
    : [x, ...output]

// map :: (a -> b) -> [a] -> Optional [b] -> [b]
export const map = (f, [x, ...rest], output = []) =>
  rest.length
    ? map(f, rest, [...output, f(x)])
    : [...output, f(x)]

// filter :: (a -> Bool) -> [a] -> Optional [a] -> [a]
export const filter = (f, [x, ...rest], output = []) =>
  rest.length
    ? filter(f, rest, f(x) ? [...output, x] : output)
    : f(x) ? [...output, x] : output

// reduce :: (b -> a -> b) -> [a] -> b -> Optional [a] -> b
export const reduce = (f, acc, [x, ...rest]) =>
  rest.length
    ? reduce(f, f(acc, x), rest)
    : f(acc, x)

// reduceRight :: (b -> a -> b) -> [a] -> b -> Optional [a] -> b
export const reduceRight = (f, acc, xs) =>
  reduce(f, acc, reverse(xs))

// range :: number -> number -> Optional [number] -> [number]
export const range = (start, end, xs = []) =>
  start > end
    ? xs
    : range(start + 1, end, [...xs, start])

// fact :: number -> Optional number -> number
export const fact = (x, output = 1) =>
  x
    ? fact(x - 1, x * output)
    : output

// compose :: (..., (c -> d), (b -> c), (a -> b)) -> a -> d
export const compose = (...funcs) =>
  x => reduceRight((acc, f) => f(acc), x, funcs)

// pipe :: ((a -> b), (b -> c), (c -> d), ...) -> a -> d
export const pipe = (...funcs) =>
  x => reduce((acc, f) => f(acc), x, funcs)