Scheme Programming/List Operations

From Wikibooks, open books for an open world
< Scheme Programming
Jump to: navigation, search

Creating Lists[edit]

One of more powerful features of Scheme is it's ability to process 'Lists' of data.

Lists are constructed by using the cons keyword, as is shown here:

> (cons 1 '())
(1)

cons creates a 'Pair' of values. However, if the last parameter of cons is a list (as the empty list, '() is) then it generates a list of 2 values. Knowing this, we can generate an infinitely long list using cons

> (cons 1 (cons 2 (cons 3 '())))
(1 2 3)

Helpfully, there is a shortcut to creating a list, the list keyword,

> (list 1 2 3)
(1 2 3)

This is completely analogous to the previous set of conses which built the same list.

You can also type (quote (1 2 3)) or '(1 2 3) to develop the same list.

List manipulation[edit]

There are a few primitive expressions for manipulating lists and pairs in Scheme. They are car, cdr and map. They select specific parts of the pair or list.

> (define test (cons 1 2))
#<unspecified>
> (car test)
1
> (cdr test)
2

As you can see from the example above, when used with a pair, car and cdr select the first and second half of the pair respectively. car And cdr can also be applied to lists.

> (define test (list 1 1 2 3 5))
#<unspecified>
> (car test)
1
> (cdr test)
(1 2 3 5)

So The result of cdr is always a list, if the parameter is a list. cdr can return the empty list, (), and this is often used to test if one has reached the end of the list. car can return an atomic data, however, what happens if we do this:

> (define test (list (list 1 1) 2 3 5))
#<unspecified>
> (car test)
?

The answer is that you get another list, (1 1). Lists can contain within them any number of other datatypes. Vectors, symbols, strings, lists, pairs, numbers, any datatype that Scheme has. And car and cdr can handle them.

There are shortcut procedures for accessing other elements in a list besides just the car and cdr. The second element of a list is accessed with cadr, the third with caddr, and so on.

Now, map is often considered to be one of the more useful (if less versatile) methods for manipulating a list. map Takes a list, and a procedure, and applies the procedure to every element of the list:

> (map (lambda (x) (* x x)) (list 1 2 3 4 5 6))
(1 4 9 16 25 36)

Since it is less versatile, it is not seen or used as often, and is overlooked. Many programmers forget the map procedure when repeatedly applying an operation to a list.

Some Scheme programmers (for example, those using the Racket dialect of Scheme) like to give more descriptive names to car and cdr.

(define first (lambda (x) (car x)))
(define second (lambda (x) (cadr x)))
(define rest (lambda (x) (cdr x)))