SICP Chapter 2.2 Notes

SICP

Chapter 2.2

Hierarchical Data and the Closure Property

Box-and-pointer notation, each object can contain pointer/s to the next object
- For list representations, car retrieves the value, cdr retrieves the next pair
- Both elements of the cons could also be pointers to other pairs, forming a tree representation
- The ability to create pairs whose elements are pairs is referred to the closure property of cons, permitting the creation of hierarchical structures

Representing Sequences

As mentioned, a sequence or list can be constructed with pairs formed by nested cons
```
(cons 1
      (cons 2
            (cons 3 nil)))
```
There's also the primitive list which is simpler and equivalent to the method above
- (list <a1> <a2> ... <an>)
```
(list 1 2 3)
```
List operations are performed by making successive calls with cdr which gives us the reference to the next item
- The primitive predicate null? test whether an item is an empty list
- Example of length procedure for finding the length of a list
```
(define (length items) 
    (if (null? items) 
        0 
        (+ 1 (length (cdr items)))))
```
Mapping over lists is to apply some transformation to each element within the list and returning the results
- Abstract the idea and produce a higher-order procedure map which takes a transformation procedure and a list
```
(define (map fn items) 
    (if (null? items)
        nil 
        (cons (fn (car items)) 
              (map fn (cdr items)))))
```

Hierarchical Structures

Another way to think of sequences whose elements are sequences is as trees
- Elements are branches
- Elements that are also sequences are sub-trees
Recursion is the most natural concept for dealing with tree structures
- The primitive predicate pair? tests whether a value is a pair (if the element is a sequence / sub-tree or not)
- Example of count-leaves to find the number of leaf nodes in a tree
```
(define (count-leaves x) 
    (cond ((null? x) 0) 
          ((not (pair? x)) 1) 
          (else (+ (count-leaves (car x)) 
                   (count-leaves (cdr x))))))
```

Mapping over trees can be analogous to the procedure for mapping over lists

(define (map-tree fn tree) 
    (cond ((null? tree) nil) 
          ((not (pair? tree)) (fn tree)) 
          (else (cons (map-tree fn (car tree)) 
                      (map-tree fn (cdr tree))))))

Sequences as Conventional Interfaces

Higher-order procedures can be further abstracted, can capture common patterns dealing with data and create a general procedure
- Consider the flow structure of two procedures and their commonality:
  - Enumerate (tree leaves) --> Filter (odd?) --> Map (square) --> Accumulate (+, 0)
  - Enumerate (integers) --> Map (fib) --> Filter (even?) --> Accumulate (cons, ())
- A transducer would be useful to apply multiple types of transformations at a time
To create a procedure reflecting the flow structure, focus on the operational procedures processing the list at each stage
- map is defined above, but filter (predicate, sequence), accumulate (operation, initial, sequence) and enumerate (tree) will also need to be defined
- Example of sum-odd-squares procedure
```
(define (sum-odd-squares tree) 
    (accumulate + 0 (map square (filter odd? (enumerate-tree tree)))))
```

Can extend the sequence paradigm to include computations commonly expressed using nested loops

Consider mapping the sequence generated by enumerate-interval which generates a pair (i, j), representing the indices for a double nested loop
- It works by combining all the sequences for i by accumulating with append, producing the sequence of pairs

(define sequence (accumulate append nil (map (lambda (i) 
                                                (map (lambda (j) (list i j)) 
                                                    (enumerate-interval 1 (- i 1)))) 
                                            (enumerate-interval 1 n))))

A separate procedure flatmap combines mapping and accumulating with append

(define (flatmap fn sequence) 
    (accumulate append nil (map fn sequence)))