1
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$ Commented Jul 15, 2022 at 11:45
0
$\begingroup$

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))
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.