Converting a function with two recursive calls in scheme to make it tail-recursive

Question

Before I start: YES, this is a homework from college. Before I get told that I'm lazy and evil: this part of the homework was to convert two functions we already had, this one is the 6th.

(define (flatten-list a-list)
  (cond ((null? a-list) '())
      ((list? (car a-list)) 
       (append (flatten-list (car a-list)) (flatten-list (cdr a-list))))
      (else (cons (car a-list) (flatten-list (cdr a-list))))))

The function, as you can guess, flattens a list even if it's nested. My specific problem with the transformation comes in the (list? (car a-list)) condition, in which I'm doing two recursive calls. I already did fibonacci, which I can do by just having two "acummulators" on the tail recursion. However, my mind is not trained in this yet to know how it should go.

I would appreciate if I was given hints and not the result. Thanks!

Answer 1

We can follow the inspiration of John McCarthy's gopher trick, i.e. do it by rotating the list (though, here, not surgically but virtually, i.e. using the arguments for that):

(define (flatten lst)
  (flat (reverse lst) empty))

(define (flat lst rs)
  (cond
     ((null? lst) rs)
     ((null? (car lst))
       (flat (cdr lst) rs))
     ((not (pair? (car lst))) ;; atom? (car lst)
       (flat (cdr lst) 
             (cons (car lst) rs)))
     (else
       (flat (append (reverse (car lst))  ;; NB
                     (cdr lst))
             rs))))

There remains one point of contention which still has to be converted to the tail recursive call:

(list? a) =>
(flat (append (reverse a) d) rs)         ;; NB
=
(define (flaprev       a  d  rs)
  (cond
    ((null? a)       (flat           d rs))
    ((null? (car a)) (flaprev (cdr a) d rs))
    (else            (flaprev (cdr a)
                         (cons (car a) d) rs))))

Coincidentally, this shows a general technique for the conversion: turn every non-tail nested call into a flat call by bringing all the nested arguments up to the same level, then implement the needed function semantics according to how it is used and what's expected of it to produce and which laws to follow.

This "do this, and then do that" approach is formalized with the CPS technique, mentioned in the comments:

(define (flatten lst)   ;; your definition
  (cond 
    ((null? lst) '())
    ((list? (car lst)) 
      (append
            (flatten (car lst)) 
                   (flatten (cdr lst))))
    (else 
      (cons (car lst) 
                   (flatten (cdr lst))))))
===
(define (flatten lst)         ;; becomes
  (flat lst (lambda (x) x)))

(define (flat lst c)  ;; continuation "c" = "and then
  (cond               ;;                 use the result as"
    ((null? lst)  (c '()))
    ((list? (car lst))
      (flat (cdr lst) (lambda (rd)
           (flat (car lst) (lambda (ra)
               (c (append ra rd)))))))     ;; NB: append (??)
    (else
      (flat (cdr lst) (lambda (rd)
               (c (cons (car lst) rd)))))))

But what's with that pesky append? We can eliminate it with the same technique as we used in flaprev, by bringing all the nested arguments up to the same level, adding an explicit parameter for the list to reverse-append unto:

(define (flatten lst)
  (flat lst '() (lambda (x) x)))
         ;; ^^^__
         ;;      vvv
(define (flat lst d c)
  (cond  ;;      ___vvv
    ((null? lst)  (c d))
    ((list? (car lst))
      (flat (cdr lst) d (lambda (rd)
           (flat (car lst) rd (lambda (ra)
               (c ra))))))
    (else
      (flat (cdr lst) d (lambda (rd)
               (c (cons (car lst) rd)))))))

Now the length of the longest continuation is that of the longest sublist in the input, instead of the length of the output list.

Answer 2

Here's my solution:

(define (flatten-iter a-list)
  (define (flat-do acc lst-interm lst)
    (cond 
      ((null? lst)
       (reverse acc))
      ((and (list? lst-interm) (not (null? lst-interm)))
       (flat-do acc (car lst-interm) (append (cdr lst-interm) lst)))
      ((not (list? lst-interm))
       (flat-do (cons lst-interm acc) empty lst))
      ((list? (car lst))
       (flat-do acc (car lst) (cdr lst)))
      (else
       (flat-do (cons (car lst) acc) empty (cdr lst)))))
  (flat-do empty empty a-list))

(flatten-iter (list 1 (list 2 (list 3 4 (list 5 empty 6))) 7 8))
=> (1 2 3 4 5 6 7 8)

Tail-recrusive functions require that they never return, and thus you can't use stack for storing your program's state. Instead, you use function arguments to pass the state between function calls. Therefore, we need to determine how to maintain the state. Because the result of our function is list?, it's meaningful to grow an empty list; we're using acc for this purpose. You can see how it works in else branch above. But we should be able to process nested lists. And while we're going deeper, we should keep the rest elements of the nested list for further processing. Sample list: (list 1 (list 2 3) 4 5)

Until (list 2 3) we have already added 1 to accumulator. Since we can't use stack, we need some other place to store the rest elements of the list. And this place is the lst argument, which contains elements of the original list to be flattened. We can just append the lst to the rest elements (cdr (list 2 3)) which are (list 3), and proceed with the list's head we stumbled upon while flattening, i. e. (car (list 2 3)) which is just 2. Now, (and (list? lst-interm) (not (null? lst-interm))) succeeds because flat-do is called this way:

(flat-do (list 1) (list 2 3) (list 4 5))

and the condition triggers this code:

(flat-do (list 1) (car (list 2 3)) (append (cdr (list 2 3)) (list 4 5)))

flat-do again is called this way: (flat-do (list 1) 2 (list 3 4 5))

The condition (not (list? 2)) now succeeds and the code (flat-do (cons 2 1) empty (list 3 4 5)) is evaluated.

The rest processing is done with else branch until lst is null? and reverse is performed on acc. Function then returns the reversed accumulator.