scheme tail recursion

Question

I am trying to create a scheme tail recursive function flatten-tl-rec that flattens a nested list of lists.

(define flatten-tl-rec
  (lambda (xs)
    (letrec ([flatten-tl-rec-acc
              (lambda (xs acc)
                (cond ((empty? xs) acc)
                      ((list? (first xs)) (flatten-tl-rec-acc (rest xs) (append (flatten-tl-rec-acc (first xs) '()) acc)))
                      (else (flatten-tl-rec-acc (rest xs) (cons (first xs) acc))))
                )])
      (flatten-tl-rec-acc xs '()))))

(flatten-tl-rec '(1 2 3 (4 5 6) ((7 8 9) 10 (11 (12 13)))))

But I am getting (13 12 11 10 9 8 7 6 5 4 3 2 1) instead of (1 2 3 4 5 6 7 8 9 10 11 12 13). Whats wrong here?

score 4 · Accepted Answer · answered Feb 19 '13 at 02:11

You're accumulating the elements at the wrong end of the list. You can either append them at the correct end of the list:

(define flatten-tl-rec
  (lambda (xs)
    (letrec ([flatten-tl-rec-acc
              (lambda (xs acc)
                (cond ((empty? xs) acc)
                      ((list? (first xs))
                       (flatten-tl-rec-acc
                        (rest xs)
                        (append acc (flatten-tl-rec-acc (first xs) '()))))
                      (else (flatten-tl-rec-acc
                             (rest xs)
                             (append acc (list (first xs)))))))])
      (flatten-tl-rec-acc xs '()))))

... Or simply reverse the list at the end:

(define flatten-tl-rec
  (lambda (xs)
    (letrec ([flatten-tl-rec-acc
              (lambda (xs acc)
                (cond ((empty? xs) acc)
                      ((list? (first xs))
                       (flatten-tl-rec-acc
                        (rest xs)
                        (append (flatten-tl-rec-acc (first xs) '()) acc)))
                      (else (flatten-tl-rec-acc
                             (rest xs)
                             (cons (first xs) acc)))))])
      (reverse (flatten-tl-rec-acc xs '())))))

score 1 · Answer 2 · edited May 23 '17 at 12:04

Your bigger problem is that that function is not tail-recursive at all: not every call to itself that it makes is in tail position. Instead do this:

(define (flatten xs)
  (let ((result (list 1)))
    (let loop ((xs xs) (p result))
      (cond 
        ((null? xs) 
          (cdr result))
        ((pair? (car xs))
          (loop (cons (caar xs) 
                  (cons (cdar xs) (cdr xs)))
                p))
        ((null? (car xs))
          (loop (cdr xs) p))
        (else
          (set-cdr! p (list (car xs)))
          (loop (cdr xs) (cdr p)))))))

This implements by hand a tail recursion modulo cons optimization, using a "head-sentinel" trick which greatly simplifies the code at a cost of allocating just one extra cons cell. More in this answer.

scheme tail recursion

2 Answers2

Linked