;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname module-09.rkt) (read-case-sensitive #t) (teachpacks ()))
;; ******************************* module-09.rkt *******************************
;; Complete count-sheep.
;; (count-sheep L) return the number of 'sheep in L.
;; count-sheep: (listof Any) -> Nat
;; Example:
;(check-expect (count-sheep (list 6 'sheep 'ram 3.14 'sheep 'ox)) 2)
;(check-expect (count-sheep (list 1 2 3)) 0)
;(check-expect (count-sheep (list 'sheep 2 3 'sheep 'sheep 'sheep)) 4)
;; an Operator is (anyof '+ '- '* '/)
(define-struct binode (op arg1 arg2))
;; a binary arithmetic expression internal node (BINode)
;; is a (make-binode Operator BinExp BinExp)
;; A binary arithmetic expression (BinExp) is either:
;; a Num or
;; a BINode
;; (eval-binexp expr) return the value of expr.
;; eval-binexp: BinExp -> Num
;; Examples:
;(check-expect (eval-binexp (make-binode '* 7 6)) 42)
;(check-expect (eval-binexp (make-binode '* 7 (make-binode '+ 4 2))) 42)
;; If you like, extend eval-binexp so it also handles '- and -/.
(define-struct bintree (label child1 child2))
;; a BinTree is a (make-bintree Any Any Any)
;; Requires: child1 and child2 are each either
;; a BinTree or
;; a leaf. Define the leaf separately!
(define (my-bintree-fun T)
(cond [(... T) ...] ; Some base case (often from a data definition)
[else (... (bintree-label T) ...
... (my-bintree-fun (bintree-child1 T)) ...
... (my-bintree-fun (bintree-child2 T)) ... )]))
(define tree0 42)
(define tree1
(make-bintree "hello" 13 17))
(define tree2
(make-bintree "sunny"
(make-bintree "day" 7 19)
3))
(define tree3
(make-bintree "climb"
5
(make-bintree "a"
31
(make-bintree "tree"
2
3))))
(define tree4
(make-bintree "have"
(make-bintree "a"
23
37)
(make-bintree "picnic"
5
3)))
;; (leftmost-child T) return the leftmost leaf
;; leftmost-child: BinTree -> Int
;; Examples:
;(check-expect (leftmost-child tree0) 42)
;(check-expect (leftmost-child tree1) 13)
;(check-expect (leftmost-child tree2) 7)
;(check-expect (leftmost-child tree3) 5)
;(check-expect (leftmost-child tree4) 23)
;; (join-labels T) join together all the labels in T.
;; join-labels: BinTree -> Str
;; Examples:
;(check-expect (join-labels tree0) "")
;(check-expect (join-labels tree1) "hello")
;(check-expect (join-labels tree2) "sunnyday")
;(check-expect (join-labels tree3) "climbatree")
;(check-expect (join-labels tree4) "haveapicnic")
(define-struct snode (key left right))
;; a SNode is a (make-snode Num SSTree SSTree)
;; a simple search tree (SSTree) is either
;; * '() or
;; * a SNode, where keys in left are less than key, and in right greater.
(define tree12
(make-snode 12
(make-snode 10
'()
(make-snode 11 '() '()))
(make-snode 15 '() '())))
;; Complete tree-sum.
;; (tree-sum tree) return the sum of all keys in tree.
;; tree-sum: SSTree -> Num
;; Example:
;(check-expect (tree-sum tree12) 48)
;; (tree-search tree item) return #true if item is in tree.
;; tree-search: SSTree Num -> Bool
;; Example:
;(check-expect (tree-search tree12 10) #true)
;(check-expect (tree-search tree12 7) #false)
(define-struct node (key val left right))
;; A binary search tree (BST) is either
;; * '() or
;; * (make-node Nat Any BST BST)...
;; which satisfies the ordering property recursively:
;; * every key in left is less than key
;; * every key in right is greater than key
(define-struct student (name programme))
(define student-bst
(make-node 7524
(make-student "Ben Bernanke" "economics")
(make-node 6938
(make-student "Al Gore" "government")
'()
(make-node 7334
(make-student "Bill Gates" "appliedmath")
'()
'()))
(make-node 8535
(make-student "Conan O'Brien" "history")
'()
(make-node 8838
(make-student "Barack Obama" "law")
'() '()))))
;; (dict-search dict item) return correct val if item is in dict.
;; dict-search: BST Num -> Any
;; Example:
(check-expect (dict-search student-bst 6938)
(make-student "Al Gore" "government"))
(check-expect (dict-search student-bst 9805) #false)
(define (dict-search dict item)
(cond [(empty? dict) #false]
[(= item (node-key dict)) (node-val dict)]
[(< item (node-key dict)) (dict-search (node-left dict) item)]
[(> item (node-key dict)) (dict-search (node-right dict) item)]))
;; mynode-template: BST -> Any
(define (mynode-template tree)
(make-node (node-key tree)
(node-val tree)
(node-left tree)
(node-right tree)))
;; Complete dict-add.
;; Look back at the data definition for BST.
(define-struct association (key val))
;; An Association is a (make-association Nat Any)
;; (dict-add newassoc tree) return tree with newassoc added.
;; dict-add: Association BST -> BST
;; Examples:
;(check-expect (dict-add (make-association 4 "four") '())
; (make-node 4 "four" '() '()))
;(check-expect
; (dict-add (make-association 6 "six")
; (dict-add (make-association 2 "two")
; (dict-add (make-association 4 "four") '())))
; (make-node 4 "four" (make-node 2 "two" '() '())
; (make-node 6 "six" '() '())))
;; (expand-bst L tree) add all items in L to tree, adding the last first.
;; expand-bst: (listof Association) BST -> BST
;; Example:
;(check-expect
; (expand-bst (list (make-association 4 "four")) '())
; (make-node 4 "four" '() '()))
;(check-expect
; (expand-bst (list (make-association 2 "two")
; (make-association 6 "six")
; (make-association 4 "four")) '())
; (make-node 4 "four"
; (make-node 2 "two" '() '()) (make-node 6 "six" '() '())))
(define-struct ainode (op args))
;; an arithmetic expression internal node (AINode)
;; is a (make-ainode Operator (listof AExp))
;; An arithmetic expression (AExp) is either:
;; a Num or
;; a AINode
;; (eval-ainexp expr) return the value of expr.
;; eval-ainexp: AExp -> Num
;; Examples:
(check-expect (eval-ainexp (make-ainode '* (list 2 3 5))) 30)
(define (eval-ainexp expr)
(cond [(number? expr) expr] ; numbers evaluate to themselves
[(equal? (ainode-op expr) '*)
(foldr * 1
(map eval-ainexp (ainode-args expr)))]
[(equal? (ainode-op expr) '+)
(foldr + 0
(map eval-ainexp (ainode-args expr)))]))
(define-struct gnode (label children))
;; a generic tree node (GNode) is a (make-gentree Any (listof GTree))
;; a generic Tree (GenTree) is either:
;; a GNode (recursive type) or
;; possibly something else (leaf type).
(define (gentree-function T)
(cond [(not (gnode? T)) ; This is a leaf.
(... T)] ; Do something with a leaf.
[else ; This is not a leaf, so it's a
( ; (make-gentree Any (listof GNode)). Work with the list!
... (gnode-label T) ... ; Do something with the label.
(foldr
... ; Function to combine answers.
... ; Base case for the combining function.
(map ; Using this function, process each child.
gentree-function (gnode-children T)))
...)]))
;; (count-leaves T) return the number of leaves in T.
;; count-leaves: GenTree -> Nat
;; Examples:
;(check-expect (count-leaves (make-gnode 'wut (list "foo" "bar" "baz"))) 3)
;(check-expect (count-leaves
; (make-gnode '+
; (list 2 3 (make-gnode '* (list 6 7 42))))) 5)
;; Here's the template all set up; you use it!
(define (count-leaves T)
(cond [(not (gnode? T)) ; This is a leaf.
(... T)] ; Do something with a leaf.
[else ; This is not a leaf, so it's a
( ; (make-gentree Any (listof GNode)). Work with the list!
... (gnode-label T) ... ; Do something with the label.
(foldr
... ; Function to combine answers.
... ; Base case for the combining function.
(map ; Using this function, process each child.
count-leaves (gnode-children T)))
...)]))
;; a Sentence is a GenTree where:
;; each label is a Sym
;; each leaf is a Str.
(define catS (make-gnode
'S (list
(make-gnode
'NP (list
(make-gnode 'D (list "the"))
(make-gnode 'N (list "cat"))))
(make-gnode
'V (list "ate")))))
;; Complete sentence->list
;(check-expect (sentence->list catS) (list "the" "cat" "ate"))
;; A few example trees you may use. See diagrams in notes.
(define llt1
(list 2)
)
(define llt2
(list 5 7)
)
(define llt3
(list 2 (list 5 7) 3)
)
(define llt4
(list 2 (list 3 (list 5 7 11)))
)
;; a leaf-labelled tree (LLT) is either
;; a Num or
;; a non-empty (listof LLT).
;; my-LLT-fun: LLT -> Any
(define (my-LLT-fun L)
(cond [(number? L) ; this is a leaf.
(... L ...)]
[else ; this is not a leaf, so it's a (listof LLT).
(... (foldr ... ... (map my-LLT-fun L) ...))]))
;; Complete count-llt
;; Complete depth.
;; (depth tree) return the max distance from the root to a leaf of tree.
;; depth: LLT -> Nat
;; Examples:
;(check-expect (depth (list 6 7)) 1)
;(check-expect (depth (list 2 (list 3 (list 5)))) 3)
;; Complete flatten.
;; (flatten tree) return the list of leaves in tree.
;; flatten: LLT -> (listof Num)
;; Examples:
;(check-expect (flatten (list 1 (list 2 3) 4)) (list 1 2 3 4))
;(check-expect (flatten (list 1 (list 2 (list 3 4)))) (list 1 2 3 4))