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?

Óscar López · Accepted Answer · 2013-02-19 02:11:37Z

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 '())))))

Community · Accepted Answer · 2017-05-23 12:04:50Z

1

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.

edited May 23, 2017 at 12:04

CommunityBot

11 silver badge

answered Feb 19, 2013 at 8:05

Will Ness

71.6k10 gold badges105 silver badges192 bronze badges

Collectives™ on Stack Overflow

scheme tail recursion

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related