Tree fold in Racket

Question

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

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.

the function call should be :

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

tree:

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

the output : 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?

any ideas or help, thanks

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.

edit: final code

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

it works as I expected

there's still a problem with your new code. as I discuss in the answer, collectAllStringsInWholeTree won't work under it. there's no need to combine initial with 0 on the empty node. why 0? what if it's strings we're dealing with? just initial is enough, there. except for that, well done. :) it defines a post-order traversal of a tree, whereas my answer suggests a pre-order one. I guess both are OK as it is not specified in the requirements. but since it is named "initial", I'd expect pre-order be the intended one. otherwise it'd be named "final" or something. — Will Ness
with numbers and + it doesn't matter, but what if it were -? or strings with string-append? then the results for pre- and post-order folding would be different, in general. i.e. (treeFold - 100 tree) should return 68, I think. — Will Ness

Will Ness Will Ness · Accepted Answer · 2020-10-24T11:37:53

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.

Your new version:

(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 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.

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.

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.

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.

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. :)

For

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

it must be, according to the specs,

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)

and

(treeFold + i (emptyNode))
==
i

Tree fold in Racket

1 Answers