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?