Note for SICP Chapter 2
 Building Abstractions with Data
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
.
 example:
 list is but a special form of pair
'()
ornil
is a listnil
is not available in MITscheme.
 The return value of
(cons something <alist>)
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
Abstraction Barriers
What Is Meant by Data?
 “the ability to manipulate procedures as objects automatically provides the ability to represent compound data.”
Extended Exercise: Interval Arithmetic
Hierarchical Data and the Closure Property
Representing Sequences

(cons something alist)
yields another list. 
(append list1 list2)
returns concatenation of list1 and list2. 
dottedtail 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 deepreverse procedure
(define (deepreverse arg) (if (list? arg) (reverse (map deepreverse alist)) arg)) (deepreverse '(1 (2 3) (4 (5 6)))) ; =>

Exercise 2.28: flattening a tree (nested list) in leftright 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 treemap procedure
(define (maptree proc arg) (if (list? arg) (map (lambda (x) (maptree proc x)) arg) (proc arg))) (define (square x) (* x x)) (display (maptree 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 alist) ; =>list

map: transform the list via a proc
(map proc alist) ; =>list

accumulate: fold a list of things, a.k.a “foldright”
(define (accumulate op init alist) (if (null? alist) init (op (car alist) (accumulate op init (cdr alist))))) ; ; 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 knowntobecommonenough interfaces

filter and map can be implemented using accumulate

Exercise 2.33: implement
map
,append
,mylength
with accumulate(define (mymap proc sequence) (accumulate (lambda (head acc) (cons (proc head) acc)) '() sequence)) (define (myappend seq1 seq2) (accumulate (lambda (head acc) (cons head acc)) seq2 seq1)) (define (mylength sequence) (accumulate (lambda (head acc) (+ 1 acc)) 0 sequence))

Exercise 2.36: implement
accumulaten
withaccumulate
(define (accumulaten op init seqs) (if (null? (car seqs)) '() (cons (accumulate op init (map car seqs)) (accumulaten op init (map cdr seqs))))) (accumulaten + 0 '((1 2 3) (4 5 6) (7 8 9) (10 11 12))) ; => '(22 26 30)

Exercise 2.38: foldleft
(define (myfoldleft op init sequence) (if (null? sequence) init (myfoldleft op (op init (car sequence)) (cdr sequence)))) ; op ; / \ ; ... last ; / ; op ; / \ ; op cadr ; / \ ; "LEFT": initial car
 a sufficient condition: when binary operator
op
satisfiesop(a,b) 三 op(b,a)
 a sufficient condition: when binary operator

Exercise 2.40: uniquepairs
 Exercise 2.41: eightqueens puzzle

Example: A Picture Language
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)
.
 Example:
(eq? a b)
returns whether symbol a and b are the same.
Example: Symbolic Differentiation
Example: Representing Sets
 Sets are defined by operations on them, i.e. the interface of Set class.
(adjoinset elem set)
(elementofset? elem set)
(intersectionset set1 set2)
(unionset 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 sortedcodes
(fastsort
(huffmanencode
'((a 8) (b 3) (c 4)
(d 1) (e 1) (f 1)
(g 1) (h 1) (i 9)
))
(sortby (lambda (x) ( (caddr x))))))
(map displaycode sortedcodes)
; 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)