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