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