scheme - 典型的なツリー再帰が末尾再帰形式に変わった例を探しています

Question

ネストされたリストに対するフラット化、アトム数のカウントなどは問題ありません。

ところで、私はCPS変換や「ペアツリー」には興味がありません。

Answer 1

処理する次のツリーを記録するスタックを使用してループを作成するだけです。アキュムレータも必要です。しかし、これはCPSとそれほど変わらないので、探しているものではない可能性があります。

(define (atom? x) 
  (not (pair? x)))
(define (size tree)
  (let loop ((t tree) (stack '()) (total 0))
    (cond
      ((and (atom? t) (null? stack)) (add1 total))
      ((atom? t) (loop (car stack) (cdr stack) (add1 total)))
      (else (loop (cadr t) (append (cddr t) stack) (add1 total))))))
(define (flatten tree)
  (let loop ((t tree) (stack '()) (l '()))
    (cond
      ((and (atom? t) (null? stack)) (reverse (cons t l)))
      ((atom? t) (loop (car stack) (cdr stack) (cons t l)))
      (else (loop (cadr t) (append (cddr t) stack) (cons (car t) l))))))