Skip to content

Instantly share code, notes, and snippets.

@stefanmaric

stefanmaric/notes.md

Last active February 11, 2023 04:51
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save stefanmaric/1dfc01dd3985d5b423f22fcad7c58da2 to your computer and use it in GitHub Desktop.
Save stefanmaric/1dfc01dd3985d5b423f22fcad7c58da2 to your computer and use it in GitHub Desktop.
Download ZIP
CleverKek notes
Raw
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:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment