Tutorial 6: Recursion, Lists, and Tally Sets (October 17-19, 2007)
In this week's tutorial, we'll be using recursion to write functions that consume and/or produce numbers in two different representations. First we will use the built-in numbers in Scheme and write our own versions of some of the basic arithmetic functions. Then we will use a list-of-lists representation which corresponds to writing tally sets. The material covered here is from lecture module 6 in the course notes (the last module which will be covered on your second midterm).
In the starter code for this tutorial (t6-starter.scm), one constant,
Using only the functions above and the ones you write (no other built-in Scheme functions), give definitions for the following functions, whose behaviour should correspond to the behaviour of the standard Scheme functions. You'll probably want to implement them in the order they're given below.
You may also assume that all numbers consumed and produced are non-negative integers. So for example the second argument to
A more primitive way of writing numbers than the Arabic numerals we are used to is tally sets. These are just collections of lines, usually structured in groups of 5, with at most one incomplete group. The number represented by a tally set is just the number of lines in the set.
To represent a tally set in Scheme, we will use a list of non-empty lists of
Write the functions
Change the definitions of the constant
Using only the functions
Now, using the definition of a natural number as either 0, 2 times a natural number, or 2 times a natural number plus 1, rewrite your definition of