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
✤
Append: Place one list after another.
Basic operation on lists: place one after the other:
Append(11 12 13)to(1 2 3) (1 2 3 11 12 13)
It’s easy: (define (append list1 list2) ; in R5RS (if (null? list1)
✤
✤
Then…
list2
(cons (car list1)
(append (cdr list1) list2))))
>(append ‘(1 2 3) ‘(13 14 15))
(1 2 3 13 14 15)
How long does this take?
A good measure of the “time taken” by a Scheme function (without looping constructs, which we will discuss later) is simply the number of recursive calls it generates.
(append list1 list2) involves a total of length(lista) recursive calls. (Why? I needs to find the end of the list.)
(append list1 list2)
(append (cdr list1) list2)
✤
✤
(append (cdr (cdr list1)) list2)
Back to asymmetry: Reversing a list. Not as easy as you thought…
Reversing a list. One strategy: peel off the first element; reverse the rest; append the first element to the end. This yields:
(define (reverse items)
(if (null? items)
‘()
(append (reverse (cdr items))
(list (car items)))))
Then… > (reverse ‘(1 2 3 4 5)) (5 4 3 2 1)
✤
Even after all that work: This reverse has a serious problem
How long does it take to reverse a list? (One good way to measure the running time of a SCHEME function is to measure the total number of procedure calls it generates.)
If the list has n elements, reverse is called on each prefix. There are about n of these, which looks OK.
However, each reverse also calls append. If reverse is called with a list of k elements, the append needs to step all the way through this list in order to get to the end, generating k total calls to append.
✤ All in all, this is roughly n + (n-1) + … + 1 calls; about n2/2. Surely we can reverse a list in roughly n steps!
✤
✤
✤
Appending the car once the rest of the list is reversed is costly…
…what if we pass the car along as a parameter, asking our next-in- line to take care of the job of appending it to the resulting list?
(define (reverse items)
(define (reverse-iter r-items rest)
(if (null? r-items)
rest
(reverse-iter (cdr r-items)
(cons (car r-items) rest))))
(reverse-iter items ‘())
Note: this simply generates ~n recursive calls!
✤
✤
Visually
r-items
rest
(cdr r-items)
(cons (car r-items) rest))
1
2
3
4
5
6
●
●
2
3
4
5
6
●
●
3
4
5
6
●
2
1
●
4
5
6
●
3
2
1
●
5
6
●
4
3
2
1
●
6
●
5
4
3
2
1
●
6
5
4
3
2
1
●
●
Let’s consider another data type
✤
✤
The names used for functions and variables: e.g. x, f, car, empty?, sum, product
These are of type symbol, and they evaluate to their assigned values, e.g. when you evaluate (sqrt 4) you evaluate sqrt (a function) and 4 (a number), and apply that function to the value of the number, obtaining 2.
A symbol may also have a symbol as its value, but that requires using quotation.
✤
Need to quote?
> (define a 10)
> (define b 20)
> (list a b)
(10 20)
What if we wanted (a b)?
Need to quote!
>(define a 10)
>(define b 20)
>(list ‘a ‘b)
(a b)
Could also use ‘(a b)
>(define teacher ‘(robert mccartney))
>teacher
(robert mccartney)
>(car teacher)
robert
Functions for checking types
(pair? x) #t if value of x is a pair
(list? y) #t if value of y is a list (i.e. a pair or the empty list) (symbol? w) #t if value of w is a symbol
(number? z) #t if value of z is a number
Examples
>(define a ‘fred)
>(define b ‘(10))
>(define c ‘())
>(symbol? a)
>(symbol? b)
>(symbol? ‘b)
>(list? b)
>(list? c)
>(pair? b)
>(pair? c)
>(number? b)
>(number? (car b))
Functions for checking equality
(= x y) #t if values of x and y are equal numbers (eq? x y) #t values of x and y are equal symbols,
(or equal numbers of the same kind, or refer to the same thing)
(equal? x y) #t if either(= x y), or(eq? x y), or x and y are both lists and their elements are equal? , that is
(and (equal? (car x)(car y)) (equal? (cdr x)(cdr y))
Note: the empty list is treated like a symbol for equality,
(eq? ‘() ‘()) => #t
Examples
> (define a ‘(fred))
> (define b ‘(10))
> (define c ‘())
> (define d a)
>(eq? (car a) ‘fred)
>(eq? a ‘(fred))
>(equal? a ‘(fred))
>(eq? a d)
>(eq? b 10.0)
>(= b 10.0)
>(eq? c ‘())
>(eq? c (cdr a))
Count the atoms in a list (top-level)
Define recursively: {0 if x is ‘()
(count-atoms x) = (+ 1 (count-atoms(cdr x))
if (car x) is not a list
(count-atoms (cdr x)) otherwise
(define (count-atoms x)
(cond ((null? x) 0)
((not (list? (car x))
(+ 1 (count-atoms (cdr x))))
(else
(count-atoms (cdr x)))))
Count the atoms in a nested list
Define recursively: {
0 if x is ‘()
(ncount-atoms x) = 1 if x is not a list
(+ (ncount-atoms (car x))
(ncount-atoms (cdr x))) otherwise
(define (ncount-atoms x)
(cond ((null? x) 0)
((not (list? x)) 1)
(else
(+ (ncount-atoms (car x))
(ncount-atoms (cdr x))))))
Example: use lists to represent sets
A set is a collection of things without repeats
Using lists:
✤ Define a function to see whether a set is empty
✤ Define a function to see whether something is an element of a set
✤ Define a function to add an element to a set
✤ Then define other set operations in terms of the above functions
✤ Note: if x is a set, (cdr x) is also a set.
Some of these are easy
(define (empty-set? x)
(null? x))
Set membership
Is x an element of set y?
✤ Nothing is in the empty list
x is in set y if it is equal to the first element of y, or is in the y excluding its first element (think car and cdr)
(define (element-of-set? x set)
(cond ((null? set) #f)
((equal? x (car set)) #t)
(else
(element-of-set? x (cdr set)))))
✤
Add element to a set
(adjoin-set x set):
if x is already in set, result is set, otherwise add x to the front of the list
(define (adjoin-set? x set)
(if (element-of-set? x set)
set
(cons x set)))
Set intersection
(intersect-set x y)
✤ If either x or y is empty, the intersection is empty set.
if the first element of x is in y, then the intersection is the first of x added to the intersection of the rest of x with y
✤ if the first element of x is not in y, then the intersection is the intersection of the rest of x and y
(define (intersect-set x y)
(cond ((or (empty-set? x)(empty-set? y)) ‘())
((element-of-set? (car x) y)
(cons (car x)(intersect-set (cdr x) y))
(else
(intersect-set (cdr x) y))))
✤
Finding the smallest
Objective
Write a function that finds the smallest element in a list Inductive definition
Base case?
List of one element…. Induction?
Smallest between the head and smallest in tail
✤
✤
✤
✤
✤
✤
✤
The Scheme code
One auxiliary function to choose the smallest among 2 One plain induction on the list.
(define (smallest l)
(define (smaller a b) (if (< a b) a b))
(if (null? (cdr l))
(car l)
(smaller (car l) (smallest (cdr l)))))
✤
✤
Removing from a list
✤
✤
✤
✤
Goal
Remove a single occurrence of a value from a list
Inductive definition Base case:
Easy: empty list Induction:
If we have a match:
If we don’t: remove from the tail and preserve the head.
✤
✤
done! Just return the tail.
✤
✤
The Scheme code
One plain induction on the list.
v: the value to remove
elements: the list to remove it from
(define (remove v elements)
(if (null? elements)
elements
(if (equal? v (car elements))
(cdr elements)
(cons (car elements)
(remove v (cdr elements))))))
✤
✤
✤