cons
forges a pair. car
, cdr
takes value out of a pair.
(car (cons a b)) ; =>a
, (cdr (cons a b)) ; =>b
.list is but a special form of pair
'()
or nil
is a listnil
is not available in MIT-scheme.(cons something <a-list>)
is also a list(list a1 a2 ... an)
is short for (cons a1 (cons a2 ... (cons an nil) ... ))
(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>)
(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)))
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
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
op
satisfies op(a,b) 三 op(b,a)
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.
(let ((a 1)) `(a ,a))
evals to (a 1)
.(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:
(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)