4 Natural Numbers and Counters

Purpose: The purpose of this lab is to practice designing programs using natural numbers and counters to prepare you for the next homework.

Textbook references:

Chapter 9: Designing with Self-Referential Data Definitions

Expanding Conciousness

Goals: Learn to look at numbers and recursion in a new way.

Starter Code: Below is a data definition which shows how natural numbers can be built up recursively.

; A Nat is one of:

; - 0

; - (add1 Nat)

(define nat0 0)

(define nat1 (add1 nat0))

(define nat2 (add1 nat1))

; nat-temp : Nat -> ?

(define (nat-temp nat)

(cond

[(zero? nat) ...]

[(positive? nat) (... (nat-temp (sub1 nat)) ...)]))

Sample Problem Design the function double which doubles a Nat. As we are following the Nat template, you may only use the functions mentioned above, cond, and double (no + or *).

; double : Nat -> Nat

; Double the Nat

(define (double nat)

(cond

[(zero? nat) 0]

[(positive? nat) (add1 (add1 (double (sub1 nat))))]))

(check-expect (double nat0) 0)

(check-expect (double nat1) 2)

(check-expect (double nat2) 4)

Exercise 1 Design the function even?/nat which deterimes if a Nat is even. You may only use the functions mentioned above, as well as cond, not, and even?/nat. Your code must follow the template exactly, and therefore two successive calls to sub1 is forbidden.

Exercise 2 Design the function nat+ which sums two Nats. You may only use the functions mentioned above, as well as cond and nat+ (no +).

Switch pair programming roles before continuing!

Exercise 3 Design the function nat* which multiplies two Nats. You may only use the functions mentioned above, as well as cond, nat+, and nat* (no *).

Exercise 4 Design the function factorial which computes the factorial of a natural number. You may only used the functions mentioned above, cond, nat*, and factorial.

Switch pair programming roles before continuing!

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])

; 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 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

(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)))]))

(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)))

; increment-value : Pair -> Pair

; Increment the value in pair

(define (increment-value pair)

(make-pair (pair-element pair) (add1 (pair-value 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))

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

Exercise 6 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.

Switch pair programming roles before continuing!

Exercise 7 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 8 Design the function highest-count, which returns the highest count for a single element in a Counter. If the counter is empty, return 0.

Brief Aside on Mappings

Our Counter definition is actually a specialized version of a mapping. It’s a mapping from Strings to their counts; that is, it keeps track of a count for each individual String.

Mappings are everywhere in computer science, and most "real" programming languages will come with them baked-in (where they might also be called dictionaries, hash maps, associative arrays, etc.), along with functions that let you work with them. You’ll see more general and useful mappings very soon.

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.

Bonus Exercise

Exercise 9 Design the function counter-, which "subtracts" one Counter from another. That is, if other-marbles contains 4 red, 1 blue, and 2 green marbles, (counter- marble-bag other-marbles) should return (list (make-pair "red" 1)).