Skip to content

Instantly share code, notes, and snippets.

@bijoythomas
Last active March 18, 2020 20:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bijoythomas/276b849fe39b2f32b4a6969f778685c9 to your computer and use it in GitHub Desktop.
Save bijoythomas/276b849fe39b2f32b4a6969f778685c9 to your computer and use it in GitHub Desktop.
Trampolining TCO functions in JS examples
/*
* aperture function modelled after https://ramdajs.com/docs/#aperture
*/
const head = xs => xs[0]
const last = xs => xs[xs.length - 1]
const tail = xs => xs.slice(1)
const isEmpty = xs => xs.length == 0
/* A recursive aperture implementation
*
*
* Usage examples:
* recursive_aperture([1,2,3,4,5,6,7,8,9], 4)
* => [ [ 1, 2, 3, 4 ], [ 2, 3, 4, 5 ], [ 3, 4, 5, 6 ], [ 4, 5, 6, 7 ], [ 5, 6, 7, 8 ], [ 6, 7, 8, 9 ] ]
* recursive_aperture([1,2,3,4,5,6,7,8,9], 3)
* => [ [ 1, 2, 3 ], [ 2, 3, 4 ], [ 3, 4, 5 ], [ 4, 5, 6 ], [ 5, 6, 7 ], [ 6, 7, 8 ], [ 7, 8, 9 ] ]
*
*/
function recursive_aperture(seq, n, acc=[]) {
if (isEmpty(seq)) {
return acc
}
if (isEmpty(acc)) {
return recursive_aperture(seq.slice(n), n, [seq.slice(0, n)])
}
rem = last(acc).slice(1)
acc = acc.concat([rem.concat([head(seq)])])
return recursive_aperture(tail(seq), n, acc)
}
/*
* A function that trampolines between its function argument based on returned result
*/
function trampoline(fn) {
return function(...args) {
let nextArgs = args
while (true) {
let result = fn.apply(this, nextArgs)
proceed = result[0]
nextArgs = result[1]
if (!proceed) {
return nextArgs
}
}
}
}
/*
* The aperture function re-written to use the trampoline
*
* Examples:
* trampoline(aperture)([1,2,3,4,5,6,7,8,9], 2)
* => [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 4, 5 ], [ 5, 6 ], [ 6, 7 ], [ 7, 8 ], [ 8, 9 ] ]
* trampoline(aperture)([1,2,3,4,5,6,7,8,9], 4)
* => [ [ 1, 2, 3, 4 ], [ 2, 3, 4, 5 ], [ 3, 4, 5, 6 ], [ 4, 5, 6, 7 ], [ 5, 6, 7, 8 ], [ 6, 7, 8, 9 ] ]
*/
function aperture(seq, n, acc=[]) {
if (isEmpty(seq)) {
return [false, acc]
}
if (isEmpty(acc)) {
return [true, [seq.slice(n), n, [seq.slice(0, n)]]]
}
rem = last(acc).slice(1)
acc = acc.concat([rem.concat([head(seq)])])
return [true, [tail(seq), n, acc]]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment