Week 10 Set a
Due Date Monday 11/4 at 9:00pm (Week 10)
Purpose To further extend recursive thinking & think more about signatures.
Finger Exercises
Exercise 1 Design a function which inserts a given element into a given list at a given index. This index represents the element’s position in the newly created list and does not replace any of the old ones.
Graded Exercises
Exercise 2 Design a function which given a list outputs a list of all permutations (orderings) of the input list. Assume the input list has no duplicate entries.
Types and Obligations
In lecture, we defined a Type data definition and a enforce function that we used to enforce what was specified in our signatures. The code we wrote in class is the following:
(define-struct pair [fst snd]) ; a [Pair-of A B] is a (make-pair A B) ; A Type is one of: ; - 'number ; - 'boolean ; - 'string (define-struct pair-ty [fst snd]) ; - (make-pair-ty Type Type) (define-struct fun-ty [arg ret]) ; - (make-fun-ty Type Type) ; Interpretation: a Type represents different types of data we use in our programs. ; In particular, these are some of the types we write in our signatures. (define (type-temp type) (cond [(equal? type 'number) ...] [(equal? type 'boolean) ...] [(equal? type 'string) ...] [(pair-ty? type) (... (type-temp (pair-ty-fst type)) ... (type-temp (pair-ty-snd type)) ...)] [(fun-ty? type) (... (type-temp (fun-ty-arg type)) ... (type-temp (fun-ty-ret type)) ...)])) (define Number 'number) (define Boolean 'boolean) (define String 'string) (define (Pair-of A B) (make-pair-ty A B)) (define (Function X Y) (make-fun-ty X Y)) ; enforce : Type X -> X ; ensures the argument x behaves like the type, ; erroring otherwise (either immediately or when used) (define (enforce type x) (local ((define (err _) (error "the type didn't match: " x " : " type))) (cond [(equal? type 'number) (if (number? x) x (err 1))] [(equal? type 'boolean) (if (boolean? x) x (err 1))] [(equal? type 'string) (if (string? x) x (err 1))] [(pair-ty? type) (if (pair? x) (make-pair (enforce (pair-ty-fst type) (pair-fst x)) (enforce (pair-ty-snd type) (pair-snd x))) (err 1))] [(fun-ty? type) (if (procedure? x) (lambda (y) (local ((define _ (enforce (fun-ty-arg type) y))) (enforce (fun-ty-ret type) (x y)))) (err 1))])))
UPDATE: The above enforce function we gave you contains a mistake. In the last branch of the conditional, when (fun-ty? type), if x is a procedure, then we should return the following lambda:
(lambda (y) (local ((define arg (enforce (fun-ty-arg type) y))) (enforce (fun-ty-ret type) (x arg)))) Extra Credit Exercise: We didn't discover the mistake in enforce because we didn't have enough tests. Write a test that enforces a signature on some function such that the test would have erroneously passed with the original version of enforce we gave you. When you run your test with the updated version of enforce, it will correctly enforce the signature and report that the type didn't match.
(check-expect (enforce Number 1) 1) (check-error (enforce Number "hi")) (check-expect (enforce Boolean #true) #true) (check-expect (enforce String "hi") "hi") (check-error (enforce String 34)) (check-expect (enforce (Pair-of Number Number) (make-pair 1 2)) (make-pair 1 2)) (check-error (enforce (Pair-of Number String) 1)) (check-expect ((enforce (Function Number Number) (lambda (x) x)) 1) 1) (check-error ((enforce (Function Number Number) (lambda (x) x)) "hi")) (check-error ((enforce (Function Number String) (lambda (x) x)) 1))
An example where we used this to find a bug where our implementation did not match our signature is the following:
; positive : Number -> Boolean ; returns whether number is positive (define positive (enforce (Function Number Boolean) (lambda (x) (cond [(<= x 0) "nonpositive"] [(> x 0) "positive"]))))
Exercise 3 Extend the Type data definition and the enforce function to handle lists (i.e., [List-of Number], [List-of [Number -> String]], etc). Use enforce to rewrite the following two functions to enforce the signatures (you should rewrite them in the same way that positive was rewritten above, and running them on input should produce an error telling you what was wrong – but do not correct the functions):
; sum-list : [List-of Number] -> Number ; Adds up the numbers in the list (define (sum-list lon) (cond [(empty? lon) 0] [(cons? lon) (+ (first lon) (sum-list (first lon)))])) ; contains-frog? : [List-of String] -> Boolean ; Returns whether or not the list contains "frog" (define (contains-frog? los) (cond [(empty? los) "false"] [(cons? los) (or (string=? (first los) "frog") (contains-frog? (first los)))]))
Exercise 4 Design the function type->string that, given a Type, returns a string that contains the type as it would appear in a signature. Some tests (among others) that it should satisfy:
(check-expect (type->string String) "String") (check-expect (type->string (Pair-of Number Boolean)) "[Pair-of Number Boolean]") (check-expect (type->string (Function (Function Number Number) String)) "[[Number -> Number] -> String]") Now fix the enforce function so that it uses type->string when it produces error messages, so that the errors you get are easier to read.