(@problem 1)
;;
;; PUT YOUR CS ID HERE ON THIS LINE: ____________________________
;;
(@problem 2)
;;
;; Below are a set of type comments and templates. On the TYPE COMMENTS:
;; – neatly draw reference arrows
;; – neatly label each arrow with R, SR, or MR.
;; – neatly label each arrow with a number 1, 2…
;; On the TEMPLATES:
;; – neatly label each (fn-for-… call with the number indicating the
;; arrow it corresponds to
;;
(define-struct tree (n branches))
(define-struct branch (w tree))
;;
(@htdd Tree)
;;
;; Tree is (make-tree String ListOfBranch)
;;
(@htdd ListOfBranch)
;;
;; ListOfBranch is one of:
;; – empty
;; – (cons Branch ListOfBranch)
;;
(@htdd Branch)
;;
;; Branch is (make-branch Natural Tree)
(define (fn-for-tree t)
(… (tree-n t)
(fn-for-lob (tree-branches t))))
(define (fn-for-lob lob)
(cond [(empty? lob) (…)]
[else
(… (fn-for-branch (first lob))
(fn-for-lob (rest lob)))]))
(define (fn-for-branch b)
(… (branch-w b)
(fn-for-tree (branch-tree b))))
;;
;; The following interpretation and data examples are intended to help you
;; understand how the data definitions work. The examples are also intended
;; to help you save writing time in problem 4.
;;
;; interp. An arbitrary-arity tree, with the extra feature that between a
;; tree node and any subtrees there is a branch with a weight
;; associated with it. So:
;; A Tree has a name and branches,
;; ListOfBranch is a list of branches,
;; a Branch has a weight and the next tree.
;;
;; Together these examples represent a tree that might be drawn as follows:
;;
;;
(define TA (make-tree “A” empty))
(define TC (make-tree “C” empty))
(define TB (make-tree “B” (list (make-branch 32 TC))))
(define TD (make-tree “D” empty))
(define TOP (make-tree “TOP”
(list (make-branch 12 TA)
(make-branch 20 TB)
(make-branch 41 TD))))
(@problem 3)
;;
;; Design a function that consumes a Tree and a String and does a backtracking
;; search for a tree of the given name. If it finds a tree with that name it
;; should produce the actual tree, if not it should produce false to signal
;; failure. Be sure to include all applicable design elements and tags.
;;
;; We have include a set of encapsulated templates on the next page. Do NOT
;; rewrite them entirely. Instead please NEATLY make whatever changes are
;; required. By doing less writing you save yourself time AND you make
;; it easier for the grader to read your solution.
;;
(define (fn-for-tree t)
(local [(define (fn-for-tree t)
(… (tree-n t)
(fn-for-lob (tree-branches t))))
(define (fn-for-lob lob)
(cond [(empty? lob) (…)]
[else
(… (fn-for-branch (first lob))
(fn-for-lob (rest lob)))]))
(define (fn-for-branch b)
(… (branch-w b)
(fn-for-tree (branch-tree b))))]
(fn-for-tree t)))
(@problem 4)
;;
;; Consider the following expression:
;;
(local [(define (foo x)
(local [(define (bar y)
(+ x y))]
(bar x)))]
(map foo (list 4 5 6)))
;;
;; We want you to write two things:
;;
;; (A) What value does the expression produce? Your answer MUST go in the
;; following space:
;;
;;
;; (B) When the expression is evaluated there will some number of lifted
;; definitions. Please write the SECOND lifted function definition.
;; We are not asking for a complete step by step evaluation, just
;; the second lifted definition. Don’t worry about the exact pattern
;; ISL uses to give names to lifted definitions, just use some
;; reasonable naming convention. Your answer MUST go in the following
;; space:
;;
(@problem 5)
;;
;; Write the signature for the following abstract function.
;; Your answer MUST go in the space marked below.
;;
(define (foo p f l)
(cond [(empty? l) empty]
[else
(if (p (first l))
(cons (f (first l)) (foo p f (rest l)))
(foo p f (rest l)))]))
;;
;; PUT YOUR ANSWER IN THIS COMMENT BLOCK
;;
;;
;;
;;
;;
;;
;;
;;
(@problem 6)
;;
;; Write the signature for the following abstract function.
;; Your answer MUST go in the space marked below.
;;
(define (bar f a l)
(cond [(empty? l) a]
[else
(bar f (f (first l) a) (rest l))]))
;;
;; PUT YOUR ANSWER IN THIS COMMENT BLOCK
;;
;;
;;
;;
;;
;;
;;
;;
(@problem 7)
;;
;; Below are the signature and purpose for three simple functions. The
;; definition of each of these functions can use built in abstract functions –
;; either a single abstract function or a composition of abstract functions.
;;
;; For each function check off which abstract functions you would use to
;; implement it.
;;
(@signature (listof String) -> Natural)
;; Produce length of longest string in the list, or 0 if the list is empty
;;
;; [ ] build-list [ ] foldr [ ] andmap
;;
;; [ ] filter [ ] map [ ] ormap
;;
(@signature (listof Image) -> Boolean)
;; Produce true if any image in the list is square
;;
;; [ ] build-list [ ] foldr [ ] andmap
;;
;; [ ] filter [ ] map [ ] ormap
;;
(@signature (listof Ball) -> Image)
;; Render list of balls onto the empty scene.
;;
;; [ ] build-list [ ] foldr [ ] andmap
;;
;; [ ] filter [ ] map [ ] ormap
;;
(@problem 8)
;;
;; Design a function that consumes a natural number and produces a list of
;; strings describing that many seats at a table. For example, (seats 3) should
;; produce the list (list “Seat 1” “Seat 2” “Seat 3”).
;;
;; Include all recipe elements. The body of your function definition MUST
;; USE the build-list built-in abstract function. You may optionally use an
;; additional built-in abstract function.
;;