使用折叠的树中的平方数

Question

目的是使用折叠树函数生成所有数字均平方的树。顺便说一下，这不是功课。所以我可以自由地讨论它。

; A Tree-Of-Numbers is one of:
; - (make-node Tree-Of-Numbers Number Tree-Of-Numbers)
; - EmptyTree
; interp. a tree with numbers stored at its nodes.

(define-struct node (left value right))

; An EmptyTree is a structure (make-empty-tree))
; interp. an empty tree

(define-struct empty-tree ())

(define EXAMPLE-TREE
  (make-node (make-node (make-node EMPTY 6 EMPTY)
                        20 EMPTY) 8 (make-node (make-node EMPTY 14 EMPTY)
                        42 (make-node EMPTY 2 EMPTY))))

(define EMPTY (make-empty-tree))

我已经编写了折叠树功能：

(define (fold-tree f b tree)
  (cond
    [(empty-tree? tree) b]
    [else (f (node-value tree)
             (fold-tree f b (node-left tree))
              (fold-tree f b (node-right tree)))]))

现在，我必须使用此函数对树中的所有数字求平方。我可以用其他方式做到这一点，例如：

(define (sqr-tree tree)
  (cond
    [(empty-tree? tree) EMPTY]
    [(node? tree) (make-node (sqr-tree (node-left tree))
                                 (sqr (node-value tree))
                                 (sqr-tree (branch-right tree)))]))

我还能够通过编写map-tree函数并使用该函数对树中的所有数字求平方来做到这一点。但是问题是，如何使用折叠树来做到这一点？

Answer 1

假设所有帮助程序均正确，这应该可以工作：

(define (sqr-tree tree)
  (fold-tree (lambda (value node-left node-right)
               (make-node node-left (sqr value) node-right))
             EMPTY
             tree))