CleverKek notes

notes.md

y-combinator

const y = le => (f => f(f))(f => le(x => f(f)(x)))

fib func that would theoretically take advantage of TCO

'use strict'
const fib = (n, a = 1, b = 0) => n ? fib(n - 1, a + b, a) : b

Same fib func curried

'use strict'
const fib = n => (a = 1) => (b = 0) => n ? fib(n -1)(a + b)(a) : b

fib function applied with y-combinator

'use strict'

const y = le => (f => f(f))(f => le(x => f(f)(x)))

const fibo = y(fib => n => (a = 1) => (b = 0) => n ? fib(n -1)(a + b)(a) : b)

fibo(1337)()()

Trampoline

const trampoline = fn => (...args) => {
  let result = fn(...args)
  while (result instanceof Function) result = result()
  return result
}

fac and fib using trampoline which end up in Infinity

'use strict'

const y = le => (f => f(f))(f => le(x => f(f)(x)))

const trampoline = fn => (...args) => {
  let result = fn(...args)
  while (result instanceof Function) result = result()
  return result
}

const fac = n => trampoline(
  y(self => n => (acc = 1) => n ? () => self(n - 1)(acc * n) : acc)
)(n)

const fib = n => trampoline(
  y(self => n => (a = 1) => (b = 0) => n ? () => self(n - 1)(a + b)(a) : b)
)(n)

console.log(fib(7))
console.log(fac(7))

console.log(fib(16000))
console.log(fac(16000))

fac and fib using trampoline and big-integer

'use strict'

const int = require('big-integer')

const y = le => (f => f(f))(f => le(x => f(f)(x)))

const trampoline = fn => (...args) => {
  let result = fn(...args)
  while (result instanceof Function) result = result()
  return result
}

const fac = n => trampoline(
  y(self => n => (acc = int.one) => n.isZero() ? acc.toString() : () => self(n.minus(1))(acc.multiply(n)))
)(int(n))

const fib = n => trampoline(
  y(self => n => (a = int.one) => (b = int.zero) => n.isZero() ? b.toString() : () => self(n.minus(1))(a.add(b))(a))
)(int(n))

console.log(fib(7))
console.log(fac(7))

console.log(fib(16000))
console.log(fac(16000))

Sources:

• https://benignbemine.github.io/2015/07/19/es6-tail-calls/
• https://blog.mattbierner.com/tail-call-implementation-and-defunctionalization-in-javascript/
• https://eddmann.com/posts/recursive-functions-using-a-trampoline-in-javascript/
• https://en.wikipedia.org/wiki/Fixed-point_combinator#Fixed_point_combinators_in_lambda_calculus
• https://kangax.github.io/compat-table/es6/
• https://kestas.kuliukas.com/YCombinatorExplained/
• https://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/
• https://medium.com/developers-writing/fibonacci-sequence-algorithm-in-javascript-b253dc7e320e#.ktbdmmu4e
• https://medium.com/javascript-scene/7-surprising-things-i-learned-writing-a-fibonacci-generator-4886a5c87710#.l6p9r56hj
• https://medium.com/javascript-scene/the-hidden-power-of-es6-generators-observable-async-flow-control-cfa4c7f31435#.quew23nzu
• https://raganwald.com/2013/03/28/trampolines-in-javascript.html
• https://raganwald.com/2015/04/03/left-variadic.html
• https://sahandsaba.com/five-ways-to-calculate-fibonacci-numbers-with-python-code.html
• https://stackoverflow.com/questions/33923/what-is-tail-recursion#37010
• https://taylodl.wordpress.com/2015/08/09/functional-javascript-tail-call-optimization-and-babel/
• https://wizpert.com/wizdom/variadic-functions-in-javascript
• https://www.2ality.com/2014/04/call-stack-size.html
• https://www.datchley.name/recursion-tail-calls-and-trampolines/
• https://www.gregjs.com/javascript/2016/writing-a-fibonacci-implementation-in-javascript/
• https://www.sidhe.org/~dan/blog/archives/000211.html