3 Natural Numbers and Counters🔗

Purpose: The purpose of this lab is to practice designing programs using natural numbers and counters.

Textbook references:

Chapter 9: Designing with Self-Referential Data Definitions

LANGUAGE SHOULD BE #lang htdp/bsl

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.

(define-struct next [prev])

; An SNat (a struct-based natural number) is one of:

; - 0

; - (make-next SNat)

(define N0 0)

(define N1 (make-next N0))

(define N2 (make-next N1))

; snat-temp : SNat -> ?

(define (snat-temp snat)

(cond

[(number? snat) ...]

[(next? snat) (... (snat-temp (next-prev snat)) ...)]))

Exercise 1 If you look at it the right way, the SNat definition above looks remarkably like the following alternate definition:

; A Nat is one of

; - 0

; - (add1 Nat)

Instead of using make-next to build up bigger SNats, we use add1. Instead of using next-prev to extract the inner, smaller SNat...what built-in function do you think we should use to extract the next smaller Nat?

Write out a template for Nats. You probably want to use zero? and positive? as the predicates to examine your input number.

Working with SNats🔗

Sample Problem Design the function double which doubles a SNat. Note how this follows the SNat template!

Exercise 2 Writing numbers in this form for testing is a little laborious, so your first task is to design a function to convert from SNat to Nat. Design the utility function snat->nat with signature SNat -> Nat.

Now note you can use your function to help write check-expects, e.g., as:

(check-expect (snat->nat (double N0)) 0)

(check-expect (snat->nat (double N1)) 2)

(check-expect (snat->nat (double N2)) 4)

Exercise 3 Design the function even?/snat which determines if a SNat is even. You may only use the functions mentioned above, as well as cond, not, and even?/snat (you may not use snat->nat in your code, only in testing).

Exercise 4 Design the function +/snat which sums two SNats. As before, only use the functions mentioned above, as well as cond and +/snat (do not convert to Nat, except for in testing).

Exercise 5 Translate even?/snat and +/snat to analogous functions even?/nat and +/nat operating on Nats. Assume that Racket’s real even? and + functions don’t exist – use the nat-temp template you designed earlier instead.

Switch pair programming roles before continuing!

Exercise 6 Design the function */snat which multiplies two SNats. You may only use the functions mentioned above, as well as cond, +/snat, and */snat.

Exercise 7 Design the function factorial/snat which computes the factorial of a SNat.

Exercise 8 Translate */snat and factorial/snat to analogous functions operating on Nats. Again, assume that * doesn’t exist.

Switch pair programming roles before continuing!

Counters🔗

Starter Code: Consider the following data definitions and functions:

(define-struct pair [element value])

; An Entry is a (make-pair String Nat)

; INTERPRETATION: represents an element with a count

(define (entry-temp p)

(... (pair-element p) ... (pair-value p) ...))

Stop! Why is it called entry-temp and not pair-temp? Conversely, why does it use pair-element and pair-value, and not entry-element or entry-value?

; A Counter is one of

; - '()

; - (cons Entry Counter)

; INTERPRETATION: represents a multiset (a collection of elements

; like a set, except where an element can appear more than once)

(define (counter-temp counter)

(cond [(empty? counter) ...]

[(cons? counter) (... (entry-temp (first counter))

... (counter-temp (rest counter))

...)]))

(define marble-bag (cons (make-pair "green" 2) (cons (make-pair "red" 5) '())))

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

; get : Counter String -> Nat

; 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 (cons (make-pair "cats" 3) '()) "dogs") "not found")

(check-expect (get (cons (make-pair "cats" 3) (cons (make-pair "dogs" 4) '())) "dogs") 4)

; counts-element? : Entry 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) (cons (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") (cons (make-pair "blue" 1) '()))

(check-expect (add-to-counter marble-bag "red")

(cons (make-pair "green" 2) (cons (make-pair "red" 6) '())))

(check-expect (add-to-counter marble-bag "green")

(cons (make-pair "green" 3) (cons (make-pair "red" 5) '())))

; increment-value : Entry -> Entry

; 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 9 Design the function total-size, which computes the total count of elements in a Counter (for instance, there are 7 in marble-bag).

Exercise 10 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 11 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

Gosh this endless repetition of cons is tedious! We’ll see a shortcut for this soon enough...

(cons "green"

(cons "green"

(cons "red"

(cons "red"

(cons "red"

(cons "red"

(cons "red" '())))))))

(You must design the ListOfString data definition yourself; it should be very similar in structure to Counter...)

Exercise 12 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 for additional assistance.

Bonus Exercises🔗

Exercise 13 Design the function counter-clean, which eliminates from a Counter any Entries with counts of 0.

Exercise 14 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 (cons (make-pair "red" 1) '()). (You may find it helpful to use counter-clean for this, since both marble-bag and other-marbles had green marbles in them, but the result here doesn’t even mention that color.) Consider what you should do in the opposite case of (counter- other-marbles marble-bag) – why did you choose that, and could you design an alternative instead?

Exercise 15 Tricky! Design the function counter=, which determines if two given Counters contain the same quantities of the same element.