Can a strict right fold be implemented in a single loop?

Question

A strict left fold is straightforward to implement as a loop, rather than with recursion:

foldl(fn, acc, list)
    loop until empty(list)
        acc ← fn(acc, head(list))
        list ← tail(list)

    return acc

For a strict right fold, the best I've been able to come up with is by maintaining a stack of partially applied functions, which gets unrolled at the end to evaluate the accumulator:

foldr(fn, acc, list)
    stack ← empty stack

    loop until empty(list)
        stack push λx ↦ fn(head(list), x)
        list ← tail(list)

    loop until empty(stack)
        acc ← (stack pop)(acc)

    return acc

The size of the stack, when full, will be the same size as the input list; so it has to iterate through twice. Moreover, a stack of partially applied functions is hardly different from the call stack that would be created when using recursion, so it doesn't really achieve much.

It is possible to implement a right fold using a left fold:

foldr(fn, acc, list)
    return foldl(λx,y ↦ fn(y, x), acc, reverse(list))

However, that reverse still implies a second iteration.

Is it possible to do better?

---

EDIT "Single loop" is a bit ambiguous. I suppose my question is: Can a strict right fold be implemented in $O(n)$ time and $O(1)$ space, without recursion, like a strict left fold can?

Answer 1

I believe I have come up with a solution, but I'm not convinced. We observe that, from foldr(fn, acc, list), we can rewrite the intermediary steps as a series of single-valued functions:

$$ \begin{align} eval_0 &: x \mapsto fn(list_0,x) \\ eval_1 &: x \mapsto eval_0(fn(list_1, x)) \\ \vdots \\ eval_n &: x \mapsto eval_{n-1}(fn(list_n, x)) \end{align} $$

Then, where $n$ is the length of $list$:

$$ foldr(fn, acc, list) = eval_n(acc) $$

For example:

$$ \begin{align} foldr((x,y)\mapsto x-y,0,[1,2,3]) &= eval_3(0) \\ &= eval_2(3-0) \\ &= eval_1(2-(3-0)) \\ &= 1-(2-(3-0))) \end{align} $$

So the loop algorithm looks something like:

foldr(fn, acc, list)
    eval ← λx ↦ x

    loop until empty(list)
        eval ← λx ↦ eval(fn(head(list), x))
        list ← tail(list)

    return eval(acc)

I say I'm "not convinced" as implementing this is tricky. The eval ← λx ↦ eval(...) line is self-referential: informally we know it means "eval becomes a function of the previous eval", but in reality this gets interpreted as infinite recursion. So you end up having to keep a stack in memory either way.

Answer 2

I think I have solved this! After reading more about it, it seems my hunch about trampolining -- see my comment from my previous answer -- is exactly what I want. So here's what we do:

1. Convert the recursive foldr into continuation-passing style.
2. Wrap each function evaluation into a thunk so no recursion actually happens; instead each invocation returns the next element in the sequence.
3. Write a trampoline function (just a loop) that unrolls this sequence to give the final result.

Recursive foldr:

foldr(fn, acc, list)
    match list
        empty     => return acc
        otherwise => return fn(head(list), foldr(fn, acc, tail(list))

Convert to CPS:

foldr'(fn, acc, list, k)
    match list
        empty     => return k(acc)
        otherwise => return foldr'(fn, acc, tail(list), λx ↦ k(fn(head(list), x)))

Wrap the function evaluation in thunks (argument-less lambda functions):

foldr'(fn, acc, list, k)
    match list
        empty     => return k(acc)
        otherwise => return λ ↦ foldr'(fn, acc, tail(list), λx ↦ λ ↦ k(fn(head(list), x)))

Write a trampolining function:

trampoline(f)
    loop while thunk(f)
        f ← f()
    return f

Stitch it all together:

foldr(fn, acc, list)
    return trampoline(foldr'(fn, acc, list, λx ↦ x))