How Can I Prevent A Tail Recursive Function From Reversing The Order Of A List?

I am experimenting with the functional List type and structural sharing. Since Javascript doesn't have a Tail Recursive Modulo Cons optimization, we can't just write List combinato

Solution 1:

Laziness gives you tail recursion modulo cons for free. Hence, the obvious solution is to use thunks. However, we don't just want any kind of thunk. We want a thunk for an expression in weak head normal form. In JavaScript, we can implement this using lazy getters as follows:

constcons = (head, tail) => ({ head, tail });

const list = cons(1, cons(2, cons(3, cons(4, cons(5, null)))));

consttake = n => n === 0 ? xs =>null : xs => xs && {
    head: xs.head,
    gettail() {
        deletethis.tail;
        returnthis.tail = take(n - 1)(xs.tail);
    }
};

console.log(take(3)(list));

There are lots of advantages to using lazy getters:

1. Normal properties and lazy properties are used in the same way.
2. You can use it to create infinite data structures.
3. You don't have to worry about blowing up the stack.

Hope that helps.

Solution 2:

One way to prevent the list from reversing is to use continuation passing style. Now just put it on a trampoline of your choice...

constNone =
  Symbol ()

constidentity = x =>
  x

constsafeTake = (n, [ head = None, tail ], cont = identity) =>
  head === None || n === 0
    ? cont ([])
    : safeTake (n - 1, tail, answer => cont ([ head, answer ]))

const list =
  [ 1, [ 2, [ 3, [ 4, [ 5, [] ] ] ] ] ]

console.log (safeTake (3, list))
// [ 1, [ 2, [ 3, [] ] ] ] 

Here it is on a trampoline

constNone =
  Symbol ()

constidentity = x =>
  x

constcall = (f, ...values) =>
  ({ tag: call, f, values })

consttrampoline = acc =>
{
  while (acc && acc.tag === call)
    acc = acc.f (...acc.values)
  return acc
}

constsafeTake = (n = 0, xs = []) =>
{
  constaux = (n, [ head = None, tail ], cont) =>
    head === None || n === 0
      ? call (cont, [])
      : call (aux, n - 1, tail, answer =>
          call (cont, [ head, answer ]))
  return trampoline (aux (n, xs, identity))
}

const list =
  [ 1, [ 2, [ 3, [ 4, [ 5, [] ] ] ] ] ]

console.log (safeTake (3, list))
// [ 1, [ 2, [ 3, [] ] ] ]