Lab 6 Designing and Using Abstractions

Description

P

urpose: The purpose of this lab is to you some hands-on experience with lists of structures, structures of lists, and abstracting similarities.

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

Exercise (Reviewed) 1 Consider the following two data definitions:

; A ListOfString (LOS) is one of:

; – empty

; – (cons String LOS)

; A ListOfNumber (LON) is one of:

; – empty

; – (cons Number LON)

Design a data definition which abstracts these two definitions. Redefine ListOfString and ListOfNumber using your abstraction.

Exercise 2 Consider the following two data definitions:

; A MaybeString is one of:

; – #false

; – String

; A MaybePosn is one of:

; – #false

; – Posn

Design a data definition which abstracts these two definitions. Redefine MaybeString and MaybePosn using your abstraction.

Exercise (Reviewed) 3 Consider the following two function definitions:

; matching-x-posn : [List-of Posn] Number Posn -> Posn

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

; if no such position can be found

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

(check-expect

(matching-x-posn

(cons (make-posn 1 2) (cons (make-posn 3 4) ‘())) 3 (make-posn 5 6))

(make-posn 3 4))

(define (matching-x-posn lop desired-x default)

(cond [(empty? lop) default]

[(cons? lop)

(if (= (posn-x (first lop)) desired-x)

(first lop)

(matching-x-posn (rest lop) desired-x default))]))

; string-with-length : [List-of 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

(check-expect (string-with-length ‘() 10) “no such string”)

(check-expect (string-with-length (cons “hi” (cons “hello” (cons “aloha” ‘()))) 5) “hello”)

(define (string-with-length los desired-length)

(cond [(empty? los) “no such string”]

[(cons? los)

(if (= (string-length (first los)) desired-length)

(first los)

(string-with-length (rest los) desired-length))]))

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.

Designing with Self-Referential Data (Revisited)

Consider the following self-referential data definition for natural numbers:

; A Nat is one of:

; – 0

; – (add1 Nat)

Note that this definition is different from one you may have seen in lecture. Your TAs will discuss the parallels at the start of the lab.

Exercise 4 Create a template for the data definition given above. If you are struggling with this please see the design recipe page on the course website.

Exercise 5 Design the function even-nat? which takes a Nat and returns #true if the Nat is an even number. Yes, zero is even. You may not use even? or odd? to write this function.

Exercise 6 Design the function nat+ which takes two Nats and returns their sum. You may not use + to write this function.

Counters

Starter Code: Consider the following data definitions and functions:

; A Pair is a (make-pair String PosInt)

; and represents an element with a non-zero count

(define-struct pair [element value])

(define (pair-temp p)

(… (pair-element p) … (pair-value p) …))

; A Counter is one of:

; – ‘()

; – (cons Pair Counter)

; and represents a multiset (a set of elements where

; an element can appear more than once)

(define (counter-temp counter)

(cond [(empty? counter) …]

[(cons? counter) (… (pair-temp (first counter))

… (counter-temp (rest counter))

…)]))

(define marble-bag (list (make-pair “green” 2) (make-pair “red” 5)))

; marble-bag represents a bag with 2 “green” marbles and 5 “red” ones

; get : Counter String -> PosInt

; Get the count of the given element

(define (get counter element)

(cond [(empty? counter) (error “not found”)]

[else (if (counts-element? (first counter) element)

(pair-value (first counter))

(get (rest counter) element))]))

(check-error (get (list (make-pair “cats” 3)) “dogs”) “not found”)

(check-expect (get (list (make-pair “cats” 3) (make-pair “dogs” 4)) “dogs”) 4)

; counts-element? : Pair String -> Boolean

; Does the pair hold a count for the element?

(define (counts-element? pair element)

(string=? element (pair-element pair)))

(check-expect (counts-element? (make-pair “green” 2) “green”) #true)

(check-expect (counts-element? (make-pair “red” 5) “blue”) #false)

Sample Problem Design the function add-to-counter, which given a Counter and an element will add 1 to the previously associated count. If that element was not present, its count will be 1.

; add-to-counter : Counter String -> Counter

; Add one to the count associated with element or set it to 1

; if it hasn’t been seen before

(check-expect (add-to-counter ‘() “blue”) (list (make-pair “blue” 1)))

(check-expect (add-to-counter marble-bag “red”)

(list (make-pair “green” 2) (make-pair “red” 6)))

(check-expect (add-to-counter marble-bag “green”)

(list (make-pair “green” 3) (make-pair “red” 5)))

(define (add-to-counter counter element)

(cond

[(empty? counter) (list (make-pair element 1))]

[(cons? counter) (if (counts-element? (first counter) element)

(cons (increment-value (first counter))

(rest counter))

(cons (first counter)

(add-to-counter (rest counter) element)))]))

; increment-value : Pair -> Pair

; Increment the value in pair

(check-expect (increment-value (make-pair “green” 2)) (make-pair “green” 3))

(check-expect (increment-value (make-pair “red” 5)) (make-pair “red” 6))

(define (increment-value pair)

(make-pair (pair-element pair) (add1 (pair-value pair))))

Exercise 7 Design the function total-size, which grabs the total count of elements in a Counter (there are 7 in marble-bag).

Exercise 8 Design the function initiate-counter, which given a String creates a Counter with one copy of that element. Be sure to follow the data definition.

Exercise 9 Design the function all-elements, which outputs a ListOfString containing all of the elements a Counter has counted so far. For example, the output of (all-elements marble-bag) would be (list “green” “green” “red” “red” “red” “red” “red”).

Hint: Notice that every PosInt is also a Nat; this may be helpful.

Exercise 10 Design the function highest-count, which returns the highest count for a single element in a Counter. If the counter is empty, return 0.