SICP. 2.2–2.2.1
2023-03-29 Wed (updated on 2023-04-17 Mon)

2.2 Hierarchical Data and the Closure Property

Cons is used to ``glue`` two things together into a pair. This allows us to construct compound data.

We can represent a pair using the so-called box-and-pointer notation. This latter notation represents each object as a pointer to a box (the box for a pair is actually a double box): 

*Figure 2.2:* Box-and-pointer representation of `(cons 1 2)'.

          +---+---+     +---+
     ---->| * | *-+---->| 2 |
          +-|-+---+     +---+
            |
            V
          +---+
          | 1 |
          +---+

[Figure from SICP Unofficial Texinfo Format version 2.neilvandyke4 (January 10, 2007)]

We have already seen that cons can be used to combine not only numbers but pairs as well. […] As a consequence, pairs provide a universal building block from which we can construct all sorts of data structures. (p. 97, my emphasis)

The authors refer to the ability to create pairs whose elements are pairs as the closure property of cons, borrowing the term from abstract algebra.

Closure is the key to power in any means of combination because it permits us to create hierarchical structures — structures made up of parts, which themselves are made up of parts, and so on. (p. 98)

2.2.1 Representing Sequences

A sequence is a structure; it is an ordered collection of data objects.

We can build such a sequence in terms of pairs.There are many ways to build a sequence in terms of pairs. One way to do it, a particularly straightforward one, is to represent a sequence as a what the authors call list. A list is defined as ``a chain pairs terminated by the end-of-the-list marker''. More precisely: a list is a chain of one or more pairs, each of which is the cdr of the previous one, and the last one of which has nil as its cdr.1

Here is how we would represent the sequence 1,2,3,4 as a list: 

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

Scheme provide the primitive list to create such sequences. 

(list <a_1> <a_2> ... <a_n>)

is equivalent to 

(cons ⟨a_1⟩
      (cons ⟨a_2⟩
            (cons ...
                  (cons ⟨a_n⟩
                   nil)...)))

Do not confuse (list 1 2 3 4) with (1 2 3 4)…

car, cdr, cadr, etc. are introduced. nil can be thought of as a sequence with no elements, the empty list.

Some typical list operations:

  • length:

    • recursive-process-evolving: 

      (define (length items)
  (if (null? items)
      0
      (+ 1 (length (cdr items)))))

    • iterative-process-evolving: 

      (define (length items)
  (define (length-iter a count)
    (if (null? items)
        count
        (length-iter (cdr a) (+ 1 count))))
  (length-iter items 0))

  • list-ref: 

    (define (list-ref items n)
  (if (= n 0)
      (car items)
      (list-ref (cdr items) (- n 1))))

  • append: 

    (define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1)
            (append (cdr list1) list2))))
  • map:
(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))

These operations above exemplify the techniques of ``cdring down'' and ``consing up''.

map deserves some comments, for not only it represents a common pattern, but it also ``establishes a higher level of abstraction in dealing with lists''.

Consider: 

(define (scale-list items factor)
  (if (null? items)
      nil
      (cons (* (car items) factor)
            (scale-list (cdr items) factor))))

(scale-list (list 1 2 3 4 5) 10)
(10 20 30 40 50)

Now consider a definition of scale-list in terms of map: 

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

The definition of scale-list in terms of map ``suppresses that level of detail and emphasizes that scaling transforms a list of elements to a list of results.'' ``…this abstraction gives us the flexibility to change the low-level details of how sequences are implemented, while preserving the conceptual framework of operations that transform sequences to sequences.''

Exercise 2.17

Exercise:

Define a procedure last-pair that returns the list that contains only the last element of a given (nonempty) list: 

(last-pair (list 23 72 149 34))
(34)

Answer: 

(define (last-pair l)
  (if (null? (cdr l))
      l
      (last-pair (cdr l))))

Exercise 2.18

Exercise:

Define a procedure `reverse' that takes a list as argument and returns a list of the same elements in reverse order: 

(reverse (list 1 4 9 16 25))
(25 16 9 4 1)

Answer:

My intuitive solution was interative: 

(define (reverse l)
  (define (reverse-iter l result)
    (if (null? l)
        result
        (reverse-iter (cdr l) (cons (car l) result))))
  (reverse-iter l (list)))

After having solved the exercise iteratively, I've looked for a recursive solution on the web and I've found this one: 

(define (reverse l)
  (if (null? l)
      nil
      (append (reverse (cdr l))
              (list (car l)))))

Exercise 2.20

Exercise:

The procedures +, *, and list take arbitrary numbers of arguments. One way to define such procedures is to use define with dotted-tail notation. In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter’s value will be a list of any remaining arguments. For instance, given the definition 

(define (f x y . z) ⟨body⟩)

the procedure f can be called with two or more arguments. If we evaluate 

(f 1 2 3 4 5 6)

then in the body of f, x will be 1, y will be 2, and z will be the list (3 4 5 6). Given the definition 

(define (g . w) ⟨body⟩)

the procedure g can be called with zero or more arguments. If we evaluate 

(g 1 2 3 4 5 6)

then in the body of g, w will be the list (1 2 3 4 5 6).

[ fn: To define f and g using lambda we would write 

(define f (lambda (x y . z) ⟨body⟩))
(define g (lambda w ⟨body⟩))

]

Use this notation to write a procedure same-parity that takes one or more integers and returns a list of all the arguments that have the same even-odd parity as the first argument. For example, 

(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)

(same-parity 2 3 4 5 6 7)
(2 4 6)

Answer: 

;; iterative solution (three slightly different versions):

(define (same-parity1 i . rest)
  (define (condition i1 i2)
    (= (remainder i1 2)
       (remainder i2 2)))
  (define (same-party-inner i l result)
    (if (null? l)
        result
        (same-party-inner i
                          (cdr l)
                          (if (condition i (car l))
                              (cons (car l) result)
                              result))))
  (cons i (reverse (same-party-inner i rest (list)))))

(define (same-parity2 i . rest)
  (define (condition i1 i2)
    (= (remainder i1 2)
       (remainder i2 2)))
  (define (same-party-inner i l result)
    (if (null? l)
        result
        (same-party-inner i
                          (cdr l)
                          (if (condition i (car l))
                              (cons (car l) result)
                              result))))
  (reverse (same-party-inner i rest (list i))))

(define (same-parity3 i . rest)
  (define (condition i1 i2)
    (= (remainder i1 2)
       (remainder i2 2)))
  (define (same-party-inner i l result)
    (if (null? l)
        result
        (same-party-inner i
                          (cdr l)
                          (if (condition i (car l))
                              (append result (list (car l)))
                              result))))
  (same-party-inner i rest (list i)))

(same-parity1 1 2 3 4 5 6 7) ;; (1 3 5 7)
(same-parity2 1 2 3 4 5 6 7) ;; (1 3 5 7)
(same-parity3 1 2 3 4 5 6 7) ;; (1 3 5 7)
←

Footnotes:

1

The Racket documentation defines a list as ``a combination of pairs that creates a linked list. More precisely, a list is either the empty list null, or it is a pair whose first element is a list element and whose second element is a list.''

Send me an email for comments.

Created with Emacs 28.2 (Org mode 9.5.5)