Menu

- Chapter 1 Distilled
- Introduction
- 1.1 - The Elements Of Programming
- Expressions
- Naming and the Environment
- Evaluating Combinations
- Defining New Functions
- The Substitution Model
- Exercises
- Predicates
- Conditional Expressions
- Example: Newton’s Method
- Functions as Black-Box Abstractions
- 1.2 - Procedures and the Processes They Generate
- Linear Recursion and Iteration
- Tree Recursion
- Orders of Growth
- Exponentiation
- Example: Testing For Primality
- 1.3 Higher Order Functions
- Project - Blackjack

- Chapter 2 Distilled
- Introduction
- Data Abstraction
- Everything From Nothing
- Abstractions In Clojure
- Clojure's Data Structures
- Data Abstraction, Revisited
- Escher
- Project - Escher
- Symbolic Data
- Representing Sets
- Huffman Encoding Trees
- Zippers

It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures. Alan J. Perlis - Forward

We have seen in the section on Data Abstraction the only data
structure used in the original SICP, the `cons`

cell (and I hinted
that Clojure provides us with more choices, we will see them soon).

A way of representing the list structured data created by `cons`

is
the *box-and-pointer diagram*. The box for a primitive object contains
a representation of the object. For example, the box for a number
contains a numeral. The box for a pair is actually a double box, the
left part containing (a pointer to) the car of the pair and the right
part containing the cdr.

Above are a few different ways to combine 1,2,3,4 using `cons`

A very common pattern is the sequence (an ordered collection of data
objects), the usual way to do this with `cons`

is depicted below

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

See, the chain of `cons`

's is represented in the REPL as a *list*. You
have of course seen lists already, expressions are made of them.

The value of nil , used to terminate the chain of pairs, can be thought of as a sequence of no elements, the empty list . The word nil is a contraction of the Latin word nihil, which means "nothing".

We can create lists using the `list`

function, and can `cons`

things
onto the beginning of existing lists.

```
> (def upto4 (list 1 2 3 4))
> upto4
(1 2 3 4)
> (cons 5 upto4)
(5 1 2 3 4)
```

Be careful not to confuse the expression `(list 1 2 3 4)`

with the
list `(1 2 3 4)`

, which is the result obtained when the expression is
evaluated. Attempting to evaluate the expression `(1 2 3 4)`

will signal
an error when the interpreter tries to apply the procedure 1 to
arguments 2, 3, and 4.

`cons`

In Data Abstraction we spoke about `cons`

`car`

and `cdr`

as they
are defined in SICP, and saw how we could implement them as
functions. The above examples do work in Clojure, but some of the
things we did earlier will not:

```
> (cons 1 2)
IllegalArgumentException Don't know how to create ISeq from:
java.lang.Long clojure.lang.RT.seqFrom (RT.java:505)
```

This confusing error message is because `cons`

in clojure is only for
working with lists, the second argument must be a list. The reference
to `ISeq`

mean that `2`

is not the correct type for `cons`

, it is
expecting a *sequence*.

Given a sequence, you can use `first`

to get the first element and
`rest`

to get the sequence without the first element (`first`

and
`rest`

are the equivalent of `car`

and `cdr`

for lists.

```
> (def l (list 1 2 3 4))
> l
(1 2 3 4)
> (first l)
1
> (rest l)
(2 3 4)
```

Using just these two functions you can perform many functions on lists.

For example, the procedure `nth`

takes as arguments a list and a
number $n$ and returns the $nth$ item of the list. It is customary to
number the elements of the list beginning with `0`

.

A method for computing `nth`

is the following:

- For $n = 0$, list-ref should return the car of the list.
- Otherwise, list-ref should return the $(n − 1)^{th}$ item of the cdr of the list.

```
> (defn nth [items n]
(if (= n 0)
(first items)
(recur (rest items) (- n 1))))
> (define squares (list 0 1 4 9 16 25))
> (nth squares 3)
9
```

Note here that we recur and that `n`

always decreases and the `items`

list always gets smaller, this is a good sign that it will terminate.