# Lists

Logically, there are different kinds of lists.

Just plain, FLAT lists. This means, by convention, they CANNOT have another list as one of its element, except the the-empty-list at the end.

As long as this rule holds, we could have flat lists of atoms and the procedures to manipulate its elements:

There are naive versions of classic procedures for the flat lists-of-atoms.

These must be memorized and meditated upon, to realize the beauty.

Remember, that they are so compact, self-evident and beautiful because they are based upon the small set of simple rules.

length - naive, but beautiful

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

length

```(define (length1 l)
(let f ((x 0) (l l))
(if (null? l)
x
(f (+ 1 x) (cdr l)))))  ; a tail call
```

reverse

```(define (reverse l)                      ; naive
(if (null? l)
'()
(append (reverse (cdr l)) (list (car l)))))
```

reverse - simply beautiful

```(define (reverse l)
(let f ((r '()) (l l))
(if (null? l)
r
(f (cons (car l) r) (cdr l)))))   ; a tail call
```

range/enumerate-interval

```(define (range lo hi)
(if (> lo hi)
'()
(cons lo (range (+ 1 lo) hi))))
```

append

```(define (append l1 l2)              ; naive yet beautiful
(if (null? l1)
l2
(cons (car l1)
(append (cdr l1) l2))))
```

map

```(define (map fn l)
(if (null? l)
'()
(cons (fn (car l))
(map fn (cdr l)))))
```

filter/keep

```(define (filter fn l)
(cond ((null? l) '())
((fn (car l)) (cons (car l) (filter fn (cdr l))))
(else (filter fn (cdr l)))))
```

reduce/accumulate

```(define (reduce fn i l)
(if (null? l)
i
(fn (car l)
(reduce fn i (cdr l)))))
```

atom?

```(define (atom? x)
(not (pair? x)))
```

some?

```(define (some? fn l)
(if (atom? l)
#f
(or (fn (car l)) (some? fn (cdr l)))))
```

every?

```(define (every? fn l)
(cond ((null? l) #t)
((atom? l) (fn xs))
(else (and (fn (car l)) (every? fn (cdr l))))))
```

nth

```(define (nth x l)
(let f ((x x) (l l))
(cond ((null? l) #f)
((zero? x) (car l))
(else (f (- x 1) (cdr l))))))
```

member?

```(define (member? x l)
(cond ((null? l) #f)
((eq? x (car l)) #t)
(else (member? x (cdr l)))))
```

for-each

```(define (for-each fn l)
(if (not (null? l))
(begin (fn (car l))
(for-each fn (cdr l)))))
```

quicksort

```(define (quicksort l gt?)
(if (null? l)
'()
(append (quicksort (filter (lambda (x) (gt? (car l) x)) (cdr l)) gt?)
(list (car l))
(quicksort (filter (lambda (x) (not (gt? (car l) x))) (cdr l)) gt?))))

```

To work with NESTED lists, which could containg another list as its element, we need slightly different, more stuffed set of procedures:

map1

```(define (map1 fn xs)
(cond ((null? xs) '())
((atom? xs) (fn xs))
(else (cons (map1 fn (car xs))
(map1 fn (cdr xs))))))
```

This code can traverse any structure which made out of pairs.

some?

```(define (some? fn xs)
(if (atom? xs)
#f
(or (some? fn (car xs)) (some? fn (cdr xs)))))
```

every?

```(define (every? fn xs)
(cond ((null? xs) #t)
((atom? xs) (fn xs))
(else (and (every fn (car xs)) (every fn (cdr xs))))))
```

Now the piece of amazing beauty from CS 61A.

```(define make-tree cons)
(define datum car)
(define children cdr)
(define (leaf? n)
(null? (children n)))

(define (tree-map fn tree)
(make-tree (fn (datum tree))                   ; domain-and-range mantra
(map (lambda (l) (tree-map fn l))   ; base-case is handled by map
(children tree))))
```

No fucking pages of Classes, Iterators, irrelevant stuff. Just bunch of synonyms and then pure joy and happiness.

This is joy of programming.