wiki:Types/ADTs

Abstract Data Types

Read Abstract Data Types first.

A type of the data is defined by the set of legal operations which could be performed on the data.

There are my Lecture Notes for Berkeley CS61A course as it taught in a Spring of 2008.

;; Hierarchical data - a form, a shape, a structure of the data

;; Tree - the way to represent a hierarchical data.

;; Tree is a structure with "vertical" links between its Nodes
;;     a Node of a Tree is a Tree itself (a Node is of type Tree)

;; a structure with "horizontal" links between nodes is called List
;;     usually a Node of a List is a List itself

;; Tree - a structure with only one parent for each Node

;; a structure with more than one parent for a Node is called Graph
;; Graph is a structure with "horisontal" and "vertical" links between its Nodes.
;; Nodes of a Graph are Graphs themselves 

;; Binary Tree - a structure with at most two children - left and right branches.

;; Binary Search Tree - a pre-ordered Tree
;;     all elements on the left branch are less than Datum of the Node
;;     all elements on the right branch are greater than Datum of the Node

;; ADT: General Tree - Datum and a List of children (a List of Trees/Nodes)
;;     Pieces of a tree (Nodes) are Trees themselves.

;; ADT Tree
;; Selectors: datum, children - a List of Nodes/Trees

;; root Node (only one)
;;     branch Nodes (many)
;;         leaf Nodes (Nodes with no children) (many)

;; every Node has only one parent
;;     root Node has no parent

;; each Node of a Tree is itself a Tree
;; there is no difference between Trees and Nodes - they are of the same type.

;; ADT General Tree: constructor and selectors (synonyms)

'(d n1, n2, n3)             ; a Node is a List of a Datum and a List of Nodes

(define make-tree cons)     ; prepend a Datum to a List
(define datum car)          ; CAR is a Datum
(define children cdr)       ; CDR is a List of Trees (leaf nodes)

(define (leaf? n)           ; predicate function
  (null? (children n)))

;; very beautiful piece of recursive code
(define (tree-map f t)
  (make-tree (f (datum t))
             (map (lambda (c) (tree-map f c))   ; the base-case is inside the map
                  (cildren t))))                ; a list of trees (leaf nodes)

;; read and trace this piece of code until a premature enlightenment

;; chanting: domain and range, domain and range

(define (tree-map f t)
  (make-tree (f (datum t))               ; Tree is a List of Datum and children
             (forest-map f (children t))))

(define (forest-map f l)                 ; a Forest is a list-of-trees
  (if (null? l)
      '()
      (cons (tree-map f (car l))         ; the mutual recursions
            (forest-map f (cdr l)))))

;; Recursion is the way to deal with nested Lists (sequences)
;; Mutual Recursion is a general way for dealing with 2D-structures

;; Deep Lists - Lists of Pairs - looks like a special kind of Binary Tree

'((John Lenon) (Paul McCartny) (Geoge Harrison) (Ringo Starr))

;; a defective Binary Tree 
;;     branch Nodes have no Datum, only children
;;     leaf Nodes have only Datums, no children

(define (deep-map f l)
  (if (list? l)
      (map (lambda (e) (deep-map f e)) l)   ; a branch node - no datums - proceed
      (f l)))                               ; a leaf node - apply a procedure

;; General Trees have both Datums and Children
;; Deep Lists have either Datums or Children

;; traversing a Deep List (List of Pairs) as if it is a Binary Tree.

(define (deep-map f l)
  (cond ((null? l) '())                ; the base case (())
        ((pair? l)                     ; a branch node - spine cord pair (CDR)
         (cons (deep-map f (car l))
               (deep-map f (cdr l))))
        (else (f l))))                 ; a datum (CAR)

;; traversing any structure made out of Pairs
(deep-map (lambda (x) (* x x)) '((1 . 2) (3 . 4) (((5)) . 6)))

;; Lists-of-Pairs looks like a Binary Tree
;; Associative List looks like a Lookup Table
;;    2 children          n-children
;;
;;    Binary Tree            Tree
;;
;; CAR/CDR Recursion       Deep List
;;  (nested pairs)       (nested lists)

;; Nested Lists are defective Binary Trees
;;     each Node has either children or Datum, not both.

;; CAR/CDR Recursion
(define (deep-map f p)
  (cond ((null? p) '())                ; the base case (())
        ((pair? p)                     ; a branch node - spine cord pair (cdr)
         (cons (deep-map f (car p))
               (deep-map f (cdr p))))
        (else (f p))))                 ; a datum (car)

;; Lists of Lists
(define (map f l)
  (if (null? l)
      '()
      (cons (f (car l))
            (map f (cdr l)))))

(define (filter f l)
  (cond ((null? l) '())
        ((f (car l)) (cons (car l) (filter f (cdr l))))
        (else (filter f (cdr l)))))

;; binary Decision Tree
;;     binary tree recursion without a binary tree

(+ (count-change (- amount (car coins)) coins)   ; left branch
   (count-change amount (cdr coins)))            ; right branch

;; Tree traversal (order of visiting its nodes)

;; in a Tree there are only "vertical" links between nodes, no "horizontal" links

;; a constructor
(define make-tree cons)

;; selectors - synonyms
(define datum car)
(define children cdr)

;; a tree made out of lists
(define t1 '(1 (2 (3) (4)) (5 (6) (7) (8))))

;; depth-first traversal
(define (depth-first-search t)
  (display (datum t))
  (for-each depth-first-search (children t)))

(depth-first-search t1)

;; breadth-first traversal (row by row)
;;     use breadth-first search to find a Shortest Path.
(define (breadth-first-search t)
  (bfs-iter (list t)))              ; a list of length 1 with the root Node inside

(define (bfs-iter q)
  (if (null? q)                     ; Queue is an ordered List of Trees/Nodes
      'done
      (let ((n (car q)))            ; CAR of queue is a Node (each Node is a Tree)
        (display (datum n))
        (bfs-iter (append (cdr q) (children n))))))   ; CDR of queue is a List

(breadth-first-search t1)

;; Traversing a Binary Tree

;; a Node of a Binary Tree is a Binary Tree made out of Pairs 
;; (datum . (left-branch . right-branch)) - tightly packed Pointers

;; prototyping ADT
'(1 . (2 . 3))
(car '(1 . (2 . 3)))      ; datum
(cdr '(1 . (2 . 3)))      ; CDR is pair
(cadr '(1 . (2 . 3)))     ; left branch
(cddr '(1 . (2 . 3)))     ; right branch

;; constructor
(define (make-node d l r)
   (cons d (cons l r)))

;; selectors - synonyms
(define datum car)
(define left-branch cadr)
(define right-branch cddr)

;; tests
(define n (make-node '(1 2 3) '() '())) ; a leaf node - no children, only datum
(datum n)
(left-branch n)
(right-branch n)

;; a Node of a Binary Tree is a Binary Tree made out of Lists
;; (datum left-branch right-branch) - loosely coupled Pointers

;; Computer memory is an indexed sequence (Array) of words.
;; Representing any structure as a list of pointers is the most natural way. 

;; prototyping ADT
'(1 2 3)
(car '(1 2 3))            ; datum
(cdr '(1 2 3))            ; CDR of a list is a list
(cadr '(1 2 3))           ; left branch
(caddr '(1 2 3))          ; right branch

;; constructor
(define (make-node d l r)
  (cons d (list l r)))    ; stick a Datum in front of children 

;; selectors (synonyms)
(define entry car)
(define left-branch cadr)
(define right-branch caddr)

;; testing
(define n (make-node '(1 2 3) '() '())) ; a leaf node - no children, only datum
(entry n)
(left-branch n)
(right-branch n)

;; 3 different orders - a sequence of events
(define (pre-order t)
  (cond ((null? t) '())
        ((else (display (entry t))
               (pre-order (left-branch t))
               (pre-order (right-branch t))))))

(define (in-order t)
  (cond ((null? t) '())
        (else (in-order (left-branch t))
              (display (entry t))
              (in-order (right-branch t)))))

(define (post-order t)
  (cond ((null? t) '())
        (else (post-order (left-branch t))
              (post-order (right-branch t))
              (display (entry t)))))

;; a Path is a List of names (of visited Places)

;; if the range of a procedure are lists, return a list

;; Example

(define make-tree cons)
(define datum car)
(define children cdr)

(define (city x) (make-tree x '()))
(define (leaf? n) (null? (children n)))

;; domain: Place (a Symbol) and Tree
;; range: Path (a List of Places)
(define (find-place p t)
  (cond ((eq? p (datum t)) (cons (datum t) '())) ; return a Path (a list of places)
        ((leaf? t) '())                          ; a Leaf Node (no children) - fail
        (else (let ((path (find-subtree p (children t))))
                (if (not (null? path))           ; found any path?
                    (cons (datum t) path)
                    '())))))

;; domain: Place and a Forest (a List of Trees/Nodes)
;; range: Path (a List of Places)
(define (find-subtree p l)
  (if (null? l)
      '()
      (let ((path (find-place p (car l))))
        (if (not (null? path))
            path                              ; a Path is a List
            (find-subtree p (cdr l))))))      ; proceed

;; use Hash Tables for lookups
Last modified 2 years ago Last modified on Aug 31, 2017, 9:01:06 AM
Note: See TracWiki for help on using the wiki.