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

问题描述

我是Racket的初学者，并且遇到了以下问题:

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

• 定义结构node，该结构具有以下字段:value，left，middle，right.此结构表示树结构中的节点.
  这些字段包含存储在节点，左侧子树中的值， 中间的子树和右边的子树.如果是子树 不存在，则对应的字段应包含 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

这是我到目前为止所做的:

this is what I did so far:

(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:因此，基于其评论中的答案和讨论，我得到了一个新功能，但是仍然有一个错误，我找不到它.在这里:

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.

除了，我们与(node-value tree)有什么关系?它适合哪里?答案是，应通过调用f将其与initial值组合，并且的 result 应该用作具有以下内容的初始值:我们遍历 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屋！