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!

Fossilize

Answer 1

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.

Buna

Wish I had the ability to thank you for your quick response, Yasir. After reading it, I do understand what it's doing (which is pretty important), but I would appreciate it a lot if you could just hint me on the process of thought you followed. Sorry if I'm asking for too much! And thanks a lot for the help so far. – Fossilize

Mamsaac: I'm off to eat my pizza now. If you don't mind, let me explain it in a bit more detail later :-) – Buna

Buen provecho :) (enjoy your meal) – Fossilize

While you're waiting for Yasir to finish eating his pizza: there's a general technique called "continuation-passing style" (CPS) that can transform any piece of code so that all calls are in tail position. Matt might recently had a nice blog posting on CPS transformation that you might want to take a look at. – Teniafuge

Mamsaac: I updated the answer. And I agree with @John, CPS is a nice technique which is useful to look into. – Buna

Thanks to both of you. I will take a look at CPS later at night when I'm out of work. Have a great day :) – Fossilize

It may be a bit late, but in the first condition you need to check for lst and lst-interm being empty, or it won't add values from lst-interm to accumulator for lists like '(1 2 (3)) -- function will return '(1 2). – Feck

Answer 2

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.

Starchy