# SICP Goodness - From Pair to Flatmap (I)

Explore the power of list

Do you think Computer Science

equalsbuilding websites and mobile apps?Are you feeling that you are doing

repetitiveandnot so intelligentwork?Are you feeling a bit

sickaboutreading manualsandcopy-pastingcode and keeppoking arounduntil it worksall day long?Do you want to understand the

soulofComputer Science?If yes,

read SICP!!!

Sequence is an important data structure in any programming language, especially in Lisp. In this article, we will look at how it is built and what can we do with it.

# Pair

Pair is a very simple data structure, it glues two objects together, and provides selectors for each of them.

In Scheme the function `cons`

is used to create pairs. For example, `(cons 1 2)`

. This can be illustrated by using the *box-and-pointer notation*:

Each object is shown as a pointer to a box. The box for a primitive object contains a representation of the object. For example, the box for a number contains a number. The box for a pair is actually a double box, the left part containning the first object of the pair, and the right part containning the second one.

`car`

is the selector for the first object and `cdr`

is the selector for the second object.

```
(car (cons 1 2))
;;=> 1
(cdr (cons 1 2))
;;=> 2
```

Let’s say we want to combine 1, 2, 3, 4 using pairs. There are actually many ways of doing this. For example:

```
;; Two ways of combining 1,2,3,4 using pairs
(cons (cons 1 2) (cons 3 4))
(cons (cons 1 (cons 2 3)) 4)
```

They can be illustrated respectively as follows:

# Sequence

Now we can construct **sequences**(an *ordered* collection of data objects) by chaining pairs.

For example to construct sequence of 1, 2, 3 and 4, we can do:

```
(cons 1 (cons 2 (cons 3 (cons 4 '()))))
```

Such a sequence of pairs formed by nested `cons`

is called a list, and Scheme provides a primitive called `list`

to help with creating lists.

```
;; the followings are the same
(list 1 2 3 4)
(cons 1 (cons 2 (cons 3 (cons 4 '()))))
```

# List Operations

### car and cdr

`car`

selects the first item in the list and `cdr`

select the rest items (a sublist) of the list.

```
(car (list 1 2 3 4)) ;; 1
(cdr (list 1 2 3 4)) ;; (2 3 4)
```

### n*th* element of the list

We implement this by `cdr`

ing down the list and stop at the right element.

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

## The Length of the List

Sometimes we need to `cdr`

ing down the whole list, so we need a way to stop. Primitive `null?`

tells if a list if an empty list.

```
(null? '()) ;Value: #t
(null? (list 1 2)) ;Value #f
```

Now let’s implement a function to calculate the length of the list.

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

We can also write a iterative version.

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

# Append Two Lists

This is implemented by *cons up* a result list while *cdring* down a list.

```
(define (append list1 list2)
(if (null? list1)
list2
(cons (car list1) (append (cdr list1) list2))))
```

**Two exercises:**

*Write a function to reverse a list.*

```
(define (reverse items)
(if (null? items)
'()
(append (reverse (cdr items)) (list (car items)))))
```

*Write a function to get the last pair in the list.*

```
(define (last-pair items)
(cond ((null? items) '())
((null? (cdr items)) items)
(else (last-pair (cdr items)))))
```

Part II of this series can be found here.

## Share this post

Twitter

Google+

Facebook

Reddit

LinkedIn

StumbleUpon

Email