3 Natural Numbers and Counters

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

Textbook references:

Chapter 9: Designing with Self-Referential Data Definitions

LANGUAGE SHOULD BE #lang htdp/isl

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

; A Nat is one of:

; - 0

; - (make-next Nat)

(define N0 0)

(define N1 (make-next N0))

(define N2 (make-next N1))

; nat-temp : Nat -> ?

(define (nat-temp nat)

(cond

[(and (number? nat) (zero? nat)) ...]

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

Interlude: Checked Signatures

Signatures are the first part of the design recipe for a reason—they are the most important—and correspondingly, if there is a problem in code, they are the first place to look. With checked signatures, some of that checking can be automated.

The first checked signatures we will see are ones for built-in atomic data. For example:

(: my-add (Number Number -> Number))

; adds two numbers together

(define (my-add x y)

(+ x y))

Note that the signature line is now code, rather than a comment, and signatures are created with a new language feature : that takes the name of a function and then a signature, which should be, in paretheses, a series of data types (signature values), followed by an arrow, followed by the return type.

Exercise 1 Try typing that definition in, and calling my-add with something other than numbers. What happens? What if the function was:

(: my-first (Number Number -> Number))

; returns the first argument passed in

(define (my-first x y)

x)

What do you think will happen if you call that with (my-first #f #t)? What about (my-first 10 #t)? Why? How is this different (if at all) to when signatures were in comments.

For data definitions, there are two main ways of building signatures: enum and mixed. The first, enum, is used to build a signature out of a collection (possibly 1) of values. For example:

(define ZeroOrOne (signature (enum 0 1)))

(: zoo-add1 (ZeroOrOne -> Number))

; adds one to the given input

(define (zoo-add1 x)

(+ x 1))

When defining named signatures, we use a normal define to create a constant, but the value is a signature value, identified with signature to indicate that it is a signature definition, rather than a normal value. The naming convention should match normal data definition names: capitalized words (this makes it easy to keep them distinct from constant values, which are all caps, and functions, which are all lowercase).

Exercise 2 What happens if you pass 2 to zoo-add1? What about if you change Number to ZeroOrOne – will it work? Always?

Once we have enumerated signatures, we can combine them to make mixed signatures (these are "itemizations"). For example:

(define ListOfZero (signature (mixed EmptyList [ConsOf (enum 0) ListOfZero])))

; ALTERNATIVE

; (define ListOfZero (signature [ListOf (enum 0)]))

(: loz-length (ListOfZero -> Number))

; returns the length of the given list

(define (loz-length l)

(cond [(empty? l) 0]

[(cons? l) (add1 (loz-length (rest l)))]))

This signature is different from the previous ones – first, it uses ConsOf, which is a signature that takes a signature value as an argument. Secondly, it is self referential!

Note that this pattern is quite common, so there is a built-in shorthand to define signatures like that:

(define ListOfZero (signature [ListOf (enum 0)]))

Exercise 3 Try experimenting with this function. What values can you pass it? Does it follow the template? Note how, just as with signatures in comments, some signatures are parametric: List is not a signature, but ListOf T, where T is the signature of elements, is.

Switch pair programming roles before continuing!

As it turns out, ListOf is only barely special: any struct you define creates a parametric signature that you can use to build data definitions with. This means we can define our original Nat example as:

(define-struct next [prev])

(define Nat (signature (mixed (enum 0) [NextOf Nat])))

(define N0 0)

(define N1 (make-next nat0))

(define N2 (make-next nat1))

(: nat-temp (Nat -> Any))

(define (nat-temp nat)

(cond

[(and (number? nat) (zero? nat)) ...]

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

The last type of signature you might need to create (primarily for dealing with existing code) is with predicate. This turns a function that returns true or false into a signature. For example:

(define Image (signature (predicate image?)))

(As a side note: supporting this type of signature is why we had to switch to ISL. All the rest are supported by BSL; we could have started using them on the first day).

Back to Regular Programming

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

(: zero?/nat (Nat -> Boolean))

; outputs whether a nat is zero

(define (zero?/nat nat)

(and (number? nat) (zero? nat)))

(check-expect (zero?/nat N0) #true)

(check-expect (zero?/nat N1) #false)

(check-expect (zero?/nat N2) #false)

(: double (Nat -> Nat))

; Double the Nat

(define (double nat)

(cond

[(zero?/nat nat) 0]

[(next? nat) (make-next (make-next (double (next-prev nat))))]))

(check-expect (double N0) 0)

(check-expect (double N1) (make-next (make-next 0)))

(check-expect (double N2) (make-next (make-next (make-next (make-next 0)))))

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

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

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

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

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

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

Switch pair programming roles before continuing!

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

Exercise 8 Design the function factorial which computes the factorial of a natural number.

Switch pair programming roles before continuing!

Counters

Starter Code: Consider the following data definitions and functions:

(define-struct pair [element value])

(define Entry (signature [PairOf String Number]))

; represents an element with a count

(define (pair-temp p)

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

(define Counter [ListOf Entry])

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

; 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? (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) (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 (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 grabs the total count of elements in a Counter (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 (list "green" "green" "red" "red" "red" "red" "red").

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

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 Exercise

Exercise 13 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)).