(require spd/tags)
PROBLEMS 1-5:
First consider the signature, purpose, check-expects and st
(@signature (listof String) -> Natural)
;; produce the sum of the lengths of the odd length strings in los
(check-expect (sum-odd-lengths empty) 0) (check-expect (sum-odd-lengths (list “a”)) 1) (check-expect (sum-odd-lengths (list “ab”)) 0) (check-expect (sum-odd-lengths (list “a” “abc” “ab” “abcde”)) 9)
(define (sum-odd-lengths los) 0) ;stub
You will now write FIVE different definitions for the funct the signature, purpose, check-expects or stub. Just write tag and function definition. You will want to use theR odd?
PROBLEM 1:
Write a definition as a single function based on the (listof template, with no helper functions. Be sure to include the
PROBLEM 2:
Write a definition as a composition of at least 2 helper fu wish for. Be sure to include the @template tag. For each wis also write a complete wish list entry including signature, You just need the wish list entry for those helper functions need the complete design for the helper functions.
he
d
PROBLEM 3:
Write a definition as a composition of two or more built-in functions. Be sure to include the @template tag.
PROBLEM 4:
Write a definition as a single tail-recursive function, bas (listof String) template, with a single accumulator and no Be sure to include accumulator type, invariant and the @tem
PROBLEM 5:
Write a definition as a single function using for-each, wit functions. Be sure to include the @template tag.
PROBLEM 6:
Design a function that consumes a list of numbers and produ formed by choosing elements of that list as follows.
– the 1st element is included
– the 2nd element of the rest after the above is included – the 3rd element of the rest after the above is included – and so on until you run out of elements.
Put another way, it takes a number, then skips 1, takes the number, skips 2, takes the number, skips 3 and so on.
So for example, calling choose as follows
(choose(list6 14 135 1234 123411 1
should produce (list 6 4 5 4 11)
Note that the extra spaces in the list above are for illustrat purposes only. Your function consumes (listof Number), there no magic spaces. Include all relevant recipe elements, includ purpose, stub, check-expects, @template, accumulator type and
i i
PROBLEM 7 – 8:
In these problems you will refactor the definition of functi use built-in abstract functions.
on
in
PROBLEM 7:
Write a new definition for fact that uses one or more built- functions.
(@signature Natural -> Natural) ;; produce factorial of n (check-expect (fact 0) 1) (check-expect (fact 3) 6)
(@template Natural)
s
–
(define (fact n) (cond [(zero? n) 1]
[else
(* n (fact (sub1 n)))]))
PROBLEM 8:
Write a new definition for clip-all that uses one or more bu functions.
NOTE: As used below clip means to cut a number down to fit interval.
(@signature (listof Number) -> (listof Number))
;; clip every number in list to be within the given [lo,
il
t
hi] interval
(check-expect (clip-all 10 20 (list)) (list)) (check-expect (clip-all 10 20 (list 9 10 11 19 20 21))
(list 10 10 11 19 20 20)) (check-expect (clip-all 30 50 (list 42 12 39 53 9))
(list 42 30 39 50 30))
(define (clip-all lo hi lon) (cond [(empty? lon) empty]
[else
(cons (max lo (min (first lon) hi))
(clip-all lo hi (rest lon)))]))
PROBLEM 9:
In the mutual reference laboratory you designed data and fun represent and work with sentence trees like these.
As you will recall, the idea here is that you can read a num off of this by following different routes down the tree:
…
KISS ME BEFORE YOU ARE FAMOUS AND FORGET ABOUT ME KISS ME LIKE IT IS YOUR LAST CHANCE
KISS ME ON A DARE
…
Below are data definitions and example data for sentence tre Also included is an abstract fold function for STree.
(@htdd STree)
ct
be
es
i
r
.
(define-struct st (s kids))
;; ;; ;; ;;
STree is (make-st String ListOfSTree)
interp. (make-st s kids) is a sentence tree with
s as the phrase at the root and kids as its children
(@htdd ListOfSTree)
;; ListOfSTree is one of:
;; – empty
;; – (cons STree ListOfStree)
;; interp. A list of sentence trees
(define ST1 (make-st “recipes” empty))
(define ST2 (make-st “instructions for your IKEA furniture” empty))
(define ST3 (make-st “trust the natural recursion” empty)) (define ST4 (make-st “follow the” (list ST1 ST2))) (define ST5 (make-st “Make sure you” (list ST3 ST4)))
(@htdf fold-stree)
;; (String Y -> Z) (Z Y -> Y) Y STree -> Z
;; Abstract fold for STree
(check-expect (fold-stree make-st cons empty ST5) ST5)
(define (fold-stree c1 c2 b1 st) (local [(define (fn-for-stree st)
(c1 (st-s st)
(fn-for-lost (st-kids st))))
(define (fn-for-lost lost) (cond [(empty? lost) b1]
[else
(c2 (fn-for-stree (first lost))
(fn-for-lost (rest lost)))]))] (fn-for-stree st)))
Please design a function that consumes an STree and produce the sentences that can be generated starting at the root of Each sentence should be a list of the strings that form that So calling your function with ST1 would produce (list (list because ST1 just describes a single sentence, and that single is formed from just one contribution “recipes”. Calling with a list of two lists, each with two strings.
You must provide signature, purpose, stub, check-expects and Your function must call fold-stree, no credit will be given
Work systematically and pay particular attention to the exampl of the recipe. While this problem is not particularly difficu it is a little more complicated than it seems at first.
e l
Problem 10:
READ THIS BOX TWICE CAREFULLY BEFORE BEGINNING TO WORK ON THIS
Below is a simple solver for square mazes. It has been PARTIA from 2 way mazes into a solver for 4 way mazes. What has been is to update the next-ps function to support moves in all four But nothing has been done to prevent going in cycles in the
You must complete the conversion and add the following new
Instead of searching for just one path, the function should without cycles. If there is just one, produce it. If e one, produce the shortest. If there are none produce false. mazes are small, you do not have to use tail recursion for
So (solve M1) should produce
(list (make-pos 0 0) (make-pos 0 1) (make-pos 1 1) (make-pos (make-pos 1 3) (make-pos 1 4) (make-pos 2 4) (make-pos (make-pos 4 4))
(solve M7) produces the path down the left edge and across edge of the maze since that is the shortest.
ther
L
YOU MUST COMPLETELY CONVERT THE SOLVE FUNCTION TO THIS NEW
BUT, don’t panic!! The changes required are quite few, and understand them, not that complex. It will really pay to foll think about templates and think about combination positions.
The check expects will be cumbersome. To save you time you write out the result as a list of make-pos. You can instead M1 to M7 constants to show what calling solve would produce
Be sure to edit the signature, purpose, and @template tag as
Also edit the actual function definition. Our solution makes changes to solve/p and solve/lop and adds a single new helper
Work systematically – draw pictures, think carefully about the @template, then be careful about doing that in the code.
;; Solve simple square mazes
;; Data definitions: (@htdd Maze)
;; Maze is
;; interp. ;;
;;
;;
or through ;;
(listof Boolean)
a square maze
each side length is (sqrt (length
true (aka #t) means open, can move through this false (aka #f) means a wall, cannot move into
a wall
(define O #t) ;Open (define W #f) ;Wall
o
(define M1
(list O W W W W
OOWOO WOWWW OOWWW O O O O O))
(define M2
(list O O O O O
OWWWO OWWWO OWWWO O W W W O))
(define M3
(list O O O O O
OWWWW OWWWW OWWWW O O O O O))
(define M4
(list O O O O O
OWWWO OWOOO OWOWW W W O O O))
(define M5
(list O O O O O
OWOWO OOOOO OWOWO W O O W W))
(define M6
(list O O O O O
OWOWO OOOOO OWOWO W O O O O))
(define M7
(list O O O O O O O
OWWWWWO OWOOOWO OWOWOOO OWOWWWW OWOWWOO O O O O O O O))
(@htdd Pos) (define-struct pos (x y))
;;
;;
;;
;;
;;
;;
;;
;;
;; (define P0 (define P1 (define P2 (define P3
Pos is (make-pos Integer Integer)
interp.
an x, y position in the maze.
0, 0 is upper left.
the SIZE of a maze is (sqrt (length m))
a position is only valid for a given maze if:
– (<= 0 x (sub1 SIZE)) - (<= 0 y (sub1 SIZE))
;; Functions
-thereisa
(make-pos 0 0)) (make-pos 4 0)) (make-pos 0 4)) (make-pos 4 4))
true in the given cell ;in a 5x5 maze: ;upper left
;upper right
;lower left ;lower right
(@signature Maze -> Boolean)
;; produce true if maze is solvable, false otherwise ;; assume maze has a true at least in the upper left
(check-expect (solve M1) #t) (check-expect (solve M2) #t) (check-expect (solve M3) #t) (check-expect (solve M4) #t) (check-expect (solve M5) #f) (check-expect (solve M6) #t) (check-expect (solve M7) #t)
(@template encapsulated backtracking genrec arb-tree) (define (solve m)
(local [(define
S (sqrt (length m)))
(solve/p p) [(solved? p) true] [else
(solve/lop (next-ps p))]))
(solve/lop lop) [(empty? lop) false] [else
(local [(define try (solve/p (first
(if (not (false? try)) try
(solve/lop (rest lop))))]))
lop)))]
(define (cond
(define (cond
;
;; Pos -> Boolean
;; produce true if p is bottom right ;; (@template Pos)
(define (solved? p)
(and (= (pos-x p) (sub1 S)) (= (pos-y p) (sub1 S))))
;; Pos -> (listof Pos)
;; produce list Up, down, left, right, but only when they are valid
;; (@template use-abstract-fn) (define (next-ps p)
(local [(define x (pos-x p)) (define y (pos-y p))]
(filter (lambda (p1)
(and (<= 0 (pos-x p1) (sub1 S))
;within x bounds ;within y bounds ;an open square
(<= 0 (pos-y p1) (sub1 S))
(maze-ref p1)))
(list (make-pos (add1 x) y) ;R (make-pos (sub1 x) y) ;L (make-pos x (sub1 y)) ;U
(make-pos x (add1 y)))))) ;D
;; Maze Pos -> Boolean
;; produce value of the maze cell at position p ;; (@template Pos)
(define (maze-ref p)
(list-ref m
(+ (* (pos-y p) S) (pos-x p))))]
(solve/p (make-pos 0 0))))