Схема хвостовой рекурсии

Question

Я пытаюсь создать схему хвостовой рекурсивной функции flatten-tl-rec, которая сглаживает вложенный список списков.

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

Но я получаю (13 12 11 10 9 8 7 6 5 4 3 2 1) вместо (1 2 3 4 5 6 7 8 9 10 11 12 13), Что здесь не так?

Answer 1

Вы накапливаете элементы в неправильном конце списка. Вы можете добавить их в правильном конце списка:

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

... Или просто перевернуть список в конце:

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

Answer 2

Ваша большая проблема в том, что эта функция вообще не является хвостовой рекурсивностью: не каждый вызов, который она делает, находится в хвостовой позиции. Вместо этого сделайте это:

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

Это реализует вручную оптимизацию по модулю "хвостовая рекурсия " с использованием трюка "начальник-дозорный", который значительно упрощает код за счет выделения только одной дополнительной соты. Подробнее в этом ответе.