CODEWITHSUNDEEP
recursionfunctional-programmingschemelispcommon-lisp
jaymmer - Reinstate Monica
jaymmer - Reinstate Monica

Reputation: 4328

How to achieve tail recursion in functional programs

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.

Upvotes: 3

Views: 265

Answers (1)

bobbysmith007
bobbysmith007

Reputation: 371

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.

Upvotes: 1

Related Questions