Apply function to tree structure in racket

Question

I'm trying to apply a function to a tree in the form of a Map but not sure how to exactly go about it. Here's my attempt..

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

(struct emptyNode () #:transparent) ; leaf node

(define T (node 1 (node 2 (node 5 (emptyNode) (emptyNode) (emptyNode)) (emptyNode) (emptyNode))
                            (node 3 (emptyNode) (node 6 (emptyNode) (node 8 (emptyNode) (emptyNode) (emptyNode)) (emptyNode)) (emptyNode))
                            (node 4 (emptyNode) (emptyNode) (node 7 (emptyNode) (emptyNode) (emptyNode)))))

;                   1
;                 / |  \
;               2   3   4
;              /    |     \
;             5     6      7
;                   |
;                   8

;f
;   a function, f, used in MaptoTree
(define (f b)
  (* b 2))

;MaptoTree
;    takes a function, f, and a tree structure, tree, as parameters.
;    it should then produce a new tree structure where f has been applied to each value in the original tree
(define (MaptoTree f T)
  (if (pair? T)
      ((map (lambda (x) (MaptoTree f x)) (rest T)))
      (f T)))

edit: removed question about converting struct to list

user_201359 · Answer

You must use the selectors for node, instead of pair?, rest, etc. We're using a struct to represent the tree, not a normal list.

After fixing that, we just have to traverse the tree applying the function on each value, building a new tree as we go - like this:

(define (MaptoTree f T)
  (if (emptyNode? T)
      (emptyNode)
      (node (f (node-value T))
            (MaptoTree f (node-left T))
            (MaptoTree f (node-middle T))
            (MaptoTree f (node-right T)))))

user_323874 · Answer

You could also use the data/lazytree package (disclosure: I'm the author) to accomplish this, specifically the tree-map utility.

First, define a function to get the children of a node:

(define (node-children t)
  (list (node-left t)
        (node-middle t)
        (node-right t)))

Then, use it to create the tree representation:

(require data/lazytree)
(define t (make-tree node-children
                     T
                     #:with-data node-value
                     #:empty-pred emptyNode?))

You can now use tree-map to get the result:

(tree-map f t) ; => #

This returns a stream representing the resulting tree, which you could convert back to your original format if you need to:

(export-tree node
             (tree-map f t)
             #:empty-cons emptyNode)

=> (node 2
      (node 4
            (node 10
                  (emptyNode)
                  (emptyNode)
                  (emptyNode))
            (emptyNode)
            (emptyNode))
      (node 6
            (emptyNode)
            (node 12
                  (emptyNode)
                  (node 16
                        (emptyNode)
                        (emptyNode)
                        (emptyNode))
                  (emptyNode))
            (emptyNode))
      (node 8
            (emptyNode)
            (emptyNode)
            (node 14
                  (emptyNode)
                  (emptyNode)
                  (emptyNode))))

Apply function to tree structure in racket

2 Answers