Lab 9 Designing and Using Abstractions

Purpose: This lab will give you practice using existing list abstractions.

Textbook references: Chapter 14: Similarities Everywhere, Chapter 15: Designing Abstractions, Chapter 16: Using Abstractions

Designing Abstractions

Exercise 1 Consider the following function definitions:

; matching-x-posn : [ListOf Posn] Number Posn -> Posn

; Find the first Posn in the list with the given x-coordinate;

; return the given Posn if no such position can be found

(define (matching-x-posn pts x default)

(cond [(empty? pts) default]

[(= (posn-x (first pts)) x) (first pts)]

[else (matching-x-posn (rest pts) x default)]))

(check-expect (matching-x-posn '() 10 (make-posn 0 0))

(make-posn 0 0))

(check-expect (matching-x-posn (list (make-posn 1 2) (make-posn 3 4))

3

(make-posn 5 6))

(make-posn 3 4))

; string-with-length : [ListOf String] Nat -> String

; Returns the first String in the given list with the given length

; or "no such string" if no such string can be found.

(define (string-with-length strs len)

(cond [(empty? strs) "no such string"]

[(= (string-length (first strs)) len) (first strs)]

[else (string-with-length (rest strs) len)]))

(check-expect (string-with-length '() 10) "no such string")

(check-expect (string-with-length '("hi" "hello" "aloha") 5) "hello")

Design the function find-first-match, which abstracts these two functions. Be sure to redefine matching-x-posn and string-with-length using your abstraction.

Exercise 2 Consider the following data definitions:

(define-struct pair [x y])

; A StringPair  is a (make-pair String String)

; A NumBoolPair is a (make-pair Number Boolean)

Design a parametric data definition which abstracts these two definitions. Be sure to redefine "StringPair" and "NumBoolPair" using your abstraction.

Understanding Abstractions

Goals: Understand the signatures and purposes of each pre-defined list abstraction.

Exercise 3 Determine the signature of the following function:

(define (f x y z)

(or (andmap string-numeric?

(map x (filter positive?

(foldr append '() y)))) z))

Exercise 4 Determine the best pre-defined list abstraction to use for each of the following tasks. Have a staff member look over your answers before you continue.

• Create a list of the string-lengths of every string in a list.

• Determine whether any Posn in a list is within a some distance of (0,0).

• Given a list of strings, create a list of all the strings that begin with the prefix "CS2500: ".

• Check whether every number in a list is within a certain range.

• Given a list of Posns, create a single Posn whose x-coordinate is the sum of all the x-coordinates in the list and whose y-coordinate is the sum of all the y-coordinates in the list.

Exercise 5 What is the difference between abstracting two functions and using an abstraction?

Exercise 6 Design the function double-in-list which, given a list of Strings, returns a list with all the same strings but where each instance of "double" appears twice in a row. So, for example, given the list (list "a" "double" "c" "double"), the function would return (list "a" "double" "double" "c" "double" "double").

Exercise 7 Implement the function build-list

The build-list function is one of the more minor functional abstractions provided by DrRacket. (Try it out.) It takes two arguments: a natural number n, and a function f. It returns a list of length n; the list itself is created by

(list (f 0) (f 1) ... (f n-1))

Call your version of this function %build-list. Here are some examples of your function in action:

(check-expect (%build-list 0 sqr)   '())

(check-expect (%build-list 4 sqr)   '(0 1 4 9))

(check-expect (%build-list 4 number->string) '("0" "1" "2" "3"))

(check-expect (%build-list 5 even?) '(#t #f #t #f #t))

(check-expect (%build-list 4 list)  '((0) (1) (2) (3)))

Note that different uses of your %build-list function produce lists of numbers, lists of strings, lists of booleans, and even lists of lists. Be sure your signature for %build-list is correct for this kind of polymorphism.

Before You Go...

If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.