CSE1729:
Introduction to Programming
Structured Data in SCHEME:
Pairs and lists
Robert McCartney
25 20 15 10
5 0
Score Frequency
5-7 8-10
11-13 14-16
17-19 20-22 23-25
26-28 29-31
The exam
20.74 (mean) 22.25 (median)
Style notes
(define (square-pieces k n)
(if (and (equal? (is-square? k) #t)
(equal? (is-square? (- n k)) #t)
#t
#f))
(define (square-pieces k n)
(if (equal? (is-square? k) #t)
(if (equal? (is-square? (- n k)) #t)
#t
#f) #f))
Woof!
Style notes
(define (square-pieces k n)
(if (and (is-square? k)(is-square? (- n k))
#t #f))
(define (square-pieces k n)
(if (is-square? k)
(if (is-square? (- n k))
#t
#f) #f))
Woof!
Style notes
(define (square-pieces k n) 🙂 (and (is-square? k)(is-square? (- n k)))
(define (square-pieces k n)
(if (is-square? k)
(is-square? (- n k))
#f))
Our story thus far…
…has focused on two “data-types:” numbers and functions. (In fact, numeric data types are rather more complicated than you might think at first: recall the difference between 4 and 4.0.)
However, we often want to construct and manipulate more complicated structured data objects:
pairs of objects,
lists of objects,
trees, graphs, expressions, …
✤
✤
✤
✤
✤
Key idea: Abstraction
✤
✤
✤
✤
So far we have concentrated on functional abstraction
Given a sequence of operations that will perform some task Abstract it by parameterizing some of the parts
Package it into a function that will perform the task
Key idea: Abstraction
Now we will concentrate on data abstraction
Define some data type by the functions that allow you to create it and access its parts (henceforth the constructor and selector(s)).
Use the constructor and selectors when performing computation on the data type
The implementation of the constructor and selectors is separate from the use of the data type – you don’t need to understand the internal details to use the data
✤
✤
✤
✤
Example: Rational numbers
The rational numbers can be formally defined as the equivalence classes of the quotient set (Z ✕ (Z \ {0})) / ~, where the cartesian product
Z ✕ (Z \{0}) is the set of all ordered pairs (m,n) where m and n are integers, n is not 0 (n < 0), and "~" is the equivalence relation defined by (m1,n1) ~(m2,n2) if, and only if, m1 n2 − m2 n1 = 0.
Informally, the rational numbers are the set of all numbers that can be expressed as m/n, where m and n are integers and n < 0. For any rational m/n, we denote m as the denominator, and n as the numerator. on the data type.
Rational arithmetic
Addition:
Subtraction: Multiplication:
Division: Equality:
a+c=ad+bc b d bd
a c=ad bc b d bd
a·c=ac b d bd
a ad b=
c bc d
a=c,ad=bc bd
Rational data type will provide
Constructor(n, d): Numerator(x): Denominator(x):
(make-rat n d)
(numer x)
(denom x)
Given these, we can write the arithmetic functions:
(define (add-rat x y)
(make-rat (+ (* (numer x) (denom y))
(* (numer y)(denom x)))
(* (denom x) (denom y))))
(define (sub-rat x y)
(make-rat (- (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))
(define (mul-rat x y)
(make-rat (* (numer x) (numer y))
(* (denom x) (denom y))))
Given these, we can write the arithmetic functions:
(define (div-rat x y)
(make-rat (* (numer x) (denom y))
(* (denom x) (numer y))))
(define (equal-rat? x y)
(= (* (numer x) (denom y))
(* (numer y) (denom x))))
Notice that none of these definitions depend on how rational numbers are implemented (make-rat, numer, and denom).
Pairs
Scheme has built-in support for pairs of objects. To maintain pairs, we require:
A method for producing a pair from two objects: In SCHEME, this is the cons function. It takes two arguments and returns a pair containing the two values.
A method of extracting the first (resp. second) object from a pair: In SCHEME, these are two chimerically named functions: car and cdr. Given a pair p, (car p) returns the first object in p; (cdr p) returns the second.
✤
✤
✤
Examples; notation
> (cons 1 2)
(1 . 2)
> (define p (cons 1 2))
> (car p)
1
> (cdr p)
2
> (define q (cons p 3))
> (car q)
(1 . 2)
> (cdr q)
3
> (car (car q))
1
> (cdr (car q))
2
>
✤
Note that the interpreter denotes the pair containing the two objects a and b as: (a . b).
Note that a coordinate of a pair can be…another pair! A natural diagram to represent this situation:
✤
(cons 1 2)
(cons (cons 1 2) 3)
1
2
3
1
2
Rational numbers using pairs
A natural way to maintain a rational number is as a pair
✤
(define (make-rat a b)
(cons a b))
(define (denom r) (cdr r))
(define (numer r) (car r))
> (make-rat 2 3)
(2 . 3)
> (make-rat 1 7)
(1 . 7)
Example
> (define r (make-rat 2 3)) >r
(2 . 3)
> (define s (make-rat 3 5)) >s
(3 . 5)
> (define t (mul—rat r s)) > (define u (make-rat 2 5)) > (equal-rat? t u)
#t
>u
(2 . 5)
>t
(6 . 15)
Reducing a fraction
Note that
✤
a=a/ if evenlydividesaandb b b/
✤
And hence we can always reduce a fraction by the rule:
a a/ gcd(a, b)
b b/ gcd(a, b)
✤
We could make a simplify function, or just redefine make-rat, so that all rationals are automatically in reduced form:
(define (make-rat a b)
(let ((d (gcd a b)))
(cons(/ad) (/bd))))
Examples
Using this new, automatically reducing package:
✤
> (define r (make-rat 4 6)) >r
(2 . 3)
> (define s (make-rat 3 5)) >s
(3 . 5)
> (mult-rat r s)
(2 . 5)
>
4/6 is reduced to 2/3
2/3 * 3/5 = 6/15 6/15 is reduced to 2/5
Lists…so important that SCHEME’s big sister is named after them
A list is an extremely flexible data structure that maintains an ordered list of objects, for example: Ceres, Pluto, Makemake, Haumea, Eris, a list of 5 extrasolar planets.
SCHEME implements lists in terms of the pair structure you have already met. However, pairs have only 2 slots, so we need a mechanism for using pairs to represent lists of arbitrary length.
Roughly, SCHEME uses the following recursive convention: the list of k objects a1,…, ak is represented as a pair where…
The first element of the pair is the first element of the list a1.
The second element of the list is…a list containing the rest of the elements.
✤
✤
✤
✤
✤
Building up lists with pairs
✤
✤
✤
For example, if • denotes the empty list, then…
•
(1 2) (1 2 3)
Some lists: (), (1), (1 2), (1 2 3)
To be more precise: A list is either
the empty list, or
a pair, whose first coordinate is the first element of the list, and whose second coordinate is a list containing the remainder of the elements.
() (1)
✤
1
•
1
2
•
1
2
3
•
✤
Note: the second element of the pair must be a list.
A general list; SCHEME notation
✤
Thus, a list has the form:
Pair
first%element
list%of%remaining% elements
✤
Since lists are used so frequently, SCHEME provides special notation for them:
()
(1) stands for (1 2)
empty list
(1 . ())
(1 . (2 . ()))
Note: In SCHEME, lists are always terminated with the empty list.
If this looks familiar…
✤
✤
✤
✤
…that’s good!
Indeed, you have already been using SCHEME lists. SCHEME programs (and expressions) are lists!
The details…
Quotation; entering lists in the Scheme interpreter
Recall the SCHEME evaluation rule for compound (list!) objects.
This means that the natural way to enter a list doesn’t work: SCHEME wants to apply evaluation:
> ()
. #%app: missing procedure expression; probably originally (), which is an illegal empty application
in: (#%app)
> (1 2)
. . procedure application: expected procedure, given: 1; arguments were: 2
SCHEME provides the (quote
which evaluates to
✤
✤
✤
> (quote ())
()
> (quote (1 . ()))
(1)
> (quote (1))
(1)
> ‘(1)
(1)
Note how SCHEME denotes these identical structures ‘
Examples; list construction
✤
It takes some practice to manipulate Scheme lists: the important thing to remember is that if enemies is a nonempty list, then (car enemies) is the first element of the list and (cdr enemies) is the list of all elements after the first.
Some examples:
✤
> (cons
(1 . 2)
> (cons 1 ‘())
(1)
> (cons 1 ‘(2))
(1 2)
> (cons 1 (cons 2 ‘()))
(1 2)
> (car ‘(1 2))
1 A list is a pair! > (cdr ‘(1 2))
(2)
1 2)
A pair A list
Elements of lists can be pairs, functions, other lists, …
✤
For convenience, SCHEME provides a list constructor function: list.
Note that you can construct lists of arbitrary objects.
> (list 1 2 3)
(1 2 3)
> (list (list 1 2) (list 3 4))
((1 2) (3 4))
> (list (cons 1 2) (list 3 4))
((1 . 2) (3 4))
> (list 1 (cons 2 3) (list 4 5))
(1 (2 . 3) (4 5))
> (list 1 2 ‘())
(1 2 ())
> (list)
()
✤
List processing: Handle the first elements and, then,…handle the rest
✤
✤
(null? x) returns #t is x is the empty list.
list processing: handle the first element (the car) and, then, handle the remaining list (the cdr). Notice that these have different “types.”
Computing the length, for example…
(define (nlength xyz)
(if (null? xyz)
0
(+ 1 (nlength (cdr xyz)))))
Then…
> (nlength ‘(1 2 3))
3
> (nlength ‘())
0
> (nlength ‘((1 2) (3 4)))
2
✤
The recursive call structure of a call to length
3
length (1 2 3)
2
length (2 3)
1
0
length (3)
length ()
Another example: Summing the numbers of a list
Adding the elements of a list:
(define (sum-list list)
(if (null? list)
0
(+ (car list)
(sum-list (cdr list)))))
✤
✤
Then…
> (sum-list ‘())
0
> (sum-list ‘(1 3 5 7))
16
Hey, these are great but…not all elements are created equal
If list is a list, it is easy to get to the first element: (car list). The last element, however, takes more work to find. This is an inherent feature (and, sometimes, shortcoming) of this “data structure.”
(define (last-element l)
(if (null? (cdr l))
(car l)
(last-element (cdr l))))
> (last-element ‘(5 4 3 2 1))
1
✤