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!
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)
(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
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
(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))
(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
reverse is performed on
acc. Function then returns the reversed accumulator.