• toc {:toc}

#### Building Abstractions with Data

##### Introduction to Data Abstraction
###### Example: Arithmetic Operations for Rational Numbers
• `cons` forges a pair. `car`, `cdr` takes value out of a pair.

• example: `(car (cons a b)) ; =>a`, `(cdr (cons a b)) ; =>b`.
• 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
###### What Is Meant by Data?
• "the ability to manipulate procedures as objects automatically provides the ability to represent compound data."
##### Hierarchical Data and the Closure Property
###### Representing Sequences
• `(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.
###### Hierarchical Structures
• `(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)))
``````
###### Sequences as Conventional Interfaces
• "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
;         /  \
;               \
;                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
'()
sequence))
(define (my-append seq1 seq2)
(accumulate
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
;                 /  \
;              /  \
; "LEFT": initial  car
``````
• a sufficient condition: when binary operator `op` satisfies `op(a,b) 三 op(b,a)`
• Exercise 2.40: unique-pairs

• Exercise 2.41: eight-queens puzzle

##### Symbolic Data
###### Quotation
• `'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)`.
• `(eq? a b)` returns whether symbol a and b are the same.

###### Example: Representing Sets
• 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
###### Example: Huffman Encoding 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)``````