Lab 10: Abstracting data definitions

You may submit this lab to lab10 on Handin (this is optional).

Note: Whenever you write a function in this class, follow the design recipe. You will be graded accordingly.

1 Grouping similar functions

Exercise 1. Team up and do this lecture exercise with your teammates.

2 Similar data definitions

Exercise 2. Write a data definition for a ListOfStrings.

Exercise 3. Write a data definition for a ListOfListOfNumbers.

Exercise 4. Compare these two data definitions. How are they similar? How are they different?

3 Abstracting a list data definition

We would like to abstract over both of these definitions so that we no longer need to write a ListOf_____s definition each time we would fill in that blank a different way. And, more importantly, we would like to design functions which work on all kinds of lists.

We will do this as follows. We will replace the dissimilarity in the data definitions from Exercises 2 and 3 with a variable like X or Y. We will treat ListOf as kind of operator which produces a data type. And we will informally “apply” this operator using square brackets. Here is the result:

; a [ListOf X] is one of:

; - empty

; - (cons X [ListOf X])

We will now assume that [ListOf X] is common knowledge in this class. And so it is no longer necessary in this class to give data definitions for lists of things. For example, a list of strings has type [ListOf String].

Exercise 5. Using [ListOf X], rewrite the following signatures:

count-all-words : ListOfStrings -> ListOfFrequencies

map-rot13 : ListOf1Strings -> ListOf1Strings

Exercise 6. Use [ListOf X] to define lists of lists of numbers.

Exercise 7. Finish writing the template for processing a [ListOf X].

; process-lox : [ListOf X] -> ...

(define (process-lox lox) ...)

Exercise 8. Write the signatures for cons, first and rest.

4 Abstracting a maybe data definition

Recall the following function from the Invaders game:

(define bullet-speed 2)

; a MaybePosn is one of:

; - (make-none)

; - Posn

(define-struct none [])

; move-bullet : MaybePosn -> MaybePosn

; decreases the y-coordinate of mp by bullet-speed if mp is a Posn

(define (move-bullet mp)

(cond

[(none? mp) (make-none)]

[(posn? mp) (make-posn (posn-x mp) (- (posn-y mp) bullet-speed))]))

(check-expect (move-bullet (make-none)) (make-none))

(check-expect (move-bullet (make-posn 100 200))

(make-posn 100 (- 200 bullet-speed)))

Now, consider the following function for safe division:

; a MaybeNumber is one of:

; - (make-none)

; - Number

(define-struct none [])

; safe-div : Number Number -> MaybeNumber

; returns x divided by y if y is not 0

(define (safe-div x y)

(cond

[(zero? y) (make-none)]

[else (/ x y)]))

(check-expect (safe-div 5 0) (make-none))

(check-expect (safe-div 10 2) 5)

Exercise 9. Write the data definition which is an abstraction over MaybePosn and MaybeNumber.

Exercise 10. Rewrite the signatures for move-bullet and safe-div using your abstraction.

Exercise 11. Finish writing the template for a function which processes a [Maybe X]:

; process-mx : [Maybe X] -> ...

(define (process-mx mx) ...)

Hint: Use else for the second clause.

5 Similar functions

Remember to use [ListOf X] when writing signatures in this section.

Exercise 12. Define a function hello-all which takes a list of strings and adds "hello " to the beginning of each string.

Exercise 13. What is the signature of length? Define a function list-lengths which takes a list of lists of something and returns a list of the lengths of the lists in the given list.

Exercise 14. Compare the signatures, purpose statements and definitions of hello-all and list-lengths. How are they similar? How are they different?

6 Following the abstraction design recipe

Exercise 15. In lecture this week, we designed two similar functions between-20-50 and all-contains-lorem. Here are the definitions:

; between-20-50 : ListOfNumbers -> ListOfNumbers

; returns all numbers which are between 20 and 50 (inclusive)

(define (between-20-50 lon)

(cond

[(empty? lon) empty]

[(cons? lon)

(cond

[(and (<= 20 (first lon)) (<= (first lon) 50))

(cons (first lon) (between-20-50 (rest lon)))]

[else (between-20-50 (rest lon))])]))

(check-expect (between-20-50 empty) empty)

(check-expect (between-20-50 (list 10 50 90 40 100 20 -3))

(list 50 40 20))

(check-expect (between-20-50 (list 35 50 90 40 100 20 -3))

(list 35 50 40 20))

; all-contains-lorem : ListOfStrings -> ListOfStrings

; returns all strings which contain "lorem" as a substring

(define (all-contains-lorem los)

(cond

[(empty? los) empty]

[(cons? los)

(cond

[(string-contains? "lorem" (first los))

(cons (first los) (all-contains-lorem (rest los)))]

[else (all-contains-lorem (rest los))])]))

(check-expect (all-contains-lorem empty) empty)

(check-expect (all-contains-lorem (list "plorema" "lorm" "comp115"))

(list "plorema"))

(check-expect (all-contains-lorem (list "lecture11" "noloreman" "lorm" "comp115"))

(list "noloreman"))

This was Step 1 of the abstraction design recipe. Complete the remaining steps of the abstraction design recipe. Name the abstraction filter-out.