Lab 19: Around & Around We Go

Implement this lab with the Intermediate Student Language with Lambda.

Make sure you follow The Style we use for the {B,I,A}SL{,+} languages in this class.

Choose the initial Head and Hands, and get started!

From Signatures to Functions

A function signature describes a class of functions. Most signatures describe an infinite number of functions. The signature [Number -> Boolean] includes even?, (λ (n) (> n 0)), and (λ (n) (or (= 0 (modulo 5 n)) (even? n))).

Ex 1: Define three functions ex-1-{1,2,3} with the signature String -> Number.

Hint: Be careful: the wiseacres lab might want to give (λ (x) 0) as a function with the signature String -> Number. However, the most general signature that we can give (λ (x) 0) is [X] . X -> Number, since the input x is never used as a String. Make sure the inputs to ex-1-{1,2,3} are used as Strings in your example functions.

Ex 2: Define three functions ex-2-{1,2,3} with the signature

Number [Number -> Boolean] -> String.

Ex 3: Define two function ex-3-{1,2} with the signature

[X] . [Number -> X] -> X.

Ex 4: Define two functions ex-4-{1,2} with the signature

[X Y] . [Listof X] [X -> Number] [Number -> Y] -> [Listof Y].

From Functions to Signatures

Swap Head and Hands!

Ex 5: Provide the most general signatures for each of the following functions. If you are unsure of your answer, ask one of the pairs near you. If you are asked about your signature by some other pair, answer only "that’s what we got", "ours is more general", or "ours is less general"; don’t show them your solution.

; brillig :

(define (brillig x)

(= 1 (modulo x 2)))

; slithy :

(define (slithy m n)

(> (length m) n))

; outgrabe :

(define (outgrabe x y)

(map x (append y y)))

; uffish :

(define (uffish x)

(cond [(number? x) (+ x 10)]

[(string? x) (string-length x)]))

; frabjous :

(define (frabjous a b c)

(a (b c)))

; callooh :

(define (callooh a b)

(a 10 (or (b 0) (b 1))))

; callay :

(define (callay q)

(frabjous (λ (d) (+ d 42)) q "day"))

Abstract Operations Abound

Swap Head and Hands!

Note: You should use abstract list operations in each of the solutions of this section.

Ex 6: Design a function ex-6 that removes from a list of numbers any multiples of 6.

Ex 7: Design a function ex-7 that, given a [Listof X], a String pre and a function foo : X -> String, returns a list of strings where each X value in the given list was converted to a string and prepended with pre.

Ex 8: Design a function ex-8 that, given a list of student names, returns a list of randomly-generated grades between 0 and 100 for those students.

Abstracting Operations

Swap Head and Hands!

The recursive data definition and template for the natural numbers are as follows:

; A Natural is one of:

; - 0

; - (add1 Natural)

; Interp: The non-negative integers.

; natural-template : Natural -> ???

; The form of recursive functions over Natural numbers.

(define (natural-template n)

(cond [(= 0 n) ...]

[else (... n

...

(natural-template (sub1 n)))]))

Ex 9: The following three functions share a similar form over the Natural numbers. Design an abstraction of hyp{0,1,2} named hypN, then define hyp0/2, hyp1/2, and hyp2/2 in terms of hypN.

; hyp1 : Number Number -> Number

; The first hyperoperation over natural numbers.

(define (hyp1 a n)

(cond [(= 0 n) a]

[else (add1 (hyp1 a (sub1 n)))]))

; hyp2 : Number Number -> Number

; The second hyperoperation over natural numbers.

(define (hyp2 a n)

(cond [(= 0 n) a]

[else (+ a (hyp2 a (sub1 n)))]))

; hyp3 : Number Number -> Number

; The third hyperoperation over natural numbers.

(define (hyp3 a n)

(cond [(= 0 n) a]

[else (* a (hyp3 a (sub1 n)))]))

Ex 10: Define the fourth hyperoperation over natural numbers hyp4 : Number Number -> Number in terms of hypN.

Ex 11: Design the function foldu : [X] . [Natural X -> X] X Natural -> X. If you get stuck look at the natural-template and consider the implementation of foldr over lists from your notes. Your implementation should pass the tests below.

(check-expect (foldu cons '() 3) '(3 2 1))

(check-expect (foldu * 1 5) 120)

(check-expect (foldu (λ (n s) (string-append (number->string n) " " s))

"0"

10)

"10 9 8 7 6 5 4 3 2 1 0")

Ex 12: Define the function hypN/2 in terms of foldu.