List processing

Session 5
Background
 The most important data structure in Scheme is the list.
 Lists are constructed using the function cons:
(cons first rest)
cons returns a list where the first element is first, followed by the
elements from the list rest.
> (cons ‘a '())
(a)
> (cons 'a (cons ‘b ’()))
(a b)
> (cons 'a (cons 'b (cons ‘c ‘())))
(a b c)
Constructing Lists
There are a variety of short-hands for constructing lists.

Lists are heterogeneous, they can contain elements of different

types, including other lists.
> '(a b c)
(a b c)
> (list 'a 'b 'c)
(a b c)
> '(1 a "hello")
(1 a "hello")
Examining Lists
(car L) returns the first element of a list. Some implementations also
define this as (first L).
(cdr L) returns the list 1, without the first element. Some
implementations also define this as (rest L).
Note that car and cdr do not destroy the list, just return its parts.
> (car '(a b c))
'a
> (cdr '(a b c))
' (b c)
Examining Lists
Note that (cdr L) always returns a list.

> (car (cdr '(a b c)))

'b
> (cdr '(a b c))
'(b c)
> (cdr (cdr ’(a b c)))
' (c)
> (cdr (cdr (cdr '(a b c))))
' ()
> (cdr (cdr (cdr (cdr '(a b c)))))
error
Examining Lists...
A shorthand has been developed for looking deep into a list:
(clist of "a" and "d“ r L)
Each "a" stands for a car, each "d" for a cdr.
For example, (caddar L) stands for
(car (cdr (cdr (car L))))

> (cadr '(a b c))

‘b
> (cddr '(a b c))
' (c)
> (caddr '(a b c))
'C
Lists of Lists
Any S-expression is a valid list in Scheme.

That is, lists can contain lists, which can contain lists. which...

> ' (a (b c))

(a (b c))
> ' (1 "hello“ ("bye“ 1/4 (apple)))
(1 "hello" ("bye" 1/4 (apple)))
> (caaddr ' (1 "hello" ("bye" 1/4 (apple))))
List Equivalence
(equal? L1 L2) does a structural comparison of two lists, returning #t if
they "look the same".

(eqv? L1 L2) does a "pointer comparison", returning #t if two lists are

"the same object".

> (eqv? ’ (a b c) ‘ (a b c))

false
> (equal? ’ (a b c) ‘ (a b c))
true
List Equivalence...
This is sometimes referred to as deep equivalence vs. shallow
equivalence.

> (define myList ‘ (a b c))

> (eqv? myList myList)
true
> (eqv? ‘ (a (b c (d))) '(a (b c (d))))
false
> (equal? ‘ (a (b c (d))) '(a (b c (d))))
true
Predicates on Lists
(null? L) returns t for an empty list.

(list? L) returns t if the argument is a list.

> (null? ‘())

#t
> (null? ‘(a b c))
#f
> (list? ’(a b c))
#t
> (list? "(a b c)")
#f
List Functions - Examples...
> (cdr (car ‘ ((a) b (c d))))
????
> (caddr ‘ ((a) b (c d)))
(c d)
> (cons ‘ a ‘ ())
(a)
> (cons ‘ d ’ (e))
(d e)
> (cons ‘ (a b) ‘ (c d))
((a b) c d)
Recursion over Lists - cdr-recursion
 Compute the length of a list.
 This is called cdr-recursion.
(define (length x)
(cond
[(null? x) 0]
[else (+ 1 (length (cdr x))}]
)
)
> (length ‘ (1 2 3))
3
> (length ‘ (a (b c) (d e f)))
3
Recursion over Lists – car-cdr-recursion
 Count the number of atoms in an S-expression.
 This is called car-cdr-recursion.
(define (atomcount x)
(cond
[(null? x) 0]
[(list? x)
(+ (atomcount (car x))
(atomcount (cdr x))]
[else 1]
)
)
> (atomcount ‘ (1))
1
> (atomcount ‘ (“hello” a b (c 1 (d))))
6
Recursion Over Two Lists
 (atom-list-eq? L1 L2) returns #t if L1 and L2 are the same list of atoms.

(define (atom-list-eq? L1 L2)

(cond
[(and (null? L1) (null? L2)) #t ]
[(or (null? L1) (null? L2)) #f ]
[else (and
(atom? (car L1))
(atom? (car L2))
(equal? (car L1) (car L2))
(atom-list-eq? (cdr L1) (cdr L2)))]
Recursion Over Two Lists
> (atom-list-eq? ‘ (1 2 3) ‘ (1 2 3))
#t
> (atom-list-eq? ‘ (1 2 3) ‘(1 2 a))
#f
Append
(define (append L1 L2)
(cond
[(null? L1) L2]
[else
(cons (car L1)
(append (cdr L1) L2))]
)
)
> (append ‘ (1 2) ‘ (3 4))
(1 2 3 4)
> (append ‘ () ‘ (3 4))
(3 4)
> (append ‘ (1 2) ‘ ())
(1 2)
Example: Binary Trees
 A binary tree can be represented as nested lists:
( 4 (2 () () (6 ( 5 () () ) () )))

 Each node is represented by a triple

(data left-subtree right-subtree)

 Empty subtrees are represented by ().

Example: Binary Trees
(define (key tree) (car tree))
(define (left tree) (cadr tree))
(define (right tree) (caddr tree))

(define (print-spaces N)
(cond
[( = N 0) “”]
[else (begin
(display)
(print-spaces (- N 1))))))
(define (print-tree tree)
(print-tree-rec tree 0))
Example: Binary Trees
(define (print-tree-rec tree D)
(cond
[(null? tree)]
[else (begin
(print-spaces D)
(display (key tree)) (newline)
(print-tree-rec (left tree) (+ D 1))
(print-tree-rec (right tree) (+ D 1))]
))
> (print-tree ‘ (4 (2 () ()) (6 (5 () () ) () )))
4
2
6
5
HIGHER-ORDER FUNCTIONS
Higher-Order Functions
 A function is higher-order if

1. t takes another function as an argument, or

2. it returns a function as its result.

 Functional programs make extensive use of higher-order functions

to make programs smaller and more elegant.

 We use higher-order functions to encapsulate common patterns of

computation.
Higher-Order Functions: map
 Map a list of numbers to a new list of their absolute values.
 Here's the definition of abs-list from a previous lecture:
(define (abs-list L)
(cond
[(null? L) ‘ () ]
[else (cons (abs (car L))
(abs-list (cdr L)))]
)
)
> (abs-list ‘ (1 -1 2 -3 5))
(1 1 2 3 5)
Higher-Order Functions: map...
 This type of computation is very common
 Scheme therefore has a built-in function.
(map f L)
which constructs a new list by applying the function f to every
element of the list L.

(map f ‘(c1 c2 c3 c4))

((f c1) (f c2) (f c3) (f c4))
Higher-Order Functions: map...
 map is a higher-order function, i.e. It takes another function as an
argument.

(define (addone a) (+ 1 a))

>(map addone ‘( 1 2 3))

(2 3 4)
>(map abs ‘( -1 2 -3))
(1 2 3)
Higher-Order Functions: map...
 We can easily define map ourselves:

(define (mymap f L)
(cond
[(null? L) 0]
[else
(cons ( f (car L)) (mymap f (cdr L)))])

> (mymap abs ‘(-1 2-3))

(1 2 3)
Higher-Order Functions: map...
 If the function takes n arguments, we give map n lists of arguments:

> (map string-append ("A" "B" "C") ("1" "2" "3"))

("A1" "B2" "C3")

> (map + ‘(1 2 3) ‘(1 2 3))

(list 2 4 6)

> (map cons ‘(a b c) '((1) (2) (3)))

((a 1) (b 2) (c 3))
Lambda Expressions
 A lambda-expression evaluates to a function:
(lambda (x) (* x x))
x is the function's formal parameter.
 Lambda-expressions don't give the function a name they’re
anonymous functions.

 Evaluating the function:

> ((lambda (x) (* x x)) 3)

9
Higher-Order Functions: map...
 We can use lambda-expressions to construct anonymous functions to
pass to map. This saves us from having to define auxiliary functions:

(define (addone a) (+ 1 a))

> (map addone ‘( 1 2 3 ))

(2 3 4)

> (map (lambda (a) (+ 1 a)) ‘(1 2 3))

(2 3 4)
Higher-Order Functions: fold
 Consider the following two functions:
(define (sum L)
(cond
[(null? L) 0]
[else (+ (car L) (sum (cdr 1)))]))

(define (concat L)
(cond
[(null? L)””]
[else (string-append (car L) (concat (cdr L)))]))

> (sum (1 2 3))

6
> (concat(“1” “2” “3”))
“123”
Higher-Order Functions: fold...
 The two functions only differ in what operations they apply(+ vs. string
-append, and in the value returned for the base case (0 vs. “”).
 The fold function abstracts this computation:
(define (fold L f n)
(cond
[(null? L) n]
[else (f (car L) (fold (cdr L) f n)))))

> (fold ‘(1 2 3) + 0)

6
> (fold ‘("A" "B" "C") string-append “”)
"ABC"