如何在 scheme 中使用 apply 编写 tree-map 函数

Question

写完后：

(define (tree-accumulate tree)
  (if (pair? tree)
      (apply + (car tree) (map tree-accumulate (cdr tree)))
(+ tree)))

例如：（树累积'（1 1 1（1（1（1 1 1）1 1）1 1（1 1 1（1 1 1））））） ==> 18

如何编写树图函数以便您可以编写：

(define (tree-accumulate tree)
        (tree-map + tree))

尝试过：

(define (tree-map f tree)
  (if (pair? tree)
      (apply + (car tree) (map (tree-map (cdr tree)) )
      (f tree)))

但问题是如何将f参数放入：(map (tree-map (cdr tree)) 申请还有效吗？

Answer 1

嗯，这样的函数不会被称为 map。它实际上更像是一个fold，类似于foldr or foldl。所以无论如何，这是使用 tree-foldl 函数的 tree-accumulate 的一种可能定义：

(define (tree-accumulate tree)
  (tree-foldl + 0 tree))

作为第二个参数的 0 是基本情况，用于树中没有叶子的情况。 tree-foldl函数可以这样定义：

;; (Treeof A) is one of:
;;  - A
;;  - (Listof (Treeof A))
;; Where the A type can't include lists.

;; tree-foldl : [A B -> B] B (Treeof A) -> B
;; Where the A type can't include lists.
(define (tree-foldl f base tree)
  (cond [(not (list? tree))
         (f tree base)]
        [else
         (tree-foldl/list f base tree)]))

;; tree-foldl/list : [A B -> B] B (Listof (Treeof A)) -> B
;; Where the A type can't include lists.
(define (tree-foldl/list f base tree)
  (cond [(empty? tree)
         base]
        [else
         (tree-foldl/list f
                          (tree-foldl f base (first tree))
                          (rest tree))]))

使用 tree-accumulate 这个定义，

> (tree-accumulate '(1 1 1 (1 (1 (1 1 1) 1 1) 1 1 (1 1 1 (1 1 1)))))
18

Answer 2

如前所述，这不是地图而是折叠。

不过，你只需要"wrap"在另一个函数中递归应用，这样你就可以通过f on:

(define (tree-fold f tree)
  (if (pair? tree)
      (apply f (car tree) (map (lambda (t) (tree-fold f t)) (cdr tree)))
      (f tree)))

实际地图可能如下所示：

(define (tree-map f tree)
  (if (pair? tree)
      (cons (f (car tree)) (map (lambda (t) (tree-map f t)) (cdr tree)))
      (f tree)))

如何在 scheme 中使用 apply 编写 tree-map 函数

how to write tree-map function using apply in scheme

tree

scheme

racket