How can I prevent a tail recursive function from reversing the order of a List?

Question

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 '18 at 14:14
The easiest solution would be the `return reverse(aux(n, [], list))` from `safeTake`. — Bergi, May 12 '18 at 14:15
@Bergi I asked about an explicit TRMC on [another question](https://stackoverflow.com/q/50288939/6445533) yesterday. — , May 12 '18 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. — , May 12 '18 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 '18 at 14:30
@Bergi I was hoping the interpreter would be smart enough to recognize when I use an array as a `List` type :D — , May 12 '18 at 14:32
@Bergi purescript? I rather explore how far I can bend Javascript towards functional style. — , May 12 '18 at 14:35

score 3 · Accepted Answer · answered May 12 '18 at 23:02

3

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:

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

Hope that helps.

answered May 12 '18 at 23:02

Aadit M Shah

72,912
30
168
299

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. – May 13 '18 at 06:52
3

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 '18 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 '18 at 19:13

Mulan · Answer 2 · 2018-05-13T05:41:41.707

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...

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, [] ] ] ]

edited May 13 '18 at 05:41

answered May 12 '18 at 13:36

Mulan

129,518
31
228
259

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? – May 12 '18 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` – Mulan May 12 '18 at 19:09
Hm, this also seems to cause a stack overflow: [your example](https://repl.it/repls/SlategrayFreshCamel). Here is [my shot](https://repl.it/repls/PrizeCandidOutlier) 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. – May 12 '18 at 19:42
@ftor added `call` to all return paths of `aux` – here's verification that [it works](https://repl.it/repls/VigilantRepentantExternalcommand) using a less clever test :D – Mulan May 13 '18 at 05:39
Thanks, I couldn't have fixed that. I suck at CPS. – May 13 '18 at 06:51

How can I prevent a tail recursive function from reversing the order of a List?

2 Answers2

Linked