Section 16Want more of a challenge? View in iconic form (experimental)

# MATH illustrate lists and some list operators
# to make list describable as a function, need to preceed lists
# ... with an argument count
# Lists keep an explicit record of their length
# this is to avoid the need for using a special 'nil' symbol
# ... which cannot itself be placed in the list.
#
# missing - intro to cons, car, cdr
# used to be pure-cons pure-car pure-cdr but changed for better interface to scheme
# also should introduce number? check function
#
[hear] (define list-helper /
? n /
? ret /
if (> (n) 1)
(? x /
list-helper
(- (n) 1)
(? y /
? z /
ret (+ 1 (y)) (cons (x) (z))))
(? x /
ret 1 (x)));

[hear] (define list /
? n /
if (= (n) 0)
(cons 0 0)
(list-helper (n) (? y / ? z / cons (y) (z))));

? lst /
if (= (car / lst) 0)
(undefined)
(if (= (car / lst) 1)
(cdr /
lst)
(car /
cdr /
lst)));

[hear] (define tail /
? lst /
if (= (car / lst) 0)
(undefined)
(if (= (car / lst) 1)
(cons 0 0)
(cons (- (car / lst) 1) (cdr / cdr / lst))));

[hear] (define list-length / ? lst / car / lst);

[hear] (define list-ref /
? lst /
? n /
if (= (list-ref / lst) 0)
(undefined)
(if (= (n) 0)
lst)
(list-ref (tail / lst) (- (n) 1))));

[hear] (define prepend /
? x /
? lst /
if (= (list-length / lst) 0)
(cons 1 (x))
(cons (+ (list-length / lst) 1)
(cons (x) (cdr / lst))));

[hear] (define equal /
? x /
? y /
if (= (number? (x)) (number? (y)))
(if (number? (x)) (= (x) (y)) (list= (x) (y)))
(false));

[hear] (define list= /
? x /
? y /
if (= (list-length / x) (list-length / y))
(if (> (list-length / x) 0)
(list= (tail / x) (tail / y)))
(true))
(false));

[hear] (= (list-length / (list 5) 8 5 9 2 3) 5);

[hear] (= (list-length / (list 0)) 0);

[hear] (= (list-length / (list 4) 6 5 8 4) 4);

[hear] (= (list-length / (list 8) 8 3 1 6 0 2 7 4) 8);

[hear] (= (list-length / (list 1) 3) 1);

[hear] (= (head / (list 8) 2 4 7 5 14 14 16 1) 2);

[hear] (list= (tail /
(list 8) 2 4 7 5 14 14 16 1)
((list 7) 4 7 5 14 14 16 1));

[hear] (= (head / (list 9) 6 15 18 17 2 12 12 16 8) 6);

[hear] (list= (tail /
(list 9) 6 15 18 17 2 12 12 16 8)
((list 8) 15 18 17 2 12 12 16 8));

[hear] (= (head / (list 2) 16 13) 16);

[hear] (list= (tail / (list 2) 16 13) ((list 1) 13));

[hear] (= (head / (list 8) 18 9 10 15 2 12 15 17) 18);

[hear] (list= (tail /
(list 8) 18 9 10 15 2 12 15 17)
((list 7) 9 10 15 2 12 15 17));

[hear] (= (head / (list 2) 1 15) 1);

[hear] (list= (tail / (list 2) 1 15) ((list 1) 15));

(list 10) 1 14 7 3 5 11 1 17 13 15)
1);

[hear] (list= (tail /
(list 10) 1 14 7 3 5 11 1 17 13 15)
((list 9) 14 7 3 5 11 1 17 13 15));

[hear] (= (head / (list 4) 10 19 16 4) 10);

[hear] (list= (tail /
(list 4) 10 19 16 4)
((list 3) 19 16 4));

[hear] (= (head / (list 1) 15) 15);

[hear] (list= (tail / (list 1) 15) ((list 0)));

[hear] (= (head / (list 8) 11 5 11 8 5 8 3 14) 11);

[hear] (list= (tail /
(list 8) 11 5 11 8 5 8 3 14)
((list 7) 5 11 8 5 8 3 14));

[hear] (= (head / (list 5) 6 2 13 5 1) 6);

[hear] (list= (tail /
(list 5) 6 2 13 5 1)
((list 4) 2 13 5 1));

[hear] (= (list-ref ((list 1) 18) 0) 18);

[hear] (= (list-ref ((list 3) 3 15 16) 2) 16);

[hear] (= (list-ref ((list 5) 12 0 0 0 8) 0) 12);

[hear] (= (list-ref ((list 1) 3) 0) 3);

[hear] (= (list-ref ((list 2) 16 16) 0) 16);

[hear] (= (list-ref ((list 1) 0) 0) 0);

[hear] (= (list-ref ((list 2) 9 0) 1) 0);

[hear] (= (list-ref ((list 7) 11 5 7 19 9 18 2) 2) 7);

[hear] (= (list-ref ((list 3) 18 9 12) 1) 9);

[hear] (= (list-ref ((list 1) 0) 0) 0);

[hear] (list= ((list 0)) ((list 0)));

[hear] (list= ((list 1) 10) ((list 1) 10));

[hear] (list= ((list 2) 12 8) ((list 2) 12 8));

[hear] (list= ((list 3) 5 5 0) ((list 3) 5 5 0));

[hear] (list= ((list 4) 4 10 12 11)
((list 4) 4 10 12 11));

# this next batch of examples are a bit misleading, should streamline
[hear] (not / list= ((list 0)) ((list 1) 4));

[hear] (not / list= ((list 0)) ((list 1) 4));

[hear] (not / list= ((list 1) 5) ((list 2) 8 5));

[hear] (not / list= ((list 1) 5) ((list 2) 5 3));

[hear] (not /
list= ((list 2) 11 15) ((list 3) 4 11 15));

[hear] (not /
list= ((list 2) 11 15) ((list 3) 11 15 3));

[hear] (not /
list= ((list 3) 11 19 16) ((list 4) 4 11 19 16));

[hear] (not /
list= ((list 3) 11 19 16) ((list 4) 11 19 16 1));

[hear] (not /
list= ((list 4) 14 18 5 11)
((list 5) 6 14 18 5 11));

[hear] (not /
list= ((list 4) 14 18 5 11)
((list 5) 14 18 5 11 9));

[hear] (list= (prepend 6 ((list 0))) ((list 1) 6));

[hear] (list= (prepend 6 ((list 1) 11)) ((list 2) 6 11));

[hear] (list= (prepend 17 ((list 2) 11 4))
((list 3) 17 11 4));

[hear] (list= (prepend 18 ((list 3) 6 17 4))
((list 4) 18 6 17 4));

[hear] (list= (prepend 3 ((list 4) 8 11 1 10))
((list 5) 3 8 11 1 10));

[hear] (list= (prepend 7 ((list 5) 8 3 2 8 0))
((list 6) 7 8 3 2 8 0));

[hear] (list= (prepend 17 ((list 6) 14 15 14 19 9 3))
((list 7) 17 14 15 14 19 9 3));

[hear] (list= (prepend 17 ((list 7) 10 19 8 2 7 4 1))
((list 8) 17 10 19 8 2 7 4 1));

[hear] (define pair /
? x /
? y /
(list 2) (x) (y));

[hear] (define first / ? lst / head / lst);

[hear] (define second /
? lst /
tail /
lst);

[hear] (list= (pair 2 8) ((list 2) 2 8));

[hear] (= (first / pair 2 8) 2);

[hear] (= (second / pair 2 8) 8);

[hear] (list= (pair 6 0) ((list 2) 6 0));

[hear] (= (first / pair 6 0) 6);

[hear] (= (second / pair 6 0) 0);

[hear] (list= (pair 9 3) ((list 2) 9 3));

[hear] (= (first / pair 9 3) 9);

[hear] (= (second / pair 9 3) 3);

[hear] (define list-find-helper /
? lst /
? key /
? fail /
? idx /
if (= (list-length / lst) 0)
(fail 0)
(if (equal (head / lst) (key))
(idx)
(list-find-helper
(tail /
lst)
(key)
(fail)
(+ (idx) 1))));

[hear] (define list-find /
? lst /
? key /
? fail /
list-find-helper (lst) (key) (fail) 0);

[hear] (define example-fail / ? x 100);

[hear] (= (list-find ((list 1) 13) 13 (example-fail)) 0);

[hear] (= (list-find
((list 9) 15 17 16 12 3 15 2 4 13)
15
(example-fail))
0);

[hear] (= (list-find
((list 9) 19 0 14 18 9 11 12 5 19)
11
(example-fail))
5);

[hear] (= (list-find ((list 2) 15 1) 15 (example-fail))
0);

[hear] (= (list-find ((list 4) 0 7 19 1) 7 (example-fail))
1);

[hear] (= (list-find
((list 6) 9 9 1 10 5 19)
10
(example-fail))
3);

[hear] (= (list-find ((list 2) 17 1) 1 (example-fail))
1);

[hear] (= (list-find
((list 8) 0 3 16 13 19 13 18 11)
13
(example-fail))
3);

[hear] (= (list-find ((list 4) 15 6 2 1) 1 (example-fail))
3);

[hear] (= (list-find ((list 1) 3) 3 (example-fail)) 0);

[hear] (= (list-find ((list 4) 4 6 0 10) 1 (example-fail))
100);

[hear] (= (list-find
((list 6) 5 7 8 16 1 0)
13
(example-fail))
100);

[hear] (= (list-find
((list 8) 13 17 16 0 7 10 11 3)
15
(example-fail))
100);