Description
P
urpose: The purpose of this lab is to you some handson 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:
Design a data definition which abstracts these two definitions. Redefine ListOfString and ListOfNumber using your abstraction.
Exercise 2 Consider the following two data definitions:
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:


; matchingxposn : [Listof Posn] Number Posn > Posn
; Find the first Posn in the list with the given xcoordinate or return the given Posn
; if no such position can be found
(checkexpect (matchingxposn ‘() 10 (makeposn 0 0)) (makeposn 0 0))
(matchingxposn
(cons (makeposn 1 2) (cons (makeposn 3 4) ‘())) 3 (makeposn 5 6))
(makeposn 3 4))
(define (matchingxposn lop desiredx default)
[(cons? lop)
(first lop)
(matchingxposn (rest lop) desiredx default))]))
; stringwithlength : [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
(checkexpect (stringwithlength ‘() 10) “no such string”)
(checkexpect (stringwithlength (cons “hi” (cons “hello” (cons “aloha” ‘()))) 5) “hello”)
(define (stringwithlength los desiredlength)
[(cons? los)
(if (= (stringlength (first los)) desiredlength)
(first los)
(stringwithlength (rest los) desiredlength))]))

Design the function findfirstmatch which abstracts these two functions. Be sure to redefine matchingxposn and stringwithlength using your abstraction.
Designing with SelfReferential Data (Revisited)
Consider the following selfreferential data definition for natural numbers:

; – 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 evennat? 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:

; and represents an element with a nonzero count
(definestruct pair [element value])
(define (pairtemp p)
; – ‘()
; and represents a multiset (a set of elements where
; an element can appear more than once)
(define (countertemp counter)
…)]))
(define marblebag (list (makepair “green” 2) (makepair “red” 5)))
; marblebag 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)
(pairvalue (first counter))
(get (rest counter) element))]))
(checkerror (get (list (makepair “cats” 3)) “dogs”) “not found”)
(checkexpect (get (list (makepair “cats” 3) (makepair “dogs” 4)) “dogs”) 4)
; countselement? : Pair String > Boolean
; Does the pair hold a count for the element?
(define (countselement? pair element)
(string=? element (pairelement pair)))
(checkexpect (countselement? (makepair “green” 2) “green”) #true)
(checkexpect (countselement? (makepair “red” 5) “blue”) #false)
Sample Problem Design the function addtocounter, 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.

; addtocounter : Counter String > Counter
; Add one to the count associated with element or set it to 1
; if it hasn’t been seen before
(checkexpect (addtocounter ‘() “blue”) (list (makepair “blue” 1)))
(checkexpect (addtocounter marblebag “red”)
(list (makepair “green” 2) (makepair “red” 6)))
(checkexpect (addtocounter marblebag “green”)
(list (makepair “green” 3) (makepair “red” 5)))
(define (addtocounter counter element)
(cond
[(cons? counter) (if (countselement? (first counter) element)
(rest counter))
(addtocounter (rest counter) element)))]))
; incrementvalue : Pair > Pair
; Increment the value in pair
(checkexpect (incrementvalue (makepair “green” 2)) (makepair “green” 3))
(checkexpect (incrementvalue (makepair “red” 5)) (makepair “red” 6))
(define (incrementvalue pair)
(makepair (pairelement pair) (add1 (pairvalue pair))))
Exercise 7 Design the function totalsize, which grabs the total count of elements in a Counter (there are 7 in marblebag).
Exercise 8 Design the function initiatecounter, 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 allelements, which outputs a ListOfString containing all of the elements a Counter has counted so far. For example, the output of (allelements marblebag) 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 highestcount, which returns the highest count for a single element in a Counter. If the counter is empty, return 0.