Lab 6 Designing and Using Abstractions

Purpose: 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.