挖坑自動機|/posts/works/about

  • 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
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 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
;         /  \
;       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)

    • Exercise 2.40: unique-pairs

    • Exercise 2.41: eight-queens 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).

  • (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.

    • (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)