map function for n-ary tree in Scheme

Question

the definition for a map function for binary trees is:

(define (binary-tree-map proc tree)
   (cond ((null? tree) null)
         ((not (pair? tree)) (proc tree))
         (else (cons (binary-tree-map proc (car tree))
                     (binary-tree-map proc (cdr tree))))))

what does a map function for n-ary trees look like? tried:

(define (n-tree-map proc tree)
  (cond ((null? tree) null)
        ((not (pair? tree)) (proc tree))
        (else (apply map append (lambda (p)(n-tree-map proc (cdr tree)))))))

Answer 1

Every n-ary tree made with cons (known as tree structure) will have a mirror binary tree equivalent. Mapping over the tree keeps the structure and thus all the cons in the exact same relationship so the result of running your binary-tree-map over a n-ary tree as if it were a n-ary map should yield the same result.

(1 2 (3 4)) can be interpreted as:

 /|\
1 2 |\
    3 4

But as a binary tree it would be:

 /\
1 /\
 2 /\
  /\ nil
 3 /\
  4 nil

Lets try it!

(binary-tree-map (lambda (x) (+ x 1)) '(1 2 (3 4))) 
; ==> (2 3 (4 5))

Now if you would have created a tree differently. Eg. with records so that a node is not a pair or if you need to keep track of the depth, then you would need a different procedure for it.

#!r6rs
(import (rnrs))
(define-record-type (tree make-tree tree?)
  (fields 
    (immutable children tree-children)))

(define (tree-map proc tr)
  (cond ((not (tree? tr)) (proc tr))
        (else (make-tree (map (lambda (x) (tree-map proc x)) (tree-children tr))))))

(define test-tree
        (make-tree (list '(1 2 3) 
                    '(2 3 4) 
                    '(3 4 5) 
                    (make-tree '((7 8 9) 
                            (10 11 22))))))

(tree-map cdr test-tree) 
; ==> (#tree (list '(2 3) '(3 4) '(4 5) (#tree '((8 9) (11 22)))))

Notice how lists now can be leafs since a list doesn't mean node. It's possible to do this with list structure too by using a tag to identify nodes:

(define tree-tag (vector 'tree))
(define (tree? tr) (and (pair? tr) (eq? tree-tag (car tr))))
(define (make-tree children) (cons tree-tag children))
(define tree-children cdr)

(tree-map cdr test-tree) 
; ==> '(#(tree) (2 3) (3 4) (4 5) (#(tree) (8 9) (11 22)))

Answer 2

Short answer, that function could very well be used for n-ary trees. Given that you are using language primitives directly rather than an ADT (abstract data type). One way to represent represent n-ary trees is like so...

(define (make-n-ary-tree node . children)
 (cons node children)) 

The only weird thing in this implementation combined with your function is that it would add an extra empty-tree the the end of the children trees)

When dealing with trees or other complex data types, it's ideal to construct an ADT, or put in you comments what the representation means.

Remember the computer doesn't give a flying freak about the meaning of your data. You the programmer have to be very careful to keep consistent meaning and semantics.