tree - 试图在 Racket n-ary 中写 Foldtree 只知道如何写二叉树

Question

我正在尝试为 DrRacket 中的树编写折叠命令，只知道如何编写二叉树。有什么建议吗？它应该采用f诸如+，-等的功能。并折叠所有给定的数据，但不是通过展平树。

到目前为止，这是我想出的：

(define (bt-constr int left right) (list int left right)) 
(define (bt-val tree) (car tree)) 
(define (bt-left tree) (cadr tree)) 
(define (bt-right tree) (caddr tree)) 

(define (bt-fold f int tree)
  (if (null? tree) int 
      (f (bt-val tree) (f (bt-fold f int (bt-left tree)) (bt-fold f int (bt-right tree)))))) 

提前致谢！

Answer 1

假设以下定义，

(define (nt-constr int children) (list int children)) 
(define (nt-val tree) (car tree)) 
(define (nt-children tree) (cadr tree)) 

您可以遵循相同的模式：

(define (nt-fold f int tree)
  (if (null? tree) int 
      (f (nt-val tree)
         (... fold the children ...))))

现在，您可以折叠所有孩子并使用 , 获取它们各自的“折叠值”列表map，

(map (lambda (t) (nt-fold f t)) (nt-children tree))

您可以使用以下方法将该功能应用于此列表apply：

(define (nt-fold f int tree)
  (if (null? tree) int 
      (f (nt-val tree)
         (apply f (map (lambda (t) (nt-fold f int t)) (nt-children tree))))))