;;; ordered-tree insert & "dictionary"

;;; A SND (string/number dictionary) is one of:
;;; - 'leaf
;;; - (make-node String Number NSD NSD)
;;; Invariants:
;;; - All keys in node's left child are less than node's key.
;;; - All keys in node's right child are greater than node's key.

(define-struct node [key val left right])

(define (add-entry k v nsd)
  (cond [(symbol? nsd) (make-node k v 'leaf 'leaf)]
	[else (local [(define n-key (node-key nsd))
		      (define n-val (node-val nds))]
	        (cond [(string<? k n-key)
		       (make-node n-key n-val
				  (add-entry k v (node-left nsd))
				  (node-right nsd))]
		      [(string>? k n-key)
		       (make-node n-key n-val
				  (node-let nsd)
				  (add-entry k v (node-right nsd)))]
		      [else (make-node k v
				       (node-left  nsd)
				       (node-right nsd))]))]))

;;; I could abstract the data definition over the key and value:
;;; A [Dict K V] is one of:
;;; - 'leaf
;;; - (make-node K V [Dict K V] [Dict K V])
;;;
;;; But how would I do key comparison?

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;; An AE (arithmetic expression) is one of:
;;; - Number
;;; - (make-add AE AE)
;;; - (make-sub AE AE)
;;; - (make-mul AE AE)

(define-struct add [left right])
(define-struct sub [left right])
(define-struct mul [left right])

;;; Examples:
3
(make-add 10 20)
(make-mul (make-add 10 20) 3)

;;; What's a good interpretation for these things?
;;; 3 (+ 10 20) (* 3 (+ 10 20))

;;; Can we *do* the computation so described?

;;; AE -> Number
(define (eval ae)
  (cond [(number? ae) ae]
	[(add? ae) (+ (eval (add-left ae))
		      (eval (add-right ae)))]
	[(mul? ae) (* (eval (mul-left ae))
		      (eval (mul-right ae)))]
	[(sub? ae) (- (eval (sub-left ae))
		      (eval (sub-right ae)))]))

;;; Can we convert to/from friendlier-looking lists?
(check-expect (ae->sexp (make-mul (make-add 10 20) 3))
	      '(* (+ 10 20) 3))

;;; Let's permit plus & times to take more (or less) than 2 arguments:
(define-struct add [children])
(define-struct sub [left right])
(define-struct mul [children])

;;; A tree with variable branch factor for add & mul nodes:
;;; (* (+ 3 2) (- 3 2) (* 3 2)) represented as:
(make-mul (list (make-add (list 3 2))
		(make-sub 3 2)
		(make-mul (list 3 2))))