Week 10 Set a

Due Date Monday 11/5 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 check 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))

; check : Type X -> X

; ensures the argument x behaves like the type,

; erroring otherwise (either immediately or when used)

(define (check 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

(check (pair-ty-fst type) (pair-fst x))

(check (pair-ty-snd type) (pair-snd x)))

(err 1))]

[(fun-ty? type)

(if (procedure? x)

(lambda (y)

(local ((define _ (check (fun-ty-arg type) y)))

(check (fun-ty-ret type) (x y))))

(err 1))])))

(check-expect (check Number 1) 1)

(check-error (check Number "hi"))

(check-expect (check Boolean #true) #true)

(check-expect (check String "hi") "hi")

(check-error (check String 34))

(check-expect (check (Pair-of Number Number) (make-pair 1 2)) (make-pair 1 2))

(check-error (check (Pair-of Number String) 1))

(check-expect ((check (Function Number Number) (lambda (x) x)) 1) 1)

(check-error ((check (Function Number Number) (lambda (x) x)) "hi"))

(check-error ((check (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 (check (Function Number Boolean)

(lambda (x)

(cond

[(<= x 0) "nonpositive"]

[(> x 0) "positive"]))))

Exercise 3 Extend the Type data definition and the check function to handle lists (i.e., [List-of Number], [List-of [Number -> String]], etc). Use check 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 check function so that it uses type->string when it produces error messages, so that the errors you get are easier to read.