Index: Local state, Vectors
In the previous lab, one of our examples was the following:
Develop factorial-count! : natnum -> number, which computes the factorial of its argument. It also keeps track of how many times the user has called in function, using the variable factorial-count. It does not count any recursive calls, e.g.,
> (factorial-count! 3)
6
> factorial-count
1
> (factorial-count! 5)
120
> factorial-count
2
To solve it, you wrote something like
(define factorial-count 0)
(define (factorial-count! n)
(local [(define (factorial n)
(cond
[(zero? n) 1]
[else (* n (factorial (sub1 n)))]))]
(begin
(set! factorial-count (add1 factorial-count))
(factorial n))))
This technique of having a counter (or, more generally, a variable that keeps track of information about previous calls) is a useful tool in many situations. However, let's change the problem so that it's more useful. We would like to hide the counter factorial-count locally inside the function factorial-count!, so that nobody else can change it.
Simply adding a local definition is easy enough, but there are two big problems: we need control over when the counter is initialized, and we need some way to view the counter. To do: Write factorial-count! : ('init or 'count or natnum) -> (void or natnum). Given the argument 'init, it (re)initializes the counter to zero and returns nothing; given 'count, it returns the current count; given a number, it returns the factorial and increments the count. The input is simply a "message" indicating one of the possible actions of the function.
Hints: Part of the program just follows the three-case template for the above input type -- that should be easy. The "trick" is to define the counter in the right place in the definition. Every call to factorial-count! should use the same counter.
Here's another example. Let's model a very simple bank account. All we will remember about this account is the current balance. We need at least the ability to add and subtract from this balance for deposits and withdrawals. For withdrawals, we want to model the possibility of rejecting withdrawals when there's not enough in the account.
This time we'll make a data definition for the input message. An account-action is one of
To do: Develop account : account-action -> (void or number or 'insufficient-balance) to model a single account. The initial balance should be zero. A deposit returns void. A successful withdrawal returns void. An unsuccessful withdrawal returns 'insufficient-balance.
For the curious... How would you modify this example to simulate a bank? A bank can create a new account at any time, and such that each account has a separate balance.
Vectors are another abstraction for collections of data. Like a structure, each element of a vector is named, in this case with a number. I.e., they are named 0,1,2,3,... in order. Vectors can be of any length, although you cannot change the length of a particular vector.
Some important functions are the following:
To do: Write a function iota (this name comes from APL, I think) that, given n, creates a vector (vector 0 ... n-1).
Q: What does the following return?
(local [(v (vector 0 3 7 1 9))]
(for-each (lambda (i) (vector-set! v i (* i i)))
(list 0 2 4))
v)
To do: Write a function that given a vector, returns a new vector of the same length of the squares of the numbers in the original vector. For the curious... Try to find two or more completely different ways to do this.