3

Take, for example, the following naive implementation of a right fold in Scheme:

(define (fold-rite kons knil clist)
  (if (null? clist)
    knil
    (kons (car clist) (fold-rite kons knil (cdr clist)))))

This is obviously not a candidate for tail call elimination since the recursive invocation of fold-rite has to complete before calling kons. Now, I might be a little clever and use continuation-passing style instead:

(define (fold-rite-cps kons knil clist kontinuation)
  (if (null? clist)
    (kontinuation knil)
    (fold-rite-cps kons knil (cdr clist) 
      (lambda (x) (kontinuation (kons (car clist) x))))))

Now fold-rite-cps is tail recursive, but the intermediate continuations built up during recursion will still have to be kept somewhere. So while I might not blow out the stack, I'm still using about as much memory as with the first version, and somehow I get the feeling that first collecting a massive pile of continuations and then unravelling them all in one fell swoop should be bad for performance, although the second version was actually measurably faster on my machine.

But if a left fold can run in constant space (minus the value being accumulated) and a right fold on a list is the same as a left fold on its reverse, then I imagine there should be a way to implement a tail-recursive right fold that can also run in constant space. If so, how would I do that? Getting even more general, what ways are there to make a non-tail recursive function into a tail-recursive one, preferably one that can run in constant space (assuming that an explicit loop can be written in an imperative language that also runs in constant space)? Have I made any wrong assumptions?

Although I've tagged Scheme and Lisp, I'm interested in solutions in any language; the approaches should apply to functional programs in general.

jaymmer - Reinstate Monica
  • 4,238
  • 4
  • 28
  • 34
  • 2
    "if a left fold can run in constant space (minus the value being accumulated) and a right fold on a list is the same as a left fold on its reverse, then I imagine there should be a way to implement a tail-recursive right fold that can also run in constant space." Will you be disappointed if it turns out to be "do the left fold on the reversed list" or some variant of it? – Joshua Taylor Mar 11 '15 at 12:21
  • A little :) I was wondering if it's possible without that extra step. Although it just occurred to me that it probably isn't since you can't do a right fold without traversing the list, somehow, at some point, so... I should have thought of this more. – jaymmer - Reinstate Monica Mar 11 '15 at 12:33
  • Yeah, the issue is that if you're trying to process the last element of the list, you have to get it at *some* point, and that's going to require a linear traversal. Then you need the second to last element of the list, and it seems like the best way to have that on hand is to have saved it somehow when you were traversing the list, either in a closure somewhere (when you do CPS) or on the stack (when you unwind the recursion). Note that folds on random access sequences (like arrays) don't have this problem; the right fold and the left fold perform in the same time and space. – Joshua Taylor Mar 11 '15 at 13:28
  • It's impossible doing this since the function is also the glue between this result and the result of the same process on the rest. It's much easier to make a tail recursive `map` with skip possibilities (using TRMC). When isn't `foldl`, `filter` and `map` enough? – Sylwester Mar 11 '15 at 18:53
  • 2
    It's possible to have tail-calls folding either left or right, but you have to implement your own doubly-linked lists and the respective iterator functions. Or just use vectors/arrays. Generally, if you can iterate without having to accumulate (in the iterator function itself, not in the accumulator function), and accumulate with a constant space accumulator (e.g. count, maximum, minimum, sum, pointer to last cons), you have a good tail-call candidate. If you cannot (e.g. iterating reverse singly-linked list, or accumulating median), you should still consider **not** using the call stack. – acelent Mar 12 '15 at 15:26
  • Would any of you mind posting your comments as answers? Given that my question wasn't that great to begin with, this discussion is probably as close to answering it as anyone could get. – jaymmer - Reinstate Monica Mar 12 '15 at 22:03
  • 1
    sometimes you can do https://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons. sometimes kons can be turned into associative `append` and so an accumulating version can be written. when all else fails, there's CPS, and the continuations can be reified - built as some data structure, not as actual lambdas - and then processed when all data is gathered (whole list is scanned through) (I vaguely remember Reynolds' https://en.wikipedia.org/wiki/Defunctionalization having something to do with that). Sometimes these data on heap can be simplified while being built. – Will Ness Mar 15 '15 at 22:27
  • 1
    see also https://stackoverflow.com/search?tab=newest&q=defunctionalization, esp. https://stackoverflow.com/questions/9323036/tail-recursive-function-to-find-depth-of-a-tree-in-ocaml. – Will Ness Mar 16 '15 at 00:11

1 Answers1

1

Based on the comments above, I think the best possible answer without changing data structures (cons cells) is going to be as follows (in common lisp, because that's what I had handy).

Due to the single linking structure of cons cells, in order to not accumulate space we will have to pretty much switch the order of the list then fold the reversed list. Reversing is a linear space operation and reducing could be constant space depending on the reduction function used.

(defun foldl (op clist &optional base)
  (if (null clist)
      base
      (foldl op (cdr clist)
             (funcall op (car clist) base))))

(defun foldr (op clist &optional base)
  ;; reverse the list then fold it
  (foldl op (foldl #'cons clist nil) base))

For a direct answer: No, it is not possible to foldr in constant space because the single linked nature of cons cells requires a full list traversal to reach the last element and then an unwinding step or a separate list to track the actual fold operation.

bobbysmith007
  • 326
  • 2
  • 9