球拍中的树折叠 [英] Tree fold in Racket

问题描述

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

I am a beginner at Racket and I got this question:

• 定义一个结构，node，它有这些字段:value、left、middle、对.此结构表示树结构中的节点.
  这些字段包含存储在节点、左子树中的值，分别是中间子树和右子树.如果子树不存在，那么对应的字段应该包含一个emptyNode 如下所述.
• 定义一个结构，emptyNode，在树中指定一个空节点.
• 编写一个函数，treeFold，它接受一个函数，f，一个初始值，initial，和一个树结构，tree，作为参数.这应该然后产生一个单一的值，这是使用 f 折叠树中的值(使用 left、middle 和 right 子树命令).请注意，f 是一个带有 两个 参数的函数.首先参数是树中的一个值，第二个是部分累积结果.

• 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))))

我怎样才能得到整个叶子的总数?

How can I get the total of the whole leaves?

任何想法或帮助，谢谢

因此，根据其评论中的回答和讨论，我获得了一个新功能，但仍然存在错误，我找不到它.这是:

edit: so, based on the answer and discussion in its comments I got a new function but there is still a mistake and I could not find it. here it is:

(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))))]))

你能告诉我如何解决吗?谢谢.

could you please tell me how to fix it? thank you.

最终代码

(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)))]))

它按我的预期工作

推荐答案

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

update after question was edited with new version of the function.

这是朝着正确方向迈出的一步.里面有一些正确的部分，也有一些不正确的部分.

It is a step in the right direction. There's some correct pieces in it, and some incorrect pieces.

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

Functions are like boxes that can be wired together. Stuff goes in on some wires, and goes out on some others. Each box has it proper way of use: the number of wires, and the stuff it is expecting to flow into it in them.

您的新版本:

(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 的参数，所以不可能是对的.

f expects two arguments. (f initial 0) looks right, in that regard at least. The call in (1) as well. But the call to f at (2) has only one argument supplied to f, so can't be right.

接下来说说它的意思.对 treeFold 的三个嵌套调用几乎是正确的:我们进入"进入(node-left tree)，即左子树，以initial为初始值，然后我们从中得到结果并使用it 作为新的初始值进入中间子树，并使用计算结果遍历右子树.好的.我们完成.这就是我们需要的 final 结果——无需再将其输入 f.因此，根本不需要在对 treeFold 的三个嵌套调用之上对 f 的两次调用.

Next, to the meaning of it. The three nested calls to treeFold are almost right: we "go in" into (node-left tree), i.e. the left sub-tree, with initial as the initial value, then we get the result from that and use it as the new initial value to go into the middle sub-tree, and use the computed result to go over the right sub-tree. Nice. We're done. That is the final result we need -- no need to feed it into f any further. So those two calls to f above the three nested calls to treeFold aren't needed at all.

除此之外，我们如何处理(节点值树)?它适合放在哪里?答案是，它应该结合initial值，通过调用f，以及that的resultem> 应该用作我们遍历 left 子树的初始值；我们开始折叠的值.

Except, what are we to do with the (node-value tree)? Where does it fit in? The answer is, it should be combined with the initial value, by way of calling f, and the result of that should be used as the initial value with which we go over the left sub-tree; the value with which we start the folding.

基本情况也不正确.我们已经有了initial，为什么还要突然把它和0结合起来呢?为什么0?例如，我们可以折叠包含 strings 的树，并且将字符串与数字 0 组合起来并没有多大意义.

The base case is also incorrect. We already have the initial, why would we need to combine it with 0 all of a sudden? And why 0? We could be folding over a tree holding strings, for example, and combining strings with a number 0 wouldn't make a whole lot of sense.

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

No, 0 would be supplied as the initial value in a call to treeFold, like

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

对于带有字符串的树，我们可以例如定义

And with strings-bearing tree we could e.g. define

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

答案的初始版本如下.用你的新理解来复习它的(稍微编辑过的)例子.:)

Initial version of the answer follows. Go over its (very slightly edited) example with your new understanding. :)

为了

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

它必须是，根据规范，

47 == (treeFold + 15 tree)
   == (treeFold + 15 
        (node 7 
          (node 5 (emptyNode) (emptyNode) (emptyNode)) 
          (node 20 (emptyNode) (emptyNode) (emptyNode)) 
          (emptyNode)))
   == (treeFold + 
          (treeFold + 
              (treeFold + (+ 15 7)
                  (node 5 (emptyNode) (emptyNode) (emptyNode)))
              (node 20 (emptyNode) (emptyNode) (emptyNode)))
          (emptyNode))
   == (treeFold + 
          (treeFold + 
              (treeFold +  
                   (treeFold + 
                       (treeFold + (+ 22 5) (emptyNode))
                       (emptyNode))
                   (emptyNode))
              (node 20 (emptyNode) (emptyNode) (emptyNode)))
          (emptyNode))
   == (treeFold + 
          (treeFold + 
              (treeFold +  
                   (treeFold + 27
                       (emptyNode))
                   (emptyNode))
              (node 20 (emptyNode) (emptyNode) (emptyNode)))
          (emptyNode))
   == (treeFold + 
          (treeFold + 
              (treeFold + 27
                   (emptyNode))
              (node 20 (emptyNode) (emptyNode) (emptyNode)))
          (emptyNode))
   == (treeFold + 
          (treeFold + 27
              (node 20 (emptyNode) (emptyNode) (emptyNode)))
          (emptyNode))
   .........

(将 == 写成等于").这已经为您提供了完整定义所需的一切，即

(writing == for "equals"). This already gives you everything you need for a complete definition, namely that

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

和

(treeFold + i (emptyNode))
==
i

这篇关于球拍中的树折叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！