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 combinators like this, because they are not stack safe:

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


const take = n => ([head, tail]) =>
  n === 0 ? []
    : head === undefined ? []
    : [head, take(n - 1) (tail)];


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

Now I tried to implement take tail recursively, so that I can either rely on TCO (still an unsettled Promise in Ecmascript) or use a trampoline (omitted in the example to keep things simple):

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


const safeTake = n => list => {
  const aux = (n, acc, [head, tail]) => n === 0 ? acc
    : head === undefined ? acc
    : aux(n - 1, [head, acc], tail);

  return aux(n, [], list);
};


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

This works but the new created list is in reverse order. How can I solve this issue in a purely functional manner?

  • Are you asking to implement the "tail call modulo cons" implementation explicitly? – Bergi May 12 at 14:14
  • The easiest solution would be the return reverse(aux(n, [], list)) from safeTake. – Bergi May 12 at 14:15
  • @Bergi I asked about an explicit TRMC on another question yesterday. – ftor May 12 at 14:25
  • @Bergi Personally I think the lack of TRMC is one of the biggest drawbacks of JS (not to mention TCO). But then again, I don't know any dynamic language that implements this optimization. – ftor May 12 at 14:28
  • JS doesn't have immutable linked lists anyway, so it hardly would need TRMC. I guess you really want to use PureScript instead :-) – Bergi May 12 at 14:30
up vote 2 down vote accepted

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:

const cons = (head, tail) => ({ head, tail });

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

const take = n => n === 0 ? xs => null : xs => xs && {
    head: xs.head,
    get tail() {
        delete this.tail;
        return this.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.

  • This is indeed very helpful! Is WHNF the underlying mechanism of what is sometimes referred to as guarded recursion in the Haskell community? I've been thinking guarded recursion would be a complex comppiler optimization. But now it seems it's essentially a side effect of lazyness. – ftor May 13 at 6:52
  • 2
    WHNF is not a mechanism. Laziness is the mechanism. One way to think about it is that if laziness is a verb then WHNF is a noun. An expression in WHNF is one which has possibly only been evaluated upto the outermost constructor. The fields of the constructor might not have been evaluated yet (due to laziness). Therefore, laziness allows for expressions to be in WHNF. In turn, WHNF enables guarded recursion via implicit trampolining. Hence, by transitivity laziness gives you guarded recursion for free. – Aadit M Shah May 13 at 19:10
  • Note however, that laziness is not required for guarded recursion. For example, you can have guarded recursion in strict languages like Scheme. In this case, guarded recursion (i.e. tail recursion modulo cons) is indeed a complex compiler optimization. – Aadit M Shah May 13 at 19:13

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

const None =
  Symbol ()

const identity = x =>
  x

const safeTake = (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

const None =
  Symbol ()

const identity = x =>
  x

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

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

const safeTake = (n = 0, xs = []) =>
{
  const aux = (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, [] ] ] ] 
  • I actually wanted to avoid continuations. You said one way... – ftor May 12 at 13:59
  • When I implement safeTake with loop/recur and apply it to a huge list I get a stack overflow at answer => cont ([ head, answer ]). Can you reproduce that? – ftor May 12 at 16:36
  • @ftor, I added a trampoline demo above. Remember the chainRec question? I think it would be possible to rewrite this using our stack-safe continuation monad or by using a stack-safe unfold – user633183 May 12 at 19:09
  • Hm, this also seems to cause a stack overflow: your example. Here is my shot from a few hours ago. I don't quite get it, but it seems as if the continuation winds up a real call stack as well. – ftor May 12 at 19:42
  • @ftor added call to all return paths of aux – here's verification that it works using a less clever test :D – user633183 May 13 at 5:39

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.