wiki:Tutorial5

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.

Last modified 14 months ago Last modified on 18/02/13 10:13:24