Preorder Notation in Scheme

Question

Assume that my "map-diff" function works properly for the following code. I am wondering how to take an arithmetic parse tree and output it in preorder notation. I want to be able to use my "map-diff" function inside my "preorder" function, but I can't figure out how to go about doing this. Are my base cases here correct?

(define (make-tree value left right) (list value left right)) 
(define (value tree) (car tree))
(define (left tree) (cadr tree))
(define (right tree) (caddr tree))

(define (prepare x)
  (cond ((number? x) (number->string x))
        ((char? x) (string x))))

(define x
  (map-diff (lambda (x) (prepare x)) 
    (list #\+ 
      (list #\*
         (list 3 '() '())
         (list 9 '() '()))
      (list #\+
         (list #\/ (list 5 '() '()) '())
         (list 4 '() '())))))


(define (preorder T)
  (cond ((null? T) "")
       ((eq? (value T) "+")
         (cons (value T) (cons (preorder (left T)) (preorder (right T)))))
       ((eq? (value T) "*")
        (cons (value T) (cons (preorder (left T)) (preorder (right T)))))
       ((eq? (value T) "-")
         (cons "-" (preorder (left T))))
       ((eq? (value T) "/")
         (cons "/" (preorder (left T))))
       (else (value T))))

(preorder x)

Answer 1

First , don't mix your ADT and primative types together. If you define an ADT stick with it thoughout the program. X should be defined in terms of make-tree rather than list). And make-tree rather than cons in preorder. The way you have it now your going to get a dotted list as output rather than a nice proper list form.

I'm not sure what your trying to do with prepare, casting things to strings to parse them is fairly unusual, considering lisps dynamic typing.

Anyways here is one possibility

(define (preorder T)
 (let ((top (prepare (value T))))
  (cond ((null? T) "")
        ((eq? top "+")
         (cons top (cons (preorder (left T)) (preorder (right T)))))
        ((eq? top "*")
         (cons top (cons (preorder (left T)) (preorder (right T)))))
        ((eq? top "-")
         (cons "-" (preorder (left T))))
        ((eq? top "/")
         (cons "/" (preorder (left T))))
        (else top)))

Answer 2

;; helper
(define (list-ref-at n)
  (lambda (l) (list-ref l n)))

;; node data type
(define (make-node value left right)
 `(NODE ,value ,left ,right))
(define node-value (list-ref-at 1))
(define node-left  (list-ref-at 2))
(define node-right (list-ref-at 3))

;; leaf data type (as special node)
(define (make-leaf value)
  (make-node value '() '()))
(define (node-is-leaf? node)
  (and (null? (node-left  node))
       (null? (node-right node))))

;; convert to list
(define (node->preorder-list node)
  (if (node-is-leaf? node)
      (node-value node)
      (let ((v (node-value node))
            (l (node-left  node))
            (r (node-right node)))
        (assert (not (null? l)))
        (if (null? r)
            (list v (node->preorder-list l)) ; unop
            (list v (node->preorder-list l) (node->preorder-list r)))))) ;binop

;; test
> (define x (make-node '* (make-node '+ (make-leaf 1) (make-leaf 2)) (make-leaf 10))
> (node->preorder-list x)
(* (+ 1 2) 10)
> (set! x (make-node '- x '()))
> (node->preorder-list x)
(- (* (+ 1 2) 10))