SI413: Symbols and Lists

Symbols

In Scheme, we have an unusual datatype: the symbol. For example. Suppose I define the function fib as we would for Lab 1. If I ask the interpreter to evaluate the "symbol" fib, it'll tell me that fib is a name for a function:

> fib
#<procedure:fib>
>

So, the symbol fib has a special meaning. We can tell the interpreter not to evaluate the symbol by "quoting" it, which means either writing (quote fib) or, more commonly, by putting a ' in front of the symbol, i.e. 'fib. Here's a sample interpreter session:

> fib
#<procedure:fib>
> 'fib
fib
>

All this is strange, I know, but here's an example. The function inches defined below does some basic conversions into inches, and returns the symbol error if the input units are unknown. [Note: equal? is sort of a universal equality test in scheme. It works with symbols and with lists (see below). The = operator only works with numbers.]:


> (define (inches x u) 
    (if (equal? u 'inches) x (if (equal? u 'feet)
                                 (* x 12)
                                 (if (equal? u 'yards)
                                     (* x 36)
                                     'error))))
> (inches 0.5 'feet)
6.0
> (inches 0.5 'yards)
18.0
> (inches 0.5 'meters)
error
> (inches 0.5 yards)
 reference to undefined identifier: yards
>

Notice what happens when I forget to quote yards - the interpreter tries to evaluate the symbol yards in order to get the arguements forinches, and of course that name is undefined. Note: this function definition would be alot cleaner if we used cond!

Problem: Currency Conversion
Write a function convert that takes an amount a "from" currency and a "to" currency and converts the amount of the "from" currency to the monetary equivalent in the "to" currency. The currencies you use should be euro, usdollar, yen, and ukpound.

> (define (round100 x) (/ (round (* x 100)) 100.0)) ← include this definition in scheme02.scm (otherwise the grader won't give you credit!)
> (round100 (convert 3.50 'usdollar 'euro))
2.83
> (round100 (convert 25.00 'yen 'ukpound))
0.13

Here are the conversion rates you should use:

1 British Pound (GBP) = 1.78250 US Dollar and 1 US Dollar (USD) =  0.56101 British Pound
1 Euro (EUR) = 1.23510 US Dollar and 1 US Dollar (USD) =  0.80965 Euro
1 Japanese Yen (JPY) = 0.009321 US Dollar and 1 US Dollar (USD) =  107.290 Japanese Yen

Lists

The primary data structure in scheme is the list. In fact, everything you've entered into Scheme thus far is a list (duh), only you've always asked the compiler to evaluate that list. Lists stay lists when you instruct the interpreter not to evaluate them ... and of course we already know how to tell the interpreter not to evaluate something:

> (+ 3 4 5)
12
> '(+ 3 4 5)
(+ 3 4 5)
>

So, we can easily construct any list we want by simply quoting and typing away. For example

> '(A B C)
(A B C)
> '( 1 (1) ((1)))
( 1 (1) ((1)))
> '(( + 3 4) (* 3 4))
(( + 3 4) (* 3 4))
>

This last example is an interesting one. Suppose we were looking to have (7 12) returned instead of (( + 3 4) (* 3 4))? In other words, suppose we wanted the two subexpressions in the list to be evaluated? Well, by quoting the list, we ensure that nothing gets evluated. However, there's an alternative to quoting. We can construct lists using the list function, which takes its arguments and forms a list from them.

> (list (+ 3 4) (* 3 4))
(7 12)
>

Since (+ 3 4) and (* 3 4) are unquoted arguments to functions, they're evaluted before they're passed on to the list function. Thus, list is passed 7 and 12, and forms a list with those two values. This is useful if you want a function to return more than one value. You can simply have it return a list of values.

Example: Write a function zeros that computes the zeros of a quadratic polynomial a x^2 + b x + c. Assume zeros is simply passed a, b and c. You can use the quadratic formula to compute the roots: (-b +/- sqrt(b^2 - 4 a c)) / (2a). We actually have two values to return, because of the +/-. Here's how you might implement zeros:
(define (zeros a b c)
  (let ((d (sqrt (- (* b b) (* 4 a c)))) (nb (- b)))
    (list (/ (+ nb d) (* 2 a)) (/ (- nb d) (* 2	a)))))

The thing about list, is that the length of the list you return is fixed. What if we wanted to create a function that returns lists, but we don't know ahead of time how long a list? What if we'll want to simply keep adding things to the list as we go along? The cons function takes an object x and a list L and returns the list you get by adding x to the front of L.

> (cons 3 '(5 9 11))
(3 5 9 11)
> (cons 3 '( (5) (7) (9) ))
(3 (5) (7) (9))
> (cons '(1 1) '( (1 1 1) (1 1 1 1) ))
((1 1) (1 1 1) (1 1 1 1))
> (cons 'the '())
(the)
> (cons 'the (cons 'end '()))
(the end)
>

Notice that we can construct lists by multiple cons's starting with '(), the empty list.

Example: Write a function range that takes two arguments i and j and returns the list i, i+1, i+2, ..., j.
> (define (range i j) (if (> i j) '() (cons i (range (+ i 1) j))))
> (range 1 10)
(1 2 3 4 5 6 7 8 9 10)
> 
Interestingly, all we'd have to do is to stick a + at the head of this list and we'd have an expression for the sum of the first 10 integers.
> (cons '+ (range 1 10))
(+ 1 2 3 4 5 6 7 8 9 10)
> 
The only problem, is that what we have is data, a list like any other. The interpreter doesn't look to see that this particular list would make sense as an expression to be evaluated. However, we can tell the interpreter to evaluate a piece of data as if it were an expression typed into the interpreter with the eval function.
> (eval (cons '+ (range 1 10)))
55
> 
In other words, we can take a piece of data, and turn it into a piece of code! That's pretty cool.

Not surprisingly, when we construct lists by repeated cons-ing, we run into recursion!

There's one more standard function for building lists: append. Appending lists means building a new lists whose elements are those of the first list followed by those of the second list. For example:

> (append '(1 2 3) '(a b c))
(1 2 3 a b c)

Not surprisingly, append can take an arbitrary number of list arguments, e.g.

> (append '(a) '(b c) '(d e f) '(g h i j))
(a b c d e f g h i j)

It's important to understand the difference between list, cons and append. Keep this example in mind:

> (list '(a b c) '(1 2 3))
((a b c) (1 2 3))
> (cons '(a b c) '(1 2 3))
((a b c) 1 2 3)
> (append '(a b c) '(1 2 3))
(a b c 1 2 3)

Picking lists apart

Now that we've seen some examples of returning lists from function, it's obvious to ask about passing lists as arguments into functions. Well, of course, it's no different than passing other kinds of arguments to functions. However, to do something with a list that's passed as an argument, you need to be able to pick the list apart. The two functions you need for this are car, which returns the first element in a list, and cdr, which returns the sublist of everything but the first element in the list. Performing either of these on an empty list is a bad idea!

> (car '(a b 4 () 2.1))
a
> (cdr '(a b 4 () 2.1))
(b 4 () 2.1)
>

Together, car and cdr are kind of like an inverse cons:

> (let ((L '(a b c d)))
    (cons (car L) (cdr L)))
(a b c d)
>

Now we can do a whole bunch of interesting things with lists. Note: To test whether or not a list is empty, you can either use the predicate (function returning T/F) null? like this: (if (null? L) ...) , or use the general equality predicate equal? like this: (if (equal? L '()) ...). Here's a function for computing the length of a list:


(define (my-length L) (if (equal? L '()) 0 (+ 1 (my-length (cdr L)))))

although, length already exists in scheme! Here's a function that sums all the even numbers in a list. Note: even? and odd? are builtin to Scheme.

(define (sum-even L) (if (equal? L '()) 
                         0
                         (let ((n (sum-even (cdr L))))
                           (if (even? (car L)) (+ n (car L)) n))))

Things get really interesting when we have nested lists. It takes cars of cdrs of cars of cdrs to get to data sometimes!

Aside: Global variables scheme style

So far we've created functions whose names are global identifiers, meaning that the function's name is known to the interpreter from the time of the function's definition until the interpreter exits or is reset. We can also define global identifiers for data, i.e. global variables. Don't go nuts with this kind of thing though. I'm bringing it up mostly to play with lists a little more easily.

In Scheme you end up doing things like "the car of the cdr of the car of L", which gets to be quite a hassle. Scheme has a nice abbreviation for such nested calls. An expression like (car (car (cdr L))) can be written equivalently as (caadr L). Here's how it works:

(car (car (cdr L))) condenses to (caadr L)

Now, using our newfound global variables (ugh!) we can play with this a bit:

> (define L '( (1 2 3) (a b c) ((x) (x x) (x x x)) ))
> (car L)
(1 2 3)
> (car (cdr L))
(a b c)
> (car (car (cdr L)))
a
> (caadr L)
a
> (car (cdr (cdr (car L))))
3
> (caddar L)
3
>

List Problem Set

It is impossible to overstate the importance of lists in Scheme! What follows are a series of excercises to give you some practice using them. Remember: You need to use recursion to cycle through the elements of a list! ... Sorry about that.

Tips

Write a program called tip that takes an amount and returns a list of two values, the first being the amount plus a 15% tip, the second the amount plus a twenty percent tip.

> (tip 30)
(34.5 36.0)
>

List of Squares

Write a function squares that takes integers i and j and returns list of the squares i^2, (i+1)^2, ..., (j-1)^2, j^2.

> (squares 2 12)
(4 9 16 25 36 49 64 81 100 121 144)
>

More tips

Write a function called tip-range that takes an amount, and two integers defining a range of tip percentages and prints the amount + tip for each integer percentage in the range.

> (tip-range 34.50 10 25)
(37.95 38.295 38.64 38.985 39.33 39.675 40.02 40.365 40.71 41.055 41.4 41.745 42.09 42.435 42.78 43.125)
>

Simple List Pick Aparts

Write a function called sum-abs that takes a list of numbers and returns the sum of the absolute values of the elements in the list. Note: abs is the absolute value function in scheme!

(sum-abs '(-3 2 11 -5))
21

Nested Lists, simple Pick Aparts

If you're faced with nested lists, you sometimes need cars of cdrs, and cdrs of cars, and so forth.

> (define L '( (4 a) (3 x) (3 11 4)))
> (car (cdr L))
(3 x)
> (car (cdr (car (cdr L))))
x
>

Define L to be the following ugly list: ( (a x 2) (("the") b c) (z 12)). In other words, do the following:

> (define L '( (a x 2) (("the") b c) (z 12)))

Now, write car/cdr expressions to pick apart L to get the following values:

the a in L
the "the" in L
the 12 in L

Count cash!

Write a function called sum-cash that returns the value in US dollars of a collection of amounts of different currencies (same currencies as above). The amounts will be given in a list L, such that each element of L is itself a list, whose first element is an amount and whose second element is a currency name. So, for example,

( (12.20 usdollar) (340 yen) (8.50 euro) )

as an arguement to sum-cash would mean adding 12.20 dollars, 340 yen and 8.50 euros, and giving the total in dollars. Here's an example:

> (sum-cash '((12.20 usdollar) (340 yen) (8.50 euro)))
25.86749
>

Top-down design in Scheme: standard deviation

Write a function called std-dev that takes a list of numbers and returns their standard deviation. (Recall: std dev of $x_1, x_2, \ldots, x_n$ is $\sqrt{\frac{(x_1-u)^2 + (x_2-u)^2 + \cdots + (x_n - u)^2}{n-1}}$ ... where u is the average of $x_1, x_2, \ldots, x_n$. When you write this function, use top-down design. In scheme this means writing the std-dev function using functions you wish were already defined, then going back and defining them later. Example:

> (std-dev '(34 18 25 23 29 11 28 24 27 29))
6.460134157533676