球拍中的树折叠

Question

我是 Racket 的初学者，我遇到了这个问题：

define a structure, node, which has these fields: value, left, middle, right. This structure represents nodes in a tree structure.
These fields contain the value stored in the node, the left subtree, the middle subtree, and the right subtree respectively. If a subtree does not exist, then the corresponding field should contain an emptyNode as described below.

define a structure, emptyNode, to specify an empty node in the tree.

Write a function, treeFold, which takes a function, f, an initial value, initial, and a tree structure, tree, as parameters. It should then produce a single value which is the result of using f to fold the values in the tree (using left, middle, and right subtrees in that order). Note that f is a function that takes two parameters. The first parameter is a value from the tree and the second is the partially accumulated result.

函数调用应该是：

(treeFold (lambda (a acc) (+ a acc)) 15 tree)

树：

(node 7 (node 5 (emptyNode) (emptyNode) (emptyNode)) 
        (node 20 (emptyNode) (emptyNode) (emptyNode)) 
        (emptyNode))

输出：47

这是我目前所做的：

(struct node (value left middle right) #:transparent)

(struct emptyNode () #:transparent)

(define tree 
    (node 7 
          (node 5 (emptyNode) (emptyNode) (emptyNode)) 
          (node 20 (emptyNode) (emptyNode) (emptyNode)) 
          (emptyNode)))

(define (treeFold f initial tree)
  (if (emptyNode? tree)
     (emptyNode)
     (node (f initial (node-value tree))
           (node-left tree)
           (node-middle tree)
           (node-right tree))))

如何得到整片叶子的总数？

任何想法或帮助，谢谢

编辑：因此，根据其评论中的答案和讨论，我得到了一个新功能，但仍然存在错误，我找不到它。这是：

(define (treeFold f initial tree) 
  (cond 
    [(emptyNode? tree) 
          (f initial 0)] 
    [else (f (node-value tree) 
             (f (treeFold f 
                   (treeFold f 
                      (treeFold f initial 
                         (node-left tree)) 
                      (node-middle tree)) 
                    (node-right tree))))]))

你能告诉我如何解决吗？谢谢。

编辑：最终代码

(define (treeFold f initial tree) 
  (cond 
    [(emptyNode? tree) (f initial 0)] 
    [else (f  (node-value tree)                
              (treeFold f                   
                   (treeFold f 
                        (treeFold f initial 
                             (node-left tree)) 
                             (node-middle tree)) 
                             (node-right tree)))]))

一切如我所愿

Answer 1

使用新版本的函数编辑问题后更新。

这是朝着正确方向迈出的一步。里面有正确的部分，也有错误的部分。

函数就像可以连接在一起的盒子。东西在一些电线上进，在其他一些电线上出。每个盒子都有它正确的使用方法：电线的数量，以及它期望流入其中的东西。

您的新版本：

(define (treeFold f initial tree) 
  (cond 
    [(emptyNode? tree) 
          (f initial 0)] 
    [else (f (node-value tree)                 ;; (1)
             (f (treeFold f                    ;; (2)
                   (treeFold f 
                      (treeFold f initial 
                         (node-left tree)) 
                      (node-middle tree)) 
                    (node-right tree))))]))

f 需要两个参数。 (f initial 0)看起来是对的，至少在这方面是这样。 (1) 中的调用也是如此。但是在 (2) 对 f 的调用只有一个参数提供给 f，所以不可能是正确的。

接下来说说意义吧。对 treeFold 的三个嵌套调用是 almost 右边：我们“进入”(node-left tree)，即左边 sub-tree，initial作为初始值，然后我们从中得到结果并使用它作为新的初始值进入中间sub-tree，并使用计算结果遍历右边sub-tree。好的。我们完成。这就是我们需要的 final 结果——无需再将其输入 f。因此，根本不需要对 treeFold 的三个嵌套调用之上的对 f 的两个调用。

除了，我们要用 (node-value tree) 做什么？它适合什么地方？答案是，它应该与initial值结合，通过调用f，以及that[=88]的result =] 应该用作我们遍历 left sub-tree 的初始值；我们开始折叠的值。

基本情况也不正确。我们已经有了 initial，为什么我们需要突然将它与 0 结合起来？为什么 0？例如，我们可以折叠一棵包含 字符串 的树，将字符串与数字 0 组合起来没有多大意义。

不，0 将提供作为调用 treeFold 的初始值，例如

(define (sumAllNumbersInWholeTree tree) (treeFold + 0 tree))

并且使用 strings-bearing 树我们可以，例如定义

(define (collectAllStringsInWholeTree tree) (treeFold string-append "" tree))

答案的初始版本如下。以您的新理解回顾它的（略微编辑的）示例。 :)

对于

(define tree (node 7 (node 5 (emptyNode) (emptyNode) (emptyNode)) (node 20 (emptyNode) (emptyNode) (emptyNode)) (emptyNode)))

根据规格，它必须是，

47 == (treeFold + 15 树) == (树折叠 + 15 （节点 7 (节点 5 (emptyNode) (emptyNode) (emptyNode)) (节点 20 (emptyNode) (emptyNode) (emptyNode)) （空节点））） == (树折叠 + （树折叠 + (treeFold + (+ 15 7) (节点 5 (emptyNode) (emptyNode) (emptyNode))) (节点 20 (emptyNode) (emptyNode) (emptyNode))) (空节点)) == (树折叠 + （树折叠 + （树折叠 + （树折叠 + (treeFold + (+ 22 5) (emptyNode)) (空节点)) (空节点)) (节点 20 (emptyNode) (emptyNode) (emptyNode))) (空节点)) == (树折叠 + （树折叠 + （树折叠 + (treeFold + 27 (空节点)) (空节点)) (节点 20 (emptyNode) (emptyNode) (emptyNode))) (空节点)) == (树折叠 + （树折叠 + (treeFold + 27 (空节点)) (节点 20 (emptyNode) (emptyNode) (emptyNode))) (空节点)) == (树折叠 + (treeFold + 27 (节点 20 (emptyNode) (emptyNode) (emptyNode))) (空节点)) …………

（写 == 表示“等于”）。这已经为您提供了完整定义所需的一切，即

(treeFold + i (node v lt md rt)) == (treeFold + (treeFold + (treeFold + (+ i v) lt) md) rt)

和

(treeFold + i (emptyNode)) == i

球拍中的树折叠

Tree fold in Racket

tree

fold

racket