CODEWITHSUNDEEP
recursionschemetail-recursionfoldfoldleft
Sandpoki
Sandpoki

Reputation: 35

How to make this Scheme function not tail recursive?

I can't figure out how can I make this tail recursive Scheme function not tail recursive anymore. Anyone can help me?

(define (foldrecl f x u)
  (if (null? x)
      u 
      (foldrecl f (cdr x) (f (car x) u))))

Upvotes: 0

Views: 189

Answers (3)

Sylwester
Sylwester

Reputation: 48745

left folds are inheritly iterative, but you can easily make them recursive by adding a continuation. eg. 

(let ((value expresion-that-calculates))
  value)

So in your case:

(define (foldrecl f x u)
  (if (null? x)
      u 
      (let ((result (foldrecl f (cdr x) (f (car x) u))))
        result)))

While this looks promising it does not guarantee that a smart Scheme implementation figures out that result is just returned and make it a tail call instead. Right folds are easier since they are inherently recursive:

(define (fold-right proc tail lst)
  (if (null? lst)
      tail
      (proc (car lst)
            (fold-right proc tail (cdr lst)))))

Here you clearly see the recursive part needs to become a argument to cons and thus never in tail position unless it is the base case.

Also notice it's slightly simpler to see what arguments goes where when the procedure is called proc, the tail of the result tail and the list argument lst. You don't even need to read my code to know how to use it, but yours I have no idea what x and u and ti doesn't help that the argument order doesn't follow any fold implementations known in Scheme.

Upvotes: 1

Will Ness
Will Ness

Reputation: 71070

Instead of doing, compose a plan for doing it; only in the end, do:

(define (foldreclr f xs a)
  (define (go xs)
     (if (null? xs) 
        (lambda (a) a)
        (let ((r (go (cdr xs))))    ; first, recursive call;
           (lambda                  ; afterwards, return a plan:
                  (a)               ;    given an a, to
             (r                     ;    perform the plan for (cdr xs)
               (f (car xs) a))))))  ;    AFTER processing (car x) and a.
  ((go xs)                          ; when the overall plan is ready,
           a))                      ;    use it with the supplied value

The internal function go follows the right fold pattern. It makes the recursive call first, and only afterwards it composes and returns a value, the plan to first combine the list's head element with the accumulator value, and then perform the plan for the list's tail -- just like the original foldrecl would do.

When the whole list is turned into a plan of action, that action is finally performed to transform the supplied initial accumulator value -- performing the same calculation as the original foldrecl left fold.

This is known as leaning so far right you come back left again.(*)

> (foldreclr - (list 1 2 3 4) 0)   ; 4-(3-(2-(1-0)))
2
> (foldreclr - (list 4 3 2 1) 0)   ; 1-(2-(3-(4-0)))
-2

See also:

(sorry, these are in Haskell, but Haskell is a Lisp too.)

Upvotes: 0

river
river

Reputation: 1028

The recursive call is in tail position, so put it inside another procedure call like this:

(define (identity x) x)

(define (foldrecl f x u)
  (if (null? x)
      u 
      (identity (foldrecl f (cdr x) (f (car x) u)))))

now the recursive call is not in tail position, it is not tail recursive anymore.

A compiler is allowed to optimize away the identity function if it knows that it does nothing but hopefully it wont.

Upvotes: 1

Related Questions