unfold variant

_unfold.js

//------------------------------------------------------------------------------
// A variant of my standard `unfold`, which allows us to use the entire list of
// previous values in calculating the next one.

const _unfold = (fn, init) =>
  fn (init, (x) => _unfold (fn, [...init, x]), () => init)


// My usual version looks like this:
//
//       const unfold = (fn, init, res = []) =>
//           fn (init, (x, s) => unfold (fn, s, [... res, x]), () => res)
//


//------------------------------------------------------------------------------

// First `n` Fibonacci numbers,
// 
// It's not really necessary to use this version, since we could just pass along
// `[penultimate, final]` final values as the next seed.  But it shows how it works.

const nFibs = (n) => _unfold (
  (xs, next, done) => xs .length < n ? next (xs .at (-1) + xs .at (-2)) : done (),
  [0, 1]
)

console .log (nFibs (15))
//=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]


//------------------------------------------------------------------------------

// Number of 1's in the binary representation of `n`, for `0 ... n`
//
// note that f (2 * n) == f (n)  && f (2 * n + 1) == f (n) + 1 

const oneBits = (n) => _unfold (
  (xs, next, done) => xs .length < n ? next (xs .length % 2 + xs [xs .length >> 1]) : done(),
  [0]
)

console .log (oneBits (20))
//=> [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3]


//------------------------------------------------------------------------------

// Number of legal format of `k` pairs of parentheses for `k` in `0 ... n`
//
// Calculates the nth entry by noting that some number of previous pairs (`0 ... (n - 1)`)
// must be included inside the first open parenthesis, and the remainder must come after
// it, so for each `i` less than `n`, we take the cartesian prodcut of `xss [i]` and
// `xss [n -i - 1]`, and pair them up with the entry of the first group included in the
// initial parentheses pair and the remainder following it

const parens = (n) => _unfold (
  (xss, next, done) => xss .length <= n 
    ? next (xss .flatMap ((xs, i, _, ys = xss [xss .length - i - 1]) => 
        xs .flatMap ((x) => ys .map ((y) => `(${x})${y}`))
      ))
    : done (),
  [['']]
)

console .log (parens (4))
//=> [
//     [""],
//     ["()"],
//     ["()()", "(())"],
//     ["()()()", "()(())", "(())()", "(()())", "((()))"],
//     [
//       "()()()()", "()()(())", "()(())()", "()(()())", "()((()))", "(())()()", "(())(())", 
//       "(()())()", "((()))()" ,"(()()())", "(()(()))", "((())())", "((()()))", "(((())))"
//     ]
//   ]

//------------------------------------------------------------------------------

// Also note the possibility of abstracting the `take (n)` portions of these examples.
// This could be a useful gloss, simplifying the custom functions further

const _unfold = (fn, init) =>
  fn (init, (x) => _unfold (fn, [...init, x]), () => init)

const unfoldN = (fn, init) => (n) => _unfold (
  (xs, next, done) => xs .length < n ? next (fn (xs)) : done (),
  init
)

const oneBits = unfoldN (
  (xs) => xs .length % 2 + xs [xs .length >> 1], 
  [0]
)

console .log (oneBits (20))
//=> [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3]

//------------------------------------------------------------------------------