(jordyn sicp)

2.2 Hierarchical Data and the Closure Property

!! "it is better to have 100 functions operate on one data structure
than 10 functions operate on 10 data structures" – alan perlis

like that bruce lee quote about fearing the foe who practiced one kick
10,000 times, not the one who practiced 10,000 kicks once

Box and pointer diagram of (cons 1 2)

|    +-----+-----+
+--->|     |     |    +---+
     |  *  |  *------>| 2 |
     +--|--+-----+    +---+
        |
        v
      +---+
      | 1 |
      +---+

pairs provide a universal building block from which we can build all
sorts of data structures

closure property: the ability for pairing pairs
hierarchical structures: structures made up of parts that are
made up of parts that are made up of parts…

note: closure in this sense is not the same as the closure used to
describe procedures with free variables. the authors do not like the
use of the term to mean this other thing.

the sequence 1, 2, 3, 4 repr as a chain of pairs

    +---+---+   +---+---+   +---+---+   +---+---+
--->| * | *---->| * | *---->| * | *---->| * | X |
    +-|-+---+   +-|-+---+   +-|-+---+   +-|-+---+
      v           v           v           v
    +---+       +---+       +---+       +---+
    | 1 |       | 2 |       | 3 |       | 4 |
    +---+       +---+       +---+       +---+

2.2.1 Representing Sequences

one useful structure is the sequence, ie a list

(cons 1
      (cons 2
            (cons 3
                  (cons 4 nil))))

scheme provides a primitive for this action

(list 1 2 3 4)
(define one-thru-four (list 1 2 3 4))
(car one-thru-four)
(cdr one-thru-four)

(define one-thru-four (list 1 2 3 4))
(cons 10 one-thru-four)
(cadr one-thru-four)

list processing (lisping!) is often achieved by "cdring down" lists

(define (list-ref items n)
  (if (= n 0)
      (car items)
      (list-ref (cdr items) (- n 1))))
(define squares (list 1 4 9 16 25))
(list-ref squares 4)

we often cdr down the entire list. scheme offeres the primitve null?
to help

(define (length items)
  (if (null? items)
      0
      (+ 1 (length (cdr items)))))
(define odds (list 1 3 5 7 9))
(length odds)

if iteration is more to taste,

(define (length items)
  (define (length-iter a count)
    (if (null? a)
        count
        (length-iter (cdr a) (+ 1 count))))
  (length-iter items 0))
(length (list 8 6 7 5 3 0 9))

another common technique is to "cons up" a list of answers while
"cdring down" a list

(define (myappend list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (myappend (cdr list1) list2))))
(myappend (list 1 2 3 4) (list 0 9 8 7))

– MAPPING OVER LISTS –

a very useful operation is applying a transformation to each element
in a list

(define (scale-list items factor)
  (if (null? items)
      (list)
      (cons (* (car items) factor)
            (scale-list (cdr items) factor))))
(scale-list (list 1 2 3 4 5) 100)

we can abstract this pattern

(define (mymap proc items)
  (if (null? items)
      (list)
      (cons (proc (car items))
            (mymap proc (cdr items)))))
(mymap abs (list -10 2.5 -11.6 17))

scheme provides a map primitive

we can use map to redefine scale-list

(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))

the original definition of scale-list drew attention to the
item-by-item processing. map establishes a higher level of
abstraction.

!! map abstracts the impl of procedures that operate on lists from the
details of how elements are extracted and combined

we are going to look at how this use of sequences provides a framework
for organizing programs ~~ cool

2.2.2 Hierarchical Structures

representing sequences as lists generalizes to representing sequences
made of sequences

for example,

((1 2) 3 4) ;; made by
(cons (list 1 2) (list 3 4))

is a list of three items, the first of which is a list

((1 2) 3 4) --> |.|.|---------->|.|.|-->|.|\|
                 |               |       |
                 v               v       v
                |.|.|-->|.|\|    3       4
                 |       |
                 v       v
                 1       2

!! sequences of sequences are really trees

to count the leaves in a tree:

(define x (cons (list 1 2) (list 3 4)))
(length x)              ;; 3
(count-leaves x)        ;; 4
(list x x) ;; (((1 2) 3 4) ((1 2) 3 4))
(length (list x x))     ;; 2
(count-leaves (list x x)) ;; 8

(define (count-leaves x)
  (cond ((null? x) 0)
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))
(count-leaves x)

MAPPING OVER TREES

(define (scale-tree tree factor)
  (cond ((null? tree) (list))
        ((not (pair? tree)) (* tree factor))
        (else (cons (scale-tree (car tree) factor)
                    (scale-tree (cdr tree) factor)))))
(scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)) 10)

(define (scale-tree tree factor)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (scale-tree sub-tree factor)
             (* sub-tree factor)))
       tree))
(scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)) 2)

2.2.3 Sequences as Conventional Interfaces

we have seen the power of data abstraction, we will now look at a new
powerful design principle for working with data structures:
conventional interfaces

consider this procedure, analagous to count-leaves

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else (+ (sum-odd-squares (car tree))
                 (sum-odd-squares (cdr tree))))))

on the surface, it's rather different than this one for finding even
fibs

(define (even-fibs n)
  (define (next k)
    (if (> k n)
        (list)
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ k 1)))
              (next (+ x 1))))))
  (next 0))

an abstract description shows a common nature

program 1:

enumerates the leaves of a tree
filters, selecting odds
squares selected ones
accumulates the results with +, starting with 0

program 2:

enumerates integers from 0 to n
computes fib for each int
filters, selecting evens
accumulates with cons, starting with empty list

these follow a common pattern ging through the common stages (like a
signal flow)

enumerate
filter
map
accumulate

these programs could be more elegantly expressed by organizing them to
follow a signal-flow idea

SEQUENCE OPERATIONS

concentrate on the "signals" that flow from one stage of the program
to the next. representing these signals as lists allows us to perform
list operations on them (LISt Processing ?!)

to filter, accumulate, and enumerate

(define (filter predicate sequence)
  (cond ((null? sequence) (list))
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

;; to enumerate even-fibs
(define (enumerate-interval low high)
  (if (> low high)
      (list)
      (cons low (enumerate-interval (+ low 1) high))))

;; to enumerate tree leaves
(define (enumerate-tree tree)
  (cond ((null? tree) (list))
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))

(filter odd? (list 1 2 3 4 5))
(accumulate + 0 (list 1 2 3 4 5))
(enumerate-interval 2 7)
(enumerate-tree (list 1 (list 2 (list 3 4)) 5))

with that, we can express those funcs as signal flows

(define (sum-odd-squares tree)
  (accumulate +
              0
              (map square
                   (filter odd?
                           (enumerate-tree tree)))))
(define (even-fibs n)
  (accumulate cons
              (list)
              (filter even?
                      (map fib
                           (enumerate-interval 0 n)))))

this style encorages MODULARITY … cool

we can use those units for any other task, like a list of the squares
of the first so many fib nums

(define (fib n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+
                 (fib (- n 1))
                 (fib (- n 2))))))
(define (square x) (* x x))
(define (list-fib-squares n)
  (accumulate cons
              (list)
              (map square
                   (map fib
                        (enumerate-interval 0 n)))))
(list-fib-squares 10)

we could rearrange them to compute odd ints in a sequence

(define (product-of-squares-of-odd-elements sequence)
  (accumulate *
              1
              (map square
                   (filter odd? sequence))))
(product-of-squares-of-odd-elements (list 1 2 3 4 5))

here's another example to get the highest programmer salary

(define (salary-of-highest-paid-programmer records)
  (accumulate max
              0
              (map salary
                   (filter programmer? records))))

this is just a hint of the great power conferred by sequence ops

we will use em to enable infinite sequences in 3.5

NESTED MAPPINGS

the sequence paradigm can be used in the fashion of nested loops
for this problem of pairs of numbers that add to primes

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

;; this is very common, we can express it like so
(define (flatmap proc seq)
  (accumulate append (list) (map proc seq)))

(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))
(define (make-pair-sum pair)
  (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
               (flatmap
                (lambda (i)
                  (map (lambda (j) (list i j))
                       (enumerate-interval 1 (- i 1))))
                (enumerate-interval 1 n)))))

to generate unique permutations of a set, {1 2 3} {2 1 3} {3 1 2} etc

(define (permutations s)
  (if (null? s)
      (list (list))
      (flatmap (lambda (x)
                 (map (lambda (p) (cons x p))
                      (permutations (remove x s))))
               s)))
(define (remove item sequence)
  (filter (lambda (x) (not (= x item)))
          sequence))

2.2.4 Example: A Picture Language

we are going to explore data abstraction, closure, and higher-order
procedures with the picture language

the language combines procedures as data

the picture language has only one primitive: painter

we can combine imagues by constructing new painters from given
painters

eg flip-vert takes a painter and produces a painter that paints
upside-down

we can combine these pictures with all the power of plain ol' scheme

im not really interested in this section: i see what they are getting
at and the lecture was dope, but i feel like im sitting on my thumbs
with no way to actually use painters

i do like the connection to geb

LEVELS OF LANGUAGE FOR ROBUST DESIGN

stratified design: a complex system should be structured as a
sequence of levels that are described using a sequence of
languages

each part is constructed using what it considers to be primitive

the level above takes those constructs as its primitives

the level below uses hidden concepts that are its own idea of
primitive

!! means of abstraction appropriate to the current level of detail