List Traversal in a lazy setting that produces expressions in WHNF

Question

I simulate lazy evaluation, i.e. evaluate only when needed and only once, in JS with Proxy and run into a problem with Traversable (mapA instead of traverse at the term level):

const r = List.mapA({map: Opt.map, ap: Opt.ap, of: Opt.of})
  (x => (x & 1) === 0 ? null : x)
    (List.fromArr([1,3,5]));

Opt.map(Arr.fromList) (r); // yields [1,3,5]

Please note that Opt isn't an ADT but based on null. This works as expected: r is a thunk. Arr.fromList is strict and eventually forces evaluation of r. The problem arises when I trigger short circuiting, i.e. pass List.fromArr([1,2,3]) to List.mapA. When Opt.map forces the evaluation of the outermost List layer it yields the first elem 1 and the tail of the list, which is an unevaluated thunk again. Hence Opt.map assumes continuous computation and applies r to Arr.fromList, which in turn forces the evaluation of the entire List. 2 causes the short circuiting but not within Opt.map but within List.fromArr. Hence an error is thrown.

The problem is that due to lazy evaluation the transformation of r from List to null is deferred and thus not handled by the Opt functor anymore but by the pure functon invoked by it. How does a lazy language like Haskell tackle this issue? Or am I making a mistake in between?

Unfortunately, I cannot provide a running example because it would include a huge amount of library code. Here are implementations of the core functions, in case someone is interested:

List.mapA = ({map, ap, of}) => {
  const liftA2_ = liftA2({map, ap}) (List.Cons);
  return f => List.foldr(x => acc =>liftA2_(f(x)) (acc)) (of(List.Nil));
};

const liftA2 = ({map, ap}) => f => tx => ty => ap(map(f) (tx)) (ty);

List.foldr = f => acc => function go(tx) { // guarded rec if `f` non-strict in 2nd arg
  return tx.run({
    nil: acc,
    cons: y => ty => f(y) (lazy(() => go(ty)))
//                         ^^^^^^^^^^^^^^^^^^ thunk
  });
};

---

[EDIT]

Here is a more detailed description of the computation. A thunk is not just the usual nullary function () => .. but guarded by a Proxy, so that it can be used as a placeholder for any expression in most cases.

Constructing r

1. List.fromArr creates a List {head: 1, tail} with the tail fully evaluated
2. List.mapA applies the head 1 to its f, which yields 1 and the overall op in turn returns {head: 1, tail: thunk}, i.e. the tail is a thunk (since 1 is odd there is no short circuiting)
3. The evaluation stops because List.foldr, of which List.mapA is derived of, is non-strict in the tail
4. r evaluated to {head: 1, tail: thunk}, i.e. an expression that contains a thunk and is now in weak head normal form (WHNF) (and isn't a thunk itself as I claimed in my original question)
5. please note that there is no Opt layer because optional values are encoded using null, not as an ADT

Convert the traversed list back to Array again

1. Lifting the strict Arr.fromList with Opt.map is necessary because r may be null
2. Opt.map inspects the outermost layer of the list in WHNF r, so no further evaluation takes place at this point since the expression is already in WHNF
3. it detects a List, which is equivalent to Just [a], and invokes the pure function Arr.fromList to further process r
4. Arr.fromList is strict, i.e. it recursively evaluates the tail until the base case is hit
5. during the second recursion it evaluates the tail, which is a thunk, to {head: f(2), tail: thunk}, where f is the one from List.mapA
6. f(2) evaluates to null and short circuits the original list traversal
7. Arr.fromList expects another list layer, not null and throws an error

I have a hunch that List.mapA must be strict in its list argument. I could easily do it, because there is a strict version of foldr based on tail recursion modulo cons. However, I doesn't understand the underlying principle when to make an operation strict. If list traversals were strict, so would have to be monadic list chains. That would be a bummer.

Answer 1

When Opt.map forces the evaluation of the outermost List layer it yields the first elem 1 and the tail of the list, which is an unevaluated thunk again.

Something is wrong here. Opt.map does not force the evaluation of the List layer, all it does is to force the evaluation of the Opt layer and leave the rest to the mapping callback. (Or really, Opt.map would return a thunk for this operation, it wouldn't do this immediately).

If you do

const r = List.mapA(Opt)(x => x & 1 ? x : null)(List.fromArr([1,2,3]))

then r already is null (or a thunk for it, if you want). Calling

Opt.map(Arr.fromList)(r)

on this will never even call Arr.fromList, it will just forward null.

If this is not what is happening in your code, there either is a bug in your lazy thunk implementation or in your Opt (map, ap, of) implementation.

---

Re update:

1. List.fromArr creates a List {head: 1, tail} with the tail fully evaluated
2. List.mapA applies the head 1 to its f, which yields 1 and the overall op in turn returns {head: 1, tail: thunk}, i.e. the tail is a thunk (since 1 is odd there is no short circuiting)
3. The evaluation stops because List.foldr, of which List.mapA is derived of, is non-strict in the tail
4. r evaluated to {head: 1, tail: thunk}, i.e. an expression that contains a thunk and is now in weak head normal form (WHNF) (and isn't a thunk itself as I claimed in my original question)

No no no. This sounds like you are confusing List.mapA with List.map. mapA must run through the entire list to apply the applicative effects before returning a result (though of course, it may return a thunk for this instead, but evaluating that to WHNF must distinguish between Nothing (null) and Just, where the contents of Just may be lazy still).

It doesn't matter that foldR does not evaluate the tail itself but only passes a thunk to f, it is the responsibility of Opt.ap to look at that second argument to check whether the tail of the list evaluates to Nothing or a Just.

5. please note that there is no Opt layer because optional values are encoded using null, not as an ADT

The layer is still there, even if Just is not represented by a separate JS value. Notice that this might be the reason for causing all this trouble, since it makes it hard (impossible?) to distinguish thunk::Opt a (which may evaluate to null::Opt a) from (Just thunk)::Opt a. Are you going to just make Opt strict?

2. Opt.map inspects the outermost layer of the list in WHNF r, so no further evaluation takes place at this point since the expression is already in WHNF
3. it detects a List

Why should it do that? All that Opt.map needs to do is check whether the outermost layer is null or not. It shouldn't further evaluate Just contents that are not in WHNF.

I have a hunch that List.mapA must be strict in its list argument.

Yes, but this is not done by choosing a strict foldR variant. It is done by liftA2/ap forcing evaluation of the list tail.