;;; Trees ;;; A BT is one of: ;;; - Number ;;; - (make-node BT BT) (define-struct node (left right)) ;;; Examples ;;; - tournaments ;;; - family trees ;;; - collections of things (like lists) (define (occurs? x bt) (cond [(number? bt) (= x bt)] [else (or (occurs? x (node-left bt)) (occurs? x (node-right bt)))])) ;;; An AExp (arithmetic exp) is one of: ;;; - Number ;;; - 'x ;;; - (make-sum AExp AExp) ;;; - (make-prod AExp AExp) (define-struct sum (left right)) (define-struct prod (left right)) ;;; plug : AExp Number -> AExp ;;; Replace all occurrences of 'x with the number. (define (plug ae num) (cond [(number? ae) ae] [(symbol? ae) num] ; hit! [(sum? ae) (make-sum (plug (sum-left ae) num) (plug (sum-right ae) num))] [(prod? ae) (make-prod (plug (prod-left ae) num) (plug (prod-right ae) num))])) ;;; quote notation for lists ;;; An Atom is one of: ;;; - Number ;;; - Symbol ;;; - String ;;; An SExp is one of: ;;; - Atom ;;; - LoSExp ;;; A LoSExp is a [List-of SExp] ;;; Mutual recursion! (list (list 'a (list 'a)) 'c) ;;; Any -> Boolean ;;; Is the value an atom? (define (atom? x) (or (number? x) (symbol? x) (string? x))) ;;; Are the two atoms equal? (define (atom=? x y) (cond [(number? x) (and (number? y) (= x y))] [(symbol? x) (and (symbol? y) (symbol=? x y))] [(string? x) (and (string? y) (string=? x y))])) ;;; Sexp Symbol -> Boolean ;;; Does the sexp contain the given symbol? (define (occurs-in-sexp? sym sexp) (cond [(atom? sexp) (atom=? sym sexp)] [else (occurs-in-losexp? sym sexp)])) (define (occurs-in-losexp? sym sexps) (ormap (lambda (elt) (occurs-in-sexp? sym elt)) sexps)) ;;; Mutually recursive data defn -> mutually recursive code! ;;; The structure of the code follows the structure of the data. ;;; Or just collapse the mutual recursion into the ormap: (define (occurs-in-sexp?.v2 sym sexp) (cond [(atom? sexp) (atom=? sym sexp)] [else (ormap (lambda (elt) (occurs-in-sexp?.v2 sym elt)) sexp)])) ;;; ekwal? -- 2d template ;;; "Programmers are not to be measured by their ingenuity ;;; and their logic but by the completeness of their case analysis." -A Perlis (define (mota? x) (not (atom? x))) #; (define (sexp2-tmplt? s t) ; cross-product template (cond [(and (atom? s) (atom? t)) ... s ... t ...] [(and (atom? s) (mota? t)) ... s ... t ...] [(and (mota? s) (atom? t)) ... s ... t ...] [(and (mota? s) (mota? t)) ... s ... t ...])) #; (define (losexp-tmplt s t) ; parallel-walk template (cons [(and (empty? s) (empty? t)) ... s ... t ...] [(and (empty? s) (cons? t)) ... s ... t ...] [(and (cons? s) (empty? t)) ... s ... t ...] [(and (cons? s) (cons? t)) ... (first s) ... (first t) ... (losexp-tmplt (rest s) (rest t))...])) ;;; SExp SExp -> Boolean ;;; (define (ekwal? s t) (cond [(and (atom? s) (atom? t)) (atom=? s t)] [(and (atom? s) (mota? t)) false] [(and (mota? s) (atom? t)) false] [(and (mota? s) (mota? t)) (losexp=? s t)])) (define (losexp=? xs ys) (cond [(and (empty? xs) (empty? ys)) true] [(and (empty? xs) (cons? ys)) false] [(and (cons? xs) (empty? ys)) false] [(and (cons? xs) (cons? ys)) (and (ekwal? (first xs) (first ys)) (losexp=? (rest xs) (rest ys)))])) ;;; How does the world of Sexps compare to the world of things ;;; you can write using the quote notation: ;;; '(a ((b "foo" 3) 5) () 7) ? ;;; EKWAL? packages up a notion of equality that's ;;; complex. *If* you understand it... you may use EQUAL? ;;; Sexps are more or less the same thing as XML or JSON... ;;; [List-of Number] -> [List-of Number] ;;; Sort the list into increasing order (define (insert-sort xs) (foldr insert empty xs)) ;;; Number [List-of Number] -> [List-of Number] ;;; insert the number into the sorted list. (define (insert x ys) (cond [(empty? ys) (list x)] [(< x (first ys)) (cons x ys)] [else (cons (first ys) (insert x (rest ys)))])) ;;; Generative recursion -- quicksort (define (qsort xs) (cond [(empty? xs) empty] [else (local ((define pivot (first xs)) (define smalls (filter (lambda (x) (< x pivot)) xs)) (define equals (filter (lambda (x) (= x pivot)) xs)) (define bigs (filter (lambda (x) (> x pivot)) xs))) (append (qsort smalls) equals (qsort bigs)))])) ;;; All leafy trees ;;; A Tree is one of: ;;; 'leaf ;;; (make-node Tree Tree) ;;; All trees with one of the given left children and one of the given right children. ;;; [List-of Tree] [List-of Tree] -> [List-of Tree] (define (cross lefts rights) (foldr (lambda (left ans) (append (map (lambda (right) (make-node left right)) rights) ans)) empty lefts)) ;;; All leafy trees of height h. ;;; Number -> [List-of Tree] (define (leafy= h) (cond [(zero? h) '(leaf)] [else (local ((define talls (leafy= (- h 1))) (define shorts (leafy< (- h 1)))) (append (cross shorts talls) (cross talls shorts) (cross talls talls)))])) ;;; All leafy trees of height < h. ;;; Number -> [List-of Tree] (define (leafy< h) (cond [(zero? h) '()] [else (append (leafy= (- h 1)) (leafy< (- h 1)))])) ;;; Challenge: count the *number* of leafy trees of height h. ;;; (Without computing the actual trees -- way too expensive.)