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

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

foldl(fn, acc, list)
loop until empty(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?

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.

• I feel like "trampolining" might be what I'm missing, but I'm only vaguely aware of the term and its association to problems such as these. I don't know if it's appropriate, or how to implement it... Jul 15, 2022 at 11:45

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