CS Project 19
	Recursively defined data. A list in Scheme.
Concepts	Activity	Homework

Review

We've finally covered all the simple data we are going to need, and we've also gotten pretty comfortable with one kind of composite data, pic, which gave directions for drawing a picture.

Now, we're going to make up some composite data of our own...

Concepts

Recursion in general

Recursion is a way of dealing with infinity.

When we define a set using "..." such as 1,3,5,7,9... we're giving a definition that is pretty comprehensible.

But it just isn't good enough-- precise enough-- for computers. For that matter, it isn't good enough for certain kinds of people, such as programmers and mathematicians and logicians.

When we define something using recursion, the definition has to have at least 2 cases.

One is called the base case. One is called the recursive case.

The base case lets the definition "stop running". Or, start running. (It depends on what you're doing, generating a recursive object, or recognizing a recursive object.)

A list of numbers that could be "any size you like".

It seems clear that lists of numbers should be useful things for computing with, so let's start our investigation of recursion right here.

lists... first, a list of numbers

We're going to define a new kind of data, A list of numbers (lon).

A list of numbers (lon) is either:

1) an empty list, which is called "empty"

2) a list of numbers (lon) with a number attached 
at the front using "cons".

This is a very informal definition, but the really remarkable thing about it is that it mentions itself.

Were you ever told by a teacher not to mention a word in its own definition?

This is called a recursive data definition.

The big idea to remember is that there has to be at least one "base case" and at least one "recursive case" in your definition.

If there's no recursive case, it isn't a recursive definition.

If there's no base case, it would try to repeat forever when we tried to follow the rule. This may not seem like a big deal to you as a human being, but it is when we code it up for a program. This is called infinite recursion. It generally makes the computer do things that are, um, not sensible...

Here are some examples of lon values:

empty

(cons 111 empty)

(cons 222 (cons 111 empty))

(cons 333 (cons 222 (cons 111 empty)))

Now they may look a little unlovely, but they aren't really for looking at.

They're for doing computations with. Recall that pic values were pretty unlovely too, and we were able to use them for pretty nifty stuff.

Now the third one should give you pause. See how it really is a legal list of numbers?

I applied rule #2 twice, and then rule #1. Get it?

You can apply the recursive rule as many times as you want.

Why cons????????

cons is short for "construct".

cons is "the list constructor function."

But Scheme programmers just call it "cons".

cons works on many kinds of data. Cons has a contract somewhat like this:

cons : some-data  list-of-some-data  ->  list-of-some-data

As you see, its contract is pretty general. It doesn't seem to much matter what kind of thing the first operand is.

Now the important thing about cons is that the second operand must be a list.

In our environment, DrScheme will enforce this requirement. Try it yourself, with (cons 'ear 'elbow) The Good Doctor won't be happy.

These structures have a different representation in the computer's memory that is very flexible, powerful, and elegant. But we don't really care about it very much in this course.

Think of (cons 222 (cons 111 empty)) as a value that is a lon.

Think of it as the "true" representation of a lon, just as we might think of 42 as the "true" representation of a number.

In both cases, there's an internal representation that works well for the particular machine we are using, and which varies somewhat from machine to machine. We aren't going to discuss that in detail in this course.

data definitions

data definitions are a very big deal for programmers.

We're going to write data definitions as comments, in other words, they're just for people to read.

Yet, if we don't do them right, our programs will fail to run.

So, here's an example of a data definition. It's a better definition of a list of numbers (lon).

A list of numbers is either 

1) empty

2) (cons n a-lon)

where 
      n is a number 
      and a-lon is a **list of numbers.

3 examples:

empty
(cons 111 empty)
(cons 222 (cons 111 empty))

You can probably see that the "where" clause is very important! That is where we explain what the data items mean, and what are legal values for them. Here are a few more.

A list of prices is either 

1) empty

2) (cons price a-lopr)

where 
      price is a number that is the price for a toy 
      (must be less than 1000.00)
      and a-lopr is a **list of prices

 3 examples:

 empty
 (cons 1.25 empty)
 (cons 29.95 (cons 1.25 empty))

In reality, we might have more rules for money amounts. Note that according to this, a price can be a rational like 1/7. If we wished, we could make a more correct money definition, but we won't do so now.

Notice how much more information about the "real world" situation we can put in a data definition.

We can use other things besides numbers, if the situation requires it:

A list of toys is either 

1) empty

2) (cons a-toy a-lotoy)

where 
   a-toy is a symbol that is the name of a toy, and 
   a-lotoy is a **list of toys.

examples:

empty

(cons 'MBABarbie empty)

(cons 'BorisBadinov 
  (cons 'SciTechBarbie 
    (cons 'MBABarbie empty)))

Note that it isn't necessary for the base case to be empty (though it very often will be in our definitions).

Here's a list that is never empty, called a "nelon"-- non-empty list of numbers. This is useful because some operations just flat don't make sense on an empy list.

A non-empty list of numbers (nelon) is either
1) (cons n empty)
2) (cons n a-nelon)

where n is a number and a-nelon is a **non-empty list of numbers.

examples:
(cons 111 empty)
(cons 222 (cons 111 empty)
(cons 333 (cons 222 (cons 111 empty)))

Activity

No programs this lesson!

Just making up some recursive data definitions, and give examples.

Generally, 3 examples will be what you need (base case, recursive case, one fancy example).

Make a file named P19.scm.

Use the models above to help you define the following list type data, and do an example for each case.

In each definitition, put ** where the recursive step is, as in the examples above. Make sure all your "where clauses" are complete.

Comment out the data definitions but leave the examples uncommented, and let Scheme evaluate 'em.

1) Define and give examples for a list of student's names.

2) Define and give examples for a list of letter grades which may be A,B,C,D, and F. Explain what values are legal in your "where clause".

3) Define and give examples for a list of quiz grades. Quiz grades are numeric, and are between 0 and 110, inclusive.

4) Define and give examples for a list of bank balances. Note that they may be negative.

5) Define and give examples for a list of piccy-graph colors. Explain what values are legal in your "where clause".

6) As we said, some operations just flat don't make sense on an empty list. So, the thing to do is to stop recursion while there is still something in the list. For example, averaging an empty list of numbers doesn't make sense. Write a data definition for a non-empty list of bank balances (nelobb). Use nelon above for a model.