# 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.