- toc {:toc}

`cons`

forges a pair.`car`

,`cdr`

takes value out of a pair.- example:
`(car (cons a b)) ; =>a`

,`(cdr (cons a b)) ; =>b`

.

- example:
list is but a special form of pair

`'()`

or`nil`

is a list`nil`

is not available in MIT-scheme.

- The return value of
`(cons something <a-list>)`

is also a list `(list a1 a2 ... an)`

is short for`(cons a1 (cons a2 ... (cons an nil) ... ))`

- In the other direction, a pair is an improper list

- "the ability to manipulate procedures as objects automatically provides the ability to represent compound data."

`(cons something a-list)`

yields another list.`(append list1 list2)`

returns concatenation of list1 and list2.dotted-tail notation:

`(define (foo arg1 arg2 . rest ) <body>)`

- arg1, arg2 capture the first 2 arguments, rest captures the rest.

`(cons (list 1 2) (list 3 4))`

denotes a tree.Exercise 2.27: a deep-reverse procedure

`(define (deep-reverse arg) (if (list? arg) (reverse (map deep-reverse a-list)) arg)) (deep-reverse '(1 (2 3) (4 (5 6)))) ; =>`

Exercise 2.28: flattening a tree (nested list) in left-right order

`(define (fringe arg) (if (list? arg) (apply append (map fringe arg)) (list arg))) (display (fringe (list 1 (list 2) (list 3 4 (list 5)) 6))) ; => (1 2 3 4 5 6)`

Exercise 2.31: a tree-map procedure

`(define (map-tree proc arg) (if (list? arg) (map (lambda (x) (map-tree proc x)) arg) (proc arg))) (define (square x) (* x x)) (display (map-tree square '(1 2 (3 4 (5)))) ) ; => (1 4 (9 16 (25)))`

- "basic" operations on a bunch of things:
enumerate: transform something into a list

filter: select from a list

`(filter precidate a-list) ; =>list`

map: transform the list via a proc

`(map proc a-list) ; =>list`

accumulate: fold a list of things, a.k.a "fold-right"

`(define (accumulate op init a-list) (if (null? a-list) init (op (car a-list) (accumulate op init (cdr a-list))))) ; ; op ; / \ ; car op ; / \ ; cadr ... ; \ ; op ; / \ ; last init ; init is to the "RIGHT" of l`

Use of the preceding "basic" operations encourage modular design

- Because one have to fit to the known-to-be-common-enough interfaces

filter and map can be implemented using accumulate

Exercise 2.33: implement

`map`

,`append`

,`my-length`

with accumulate`(define (my-map proc sequence) (accumulate (lambda (head acc) (cons (proc head) acc)) '() sequence)) (define (my-append seq1 seq2) (accumulate (lambda (head acc) (cons head acc)) seq2 seq1)) (define (my-length sequence) (accumulate (lambda (head acc) (+ 1 acc)) 0 sequence))`

Exercise 2.36: implement

`accumulate-n`

with`accumulate`

`(define (accumulate-n op init seqs) (if (null? (car seqs)) '() (cons (accumulate op init (map car seqs)) (accumulate-n op init (map cdr seqs))))) (accumulate-n + 0 '((1 2 3) (4 5 6) (7 8 9) (10 11 12))) ; => '(22 26 30)`

Exercise 2.38: fold-left

`(define (my-fold-left op init sequence) (if (null? sequence) init (my-fold-left op (op init (car sequence)) (cdr sequence)))) ; op ; / \ ; ... last ; / ; op ; / \ ; op cadr ; / \ ; "LEFT": initial car`

- a sufficient condition: when binary operator
`op`

satisfies`op(a,b) 三 op(b,a)`

- a sufficient condition: when binary operator
Exercise 2.40: unique-pairs

Exercise 2.41: eight-queens puzzle

`'a`

returns a symbol:`a`

`'(a b)`

evaluates to the list of symbol:`(a b)`

Extra:

``( )`

quotes a list where only specific members are evaluated ("quasiquote").`,`

specifies the evaluated number in such a list.- Example:
`(let ((a 1)) `(a ,a))`

evals to`(a 1)`

.

- Example:
`(eq? a b)`

returns whether symbol a and b are the same.

**Sets**are defined by operations on them, i.e. the interface of Set class.`(adjoin-set elem set)`

`(element-of-set? elem set)`

`(intersection-set set1 set2)`

`(union-set set1 set2)`

Underlying implementation can vary:

- unordered lists
- ordered lists
- binary trees

- prefix code: no complete code (a sequence of bits) is an prefix of another code
- code automatically get segmented: we can immediately obtain a code when its last bit is received
- no need to look forward, because it is the only legal way to decode the symbols

```
(define sorted-codes
(fastsort
(huffman-encode
'((a 8) (b 3) (c 4)
(d 1) (e 1) (f 1)
(g 1) (h 1) (i 9)
))
(sort-by (lambda (x) (- (caddr x))))))
(map display-code sorted-codes)
; symbol = i count = 9 code = (0 0)
; symbol = a count = 8 code = (0 1)
; symbol = c count = 4 code = (0 1 0)
; symbol = b count = 3 code = (0 1 1)
; symbol = d count = 1 code = (1 1 1 1)
; symbol = e count = 1 code = (1 1 1 0)
; symbol = h count = 1 code = (0 1 1 1)
; symbol = f count = 1 code = (0 1 1 0 1)
; symbol = g count = 1 code = (0 1 1 0 0)
```