Slides

S1: Overview of the Week

Outline
- 4.1 Domain of Structures
  - Values, and simple functions (car, cdr, cons)
  - box-pointer diagrams
- 4.2 quote and Symbols
  - 4.2.1 Special form quote - syntax, semantics
  - 4.2.2 Domain of Symbols
- 4.3 Collections
Reading
- Chapter 4.1, 4.2, 4.3
- B.6.3 Pairs and Lists, B.6.4 Symbols, B.5.2 Literal expressions
  - B.3.6-7 Symbols, Pairs and Lists
- Recommended Ex.: 4.1, 3, 5, 10, 11, 13...18, 24, 25, 33, 38, 42

S2: Structures

Motivation : Aggregate data types
- Simple data holds "one" value, e.g. number, character
- Aggregate data holds multiple, e.g. structure, list, vector
- Many applications process a group of data
  - e.g. Databases, Telephone directory, roadmaps, VLSI circuits...
- What are structures?
- A general storage mechanism
- Can hold a heterogeneous collection of data
- Simplest structure = a pair
A journey into "Collections" Country
- 4.1 Pairs : the simplest collections
- 4.3 Linear lists made using pairs
- Csci 3317, 3321, 3322 : trees, tables, ...
- Csci 5702, 5703: databases

S3: 4.1 Domain of Pairs

Values = set of pairs of values of scheme datatypes
- Ex. (1 . 2), (1 . null), (#t . 23), ("Mary" . "644-8286")
- Dot-notation: dot separates first and second elements
Procedures on pairs
- (i) cons - Given two values, construct a pair
  - return the address of the pair
    (cons 1 2) ; return address of (1 . 2), displays (1 . 2)
- (ii) car - Given a pair, return the first value
  (car (cons 1 2)) ; returns 1
- (iii) cdr - Given a pair, return the second value
  (cdr (cons 1 2)) ; returns 2
- (iv) pair? - Given a scheme-form, checks if it a pair
  (pair? (cons 1 2)) ; returns #t
  (pair? (car (cons 1 2))) ; Q? What will it evaluate to?
Q? What do acronyms car and cdr stand for?
1960 machine dependent jargon from IBM 7090
Better names would be < first, second > or < head, tail >
Some day Scheme hackers will give up old jargon!

S4: 4.1 Playing with cons, car, and cdr

Ex. Evaluate the following?
- Explain your answers using box-pointer diagrams (Fig. 4-2/3, pp 170).
  (car (cons "head" "tail"))
  (cdr (cons "head" "tail"))
  (car (cdr (cons 1 (cons 2 3))))
  (cons (cdr (cons 1 2)) (cdr (cons 3 4)) )
- Box-Pointer Diagrams (Fig. 4-2/3, pp 170)
- Visual representation of a pair is
  an arrow to a box with two compartments
  first compartment holds first element
  second compartment holds the other element
- Representation of other values are usual, e.g. 2.3. "aString", ...
- Will revisit in chapter 4.3 Collections
Ex. Evaluate the following:
(car (1 . 2))
(cons 1 null)
(cons 1 (cons 2 3))

S5: 4.1 Common Errors with Pairs

Q? How does Scheme separate numbers 2.3 from pairs (2 . 3)
Q? How does Scheme separate pairs from procedure-calls?
- It does not!!!, i.e. We can't use text (1 . 2) as a pair!
  (1 . 2) ;; Forces Scheme to apply procedure 1 on ...?
- Special form "quote" can help here! = > chapter 4.2
Display shortcuts
- Q? Does (cons 1 null) display (1 . null) ?
- Q? Does (cons 1 (cons 2 3)) display (1 . ( 2 . 3)) ?
- Actual displays: (1), (1 2.3)
- Remove dot followed by parenthesis or null!

S6: 4.1 Pairs of Pairs of Pairs - Recursive Data-structures!

Q? Can we have a pair, whose parts are also pairs?
- e.g. Is (cons 1 (cons 2 3)) a pair?
- Yes it is!
  (car (cons 1 (cons 2 3))) ;;; returns 1
  (cdr (cons 1 (cons 2 3))) ;;; displays (2 . 3)
  (car (cdr (cons 1 (cons 2 3)))) ;;; returns 2
  (cdr (cdr (cons 1 (cons 2 3)))) ;;; returns 3
Shorthand for sequence of car, cdr
(cadr (cons 1 (cons 2 3))) ;;; returns 2
(cddr (cons 1 (cons 2 3))) ;;; returns 3
Recursive data-structures
(cons 1 (cons 2 (cons 3 (cons 4 5))))
;;; displays (1 2 3 4 . 5)
(cons 1 (cons 2 (cons 3 (cons 4 null))))
;;; displays (1 2 3 4 5)

S7: 4.2 Special Form Quote

Use values from the domain of pair
- Use (1 . 2) to mean a pair, not a procedure call
- Suppress evaluation of 1 in (1 . 2)
- Analogy: word itself vs. its meaning (evaluation)
  A dog is an animal, while 'dog' is a noun.
Syntax: (quote scheme-form) or 'scheme-form
(quote (1 . 2)) ;;; returns (1 . 2)
(car '(2 . 3)) ;;; returns 2, not error
'(1) ;;; returns (1) not error
Semantics: Does not evaluate argument scheme-form
and return the scheme-form
Short of like "No operation"
Q? Which domain does x come from?
numbers, booleans, characters, string, pairs

S8: 4.2 Domain of Symbols (i.e. names)

Set of values: a, x, Scheme, if, factorial, ...
- i.e. set of the NAMEs for data, procedures, forms, ...
Q? How are Symbols different from Strings?
- Symbols are atomic, can not be split into characters.
- Honda, Accords are symbols, "Honda-Accord" is a string
- Symbols are case insensitive, e.g. foo, FOO, fOO
Functions on the domain of Symbols
- (symbol? x) ;; domain predicate
- (symbol-equal? x) ;; comparison predicate
- (string- > symbol string) ;; convert string to symbol
- (symbol- > string string) ;; convert symbol to string
Special forms on the domain of Symbols
- (define symbol scheme-form) ;; creates a symbol with a value
  (define x 2)

S9: 4.2 Domain of Symbols (i.e. names)

Ex. Determine the values of each symbol created below:
(define x 4) ;; value of x is 2
(define y x) ;; What if the value of y?
(define z 'x) ;; What is the value of z?
(define z2 ''x) ;; What is the value of z2?
(define z3 '''x) ;; What is the value of z3
(define (square x) (* x x)) ;; square is (lambda(x)(* x x ))
;;; What will the following forms evaluate to?
'(sqr 2)
('sqr 2)
(sqr '2)
Summary of 4.2 (quote, symbols)
Need quotes before pairs and symbols
not before numbers, booleans, strings, characters

S10: 4.3 Back to Domain of Structures : Lists

Values = (), (1), ("a" 3), (3 6 "ghij" hello), ...
- null, i.e. () is a list of no items
- if L is a list and x is anything, (cons x L) is list.
  - Also (cons x null) and (cons L null) are lists.
  - But (cons L x) is not a list unless x= null.
- Lists are made of pairs
- (1) = (cons 1 null)
- ("a" 3) = (cons "a" (cons 3 null))
- (3 6 "ghij") = (cons 3 (cons 6 (cons "ghij" null)))
Diagrams for lists using box-pointer diagrams
- Each pair = an arrow to a box with two slots
- Example: Fig. 4-14/15, pp. 189-90
- Ex. draw box-pointer diagram for the lists in this slide.

S11: 4.3 Functions on Lists

Predicates:
- (list? x) ;; check if x is a list
- (null? x) ;; check if x is an empty list
Constructors: functions that return a list
- (cons item alist) ;; Adds item to the front of alist
- (list item1 ... itemN) ;; create a list (item1 item2 ...)
- (append list1 list2) ;; put list2 at end of list1
Accessors: take lists and return items or sublists
- (car alist) ;; return the first item
- (cdr alist) ;; return the list without the first item
- (list-ref alist pos);; return item at position pos
  - ;; position of first element is 0.
- (list-tail alist pos);; return sublist from position pos
  - ;; (list-tail '(1 2) 0) = (1 2); (list-tail '(1 2) 1) = (2), ...
- Summary of primitive functions on lists:
- Basic functions are car, cdr, cons
- Others, e.g. append, can be defined using car, cdr, cons
  - to practice recursive processing of lists

S12: 4.3 Exercises on Lists

Ex. What is the difference between (cons 1 2) and (list 1 2)?
Ex. Define the following using function list:
(cons 1 (cons 2 (cons 3 '() )))
(cons 1 '(3))
(cons (cons 1 (cons 2 '())) (cons 2 '(3)) )
Ex. Evaluate the following. Some may be illegal.
'(+ 2 2)
'(1 (2 3))
'(1 '(2 3))
(+ (* 2 3) '4)
(+ '(* 2 3) 4)
'(lambda(x) (* x x))

S13: 4.3 Processing Lists Using Recursion

A generic recursive formulation
- Base cases - empty list, or list with one element
  - or result = f( first element in list)
- Recursive decomposition - into car and cdr
- Q? Can we have infinite loop?
Three kinds of return values
- A number
- An item
- Another list

S14: 4.3 Processing Lists To Produce a Number

Problem: Write a function to compute number of items in a list
(length alist) ;;count number of elements
(length '(34 66 1)) ;; returns 3
(length '()) ;;returns 0
Recursive formulation
Base Case: empty list = > length = 0
Recursive decomposition
Non-empty list
(length L) = (+ 1 (length (cdr L)))
;;;length% takes a list and returns the number of elements
;;;e.g. (length '()) = 0 ; (length '(33 42)) = 2, etc.
;;; Given a non-list argument, length% may break!
(define (length% L)
(if (null? L)
0
(+ 1 (length% (cdr L))) ))
Q? Why use symbol length% instead of length?

S15: 4.3 Processing Lists to Produce an Item

Problem: Implement (list-ref alist position)
(list-ref '(11 22 33) 0) ;; returns 11
(list-ref '(11 22 33) 2) ;; returns 33
Recursive Formulation
Base Cases
empty list = > return error
position = 1 = > (car alist)
Recursive Decomposition for N > 1
find item at (sub1 position) in (cdr alist)
;;;procedure list-ref% takes a list and a numeric position
;;; and returns the item at the position
;;;e.g. (list-ref% 0 '(3 4 5)) = 3 ; (list-ref% 2 '(3 4 5)) = 5
;;;position > = (length list) return null, (list-ref% 10 '(3 5))= null
;;; position < = 0 causes infinite looping
;;; Given a non-list argument, length% may break!
(define (list-ref% alist N)
(if (null? alist)
null
(if (zero? N)
(car alist)
(list-ref% (cdr alist) (sub1 N)) )))

S16: 4.3 Processing Lists to produce Another list

Problem: Copy a given list to produce another list
- with no pair sharing.
  (list-copy '(2 3 4)) ;; yields (2 3 4) with different pairs
- Strategies for producing lists
- (i) Strategy 1 : recursively use cons
- (ii) Strategy 2 : Tail recursion with accumulator list
Trace Driven Development of Functions
- Write a trace with a sample input
- Check if moving from step I to I+1
  - requires only simple p(e.g. primitive) functions
- Generalize the step conversion to an expression

S17: 4.3 Producing Lists - Repeating "cons"

Base Case: empty list = > return empty list
Recursive Decomposition Strategy 1 : cons
Trace driven development
- Trace
  input = (1 2 3 4)
  output = (cons 1 (cons 2 (cons 3 (cons 4 nil))))
  = (cons 1 (cons 2 (cons 3 (list-copy '(4)) )))
  = (cons 1 (cons 2 (list-copy '(3 4)) ))
  = (cons 1 (list-copy '(2 3 4)) )
  = (list-copy '(1 2 3 4))
- Generalizing to get an expression
  (list-copy L) = (cons (car L) (list-copy (cdr L)))
  ;;;;;;;;;;;;;;;
  (define (list-copy L)
  (if (null? L)
  '()
  (cons (car L) (list-copy (cdr L))) ))

S18: 4.3 Producing list using tail-recursion

Recursive Decomposition Strategy 2 : accumulator list
- Use a helper function of two arguments
- Trace with input = (1 2 3 4)
  output = (copy-helper '(1 2 3 4) '())
  = (copy-helper '(2 3 4) '(1))
  = (copy-helper '(3 4) '(1 2))
  = (copy-helper '(4) '(1 2 3 ))
  = (copy-helper '() '(1 2 3 4))
- Generalizing to get (1 2 3 4) from (1 2 3) and 4 ?
  choice 1 : (insert-at-end 4 '(1 2 3))
  choice 2 : (reverse (cons 4 (reverse (1 2 3))))
  choice 3 : (append '(1 2 3) '(4) )
  (copy-helper L R) = (copy-helper (cdr L) (append R (car L)))
  ;;;;;;;
  (define (list-copy L)
  (copy-helper L '()) )
  (define (copy-helper L R)
  (if (null? L)
  R
  (copy-helper (cdr L) (append R (list (car L)))) ))

S19: 4.3 More Examples of List Processing

Q? Which strategy is more natural?
Ex. Identify the base cases and recursive decomposition
- for the following functions on lists:
  (sum aListOfNumbers ) ;; returns sum of numbers in the list
  ;;; (sum '(2 3 4)) = 9
  (member aList anItem ) ;; predicate to check if anItem is in aList
  ;;; (member 3 '(2 3 4)) = #t ; (member 1 '(2 3 4)) = #f
  (list-tail alist pos);; return sublist from position pos
  (list item1 ... itemN) ;; create a list (item1 item2 ...)
  (append list1 list2) ;; put list2 at end of list1
  ;;; (append '(1 2 3) '(3 4)) = (1 2 3 3 4)
  (reverse aList ) ;; return another list
  ;;; (reverse '(1 2 3)) = (3 2 1)
  (read-list aList ) ;; read a list of items enclosed in "{", "}"
  (display-list aList );; display a list of items
- See chapter 4.3 for details
- 4.3.3 list-tail%, 4.3.4 equal?%, 4.3.5 member%, 4.3.6 append%
- 4.3.8 reverse% and droid-models for procedures on lists
- 4.3.9 input-output with lists

S20: 4.4 Higher level procedures: Map, Filter and Reduce

Higher level procedures
- Have a parameter of the type procedure
- i.e. They operate on the domain of procedures
- Ex. differentiate, compose, ...
List transformations: map, filter, reduce
- Are higher level procedures
- Perform a given procedure on each element of a given list
- Produce another list or atomic value
As high level procedures
- They are generalization of many operations on lists

S21: 4.4.1 Map

Map as a higher level procedure on lists
- Ex. Consider following operations
  - f1: add 1 to each element, e.g. (2 3 4) = > (3 4 5)
  - f2: square each element, e.g. (2 3 4) = > (4 6 9)
  - f3: compute GPA for each element,
    e.g.. (John Mary Lisa) = > (3.4 3.9 3.3)
- General procedure (map procedure list)
  (map add1 '(2 3 4))
  (map sqr '(2 3 4))
  (map compute-GPA '(John Mary Lisa))
Definition of procedure map
(define (map% aProcedure aList)
(if (null? aList)
'()
(cons (aProcedure (car aList)) (map% aProcedure (cdr aList)))))

S22: 4.4.2 Filter

Semantics: Given a list L and a predicate, produce another list
- consisting of element of L satisfying the predicate
- Examples:
  (filter number? '("2" "3" 4 5)) ;;; returns (4 5)
  (filter odd? '(2 3 4 5)) ;;; returns (3 5)
- Definition of procedure filter
  (define (filter% aPredicate aList)
  (if (null? aList)
  '()
  (if (aPredicate (car aList))
  (cons (car aList) (filter% aPredicate (cdr aList)))
  (filter% aPredicate (cdr aList)) )))

S23: 4.4.3 Reduce

Semantics: Recursively apply a given binary procedure
- to elements in the list as shown below:
- (reduce f 10 '(2 3 4)) = f(2, f(3, f(4, 10)))
- Simple meaning for commutative operations, e.g. +
- (reduce + 10 '(2 3 4)) = 2 + 3 + 4 + 10
- Complex meaning for non-commutative operations, e.g. -
- (reduce - 10 '(2 3 4)) = (- 2 (- 3 (- 4 10)))
  = 2 - 3 + 4 - 10
- Definition of procedure reduce
  (define (reduce% aBinaryProcedure nullValue aList)
  (if (null? aList)
  nullValue
  (aBinaryProcedure (car aList)
  (reduce% nullValue aBinaryProcedure (cdr aList)) )))

S24: 4.4 More on Reduce

Reduce is a powerful operator and can
- implement many list procedures
- Example: implementing length% using reduce
  (define (length% L) (reduce add1toY 0 L))
  (define (add1toY x y) (+ 1 y))
  ;;(reduce add1toY 0 '(4 7 2)) = (add1toY 4 (add1toY 7 (add1toY 2 0)))
- Example: implementing append% using reduce
  (define (append% L1 L2) (reduce cons L2 L1))
  ;;(reduce cons '(3 5) '(4 7 2))
  ;; = (cons 4 (cons 7 (cons 2 '(3 5))))
Generalize associative binary procedures to work with a list of values
Adding a list of numbers using binary +
(define (addNumbersInList L) (reduce + 0 L))
;; (reduce + 0 '(4 3 5 2)) = (+ 4 (+ 3 (+ 5 (+ 2 0))))
Concatenating a collection of lists
(define (cat L) (reduce append '() L))
;;(reduce append '() '((2 4) (3 2 1) (7 2)) )
;; = (append '(2 4) (append '(3 2 1) (append '( 7 2) '() )))

S25: 4.4 Exercises on map, filter and reduce

Ex. Evaluate the following:
(map (lambda(x) (cons x 'foo)) '(a b c))
(map length '( (2 3) ( 8 7) ((2)) ))
(filter list? '(1 (2 3) 4 9 ( 8 7) ((2)) ))
(filter number? '(1 (2 3) 4 9 ( 8 7) ((2)) ))
(reduce (lambda(x y)(+ y (* 10 x))) 0 '(2 4 1))
(reduce (lambda(x y)(+ x (* 2 y))) 5 '(2 4 1))
Adv. Ex. Define factorial using reduce and a helper procedure
to generate a list of numbers from 1 to N.
Adv. Ex. Define map using reduce and a helper procedure.