# Recitation 5

Today's idea: Lists

Hint:  if you're using Dr Scheme, set language to MzScheme (since other languages are too different from MIT Scheme)

### Homogeneous Lists

How to make a list
-- the empty list
null: list<A>    (in Rice Scheme)
nil: list<A>      (in MIT Scheme)
-- adding elements to a list
cons: A , list<A> -> list<A>
-- list procedure: returns a list of its arguments
list: A, A, A, ... -> list <A>

Examples
-- (list 1 2 3)
-- (list)
-- (cons 1 null)

How are lists displayed?
-- list containing 1, 2, 3 shown as (1 2 3)
-- don't confuse with a combination expression!
-- it's an external representation, not an expression

How to take a list apart
-- first and rest, with funny names:
car: list<A> -> A
car: list<A> -> list<A>

Examples
-- (car (list 1 2 3))
-- (cdr (list 1 2 3))
-- (car (cdr (list 1 2 3)))
-- (car (car (list 1 2 3)))

### Functions on Lists

Basic built-in functions
-- counter the number of elements
length: list<A> -> Number
-- form the concatenation of two lists
append: list<A> ,  list<A> ->  list<A>

Examples
(define p (list 1 2 3))
(length p)
(append p p)
(length (append p p))
(length null)

Exercise
-- write your own version of length recursively
-- write append
-- write reverse

### Higher Order List Functions

Simple higher-order procedures
-- filtering
filter: list <A>, (A -> Boolean) -> list<A>
-- map
map: list <A>, (A -> B) -> list<B>

Examples
-- (filter (list 1 2 3) is-odd)
-- (map inc (list 1 2 3))
-- (map is-odd (list 1 2 3))

Exercise
-- write a filter that eliminates null lists from the list
-- write a function that doubles all elements of a list
-- write map
-- write filter

### More complex lists

Other kinds of lists
-- lists of strings
(define ht (list "hello" "there"))  -- not a string!
-- lists of lists
(list (list 1 2 3) (list 4 5))

Examples
-- (map (lambda (s) (string-append s "!")) ht)
-- (filter (list (list) (list 1 2)) null?)
-- (map list (list 1 2 3))

### How Lists Are Implemented

In Scheme, lists are made of cons cells
-- cons is more general than we said before
-- it takes an A and a B and makes a pair with an A as first elt and B as second elt
cons: A, B -> A x B

List structure
-- a list is built as a bunch of cons cells strung together like a necklace
-- there is a special value null used to terminate lists

BPDs, box and pointer diagrams)
-- must have an arrow pointing to the object itself
-- cons cell has two parts
-- primitive objects drawn in a circle
-- null drawn with line through half of cons cell

Heterogeneous Lists
-- can make lists in which elements have different types
-- (list 1 "hello")
-- (list 1 (list 2))
-- our type notation can't handle this

Improper Lists
-- (cons 1 2) is legal in Scheme
-- but doesn't make a list!
-- sometimes called "improper list" by those who disapprove

What makes a list?
-- can keep applying cdr, and always get a list or null
-- equivalently: null is a list and if (cdr x) is a list, so is x

Draw BPDs for
-- (list 1 2 3)
-- (list (list 1) (list 2 3))
-- (cons (cons 1 2) (cons 3 4))
-- (cons 1 (cons 2 null))
-- which is a list?

### Definitions used from previous recitations

(define (inc i) (+ i 1))
(define (dec i) (- i 1))
(define (is-odd n)
(cond ((= n 0) #f)
((= n 1) #t)
(else (is-odd (- n 2)))))

### Definitions we developed in recitation

(define (length p)
(if (null? p) 0 (+ 1 (length (cdr p)))))

(define (append p q)
(if (null? p) q (cons (car p) (append (cdr p) q))))

(define (reverse p)
(if (null? p)
p
(append (reverse (cdr p)) (list (car p)))))

(define (map f p)
(if (null? p)
p
(cons (f (car p)) (map f (cdr p)))))

(define (filter p f)
(if (null? p)
p
(let ((first (car p))
(rest (filter (cdr p) f)))
(if (f first)
(cons first rest)
rest))))

Daniel Jackson
Sept 21, 1999