# MATH illustrate lists and some list operators
# to make list describable as a function, need to preceed lists
# ... with an argument count
# lists will be written as [1 2 1] = (list 3 1 2 1) after this lesson
# it would be nice to include such syntactic sugar in the message but that
# ... is a fight for another day
# finally, 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))));
[hear] (define head /
? 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)
(head /
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 list= /
? x /
? y /
if (= (list-length / x) (list-length / y))
(if (> (list-length / x) 0)
(and (= (head / x) (head / y))
(list= (tail / x) (tail / y)))
(true))
(false));
[hear] (= (list-length / (list 4) 4 8 5 0) 4);
[hear] (= (list-length / (list 5) 3 1 4 6 5) 5);
[hear] (= (list-length / (list 6) 5 0 3 4 7 8) 6);
[hear] (= (list-length / (list 7) 0 8 7 4 9 1 5) 7);
[hear] (= (list-length / (list 3) 0 3 6) 3);
[hear] (= (head / (list 5) 9 9 12 16 0) 9);
[hear] (list= (tail /
(list 5) 9 9 12 16 0)
((list 4) 9 12 16 0));
[hear] (= (head / (list 2) 1 16) 1);
[hear] (list= (tail / (list 2) 1 16) ((list 1) 16));
[hear] (= (head / (list 8) 17 11 7 14 0 12 13 11) 17);
[hear] (list= (tail /
(list 8) 17 11 7 14 0 12 13 11)
((list 7) 11 7 14 0 12 13 11));
[hear] (= (head / (list 8) 15 17 8 6 10 18 19 14) 15);
[hear] (list= (tail /
(list 8) 15 17 8 6 10 18 19 14)
((list 7) 17 8 6 10 18 19 14));
[hear] (= (head / (list 4) 4 7 12 12) 4);
[hear] (list= (tail /
(list 4) 4 7 12 12)
((list 3) 7 12 12));
[hear] (= (head / (list 4) 6 10 6 8) 6);
[hear] (list= (tail /
(list 4) 6 10 6 8)
((list 3) 10 6 8));
[hear] (= (head / (list 2) 9 4) 9);
[hear] (list= (tail / (list 2) 9 4) ((list 1) 4));
[hear] (= (head / (list 9) 7 4 19 17 14 10 5 7 5) 7);
[hear] (list= (tail /
(list 9) 7 4 19 17 14 10 5 7 5)
((list 8) 4 19 17 14 10 5 7 5));
[hear] (= (head / (list 1) 11) 11);
[hear] (list= (tail / (list 1) 11) ((list 0)));
[hear] (= (head / (list 1) 1) 1);
[hear] (list= (tail / (list 1) 1) ((list 0)));
[hear] (= (list-ref ((list 3) 16 2 19) 1) 2);
[hear] (= (list-ref ((list 9) 19 15 15 13 17 6 10 17 14) 0)
19);
[hear] (= (list-ref ((list 5) 13 13 10 16 7) 2) 10);
[hear] (= (list-ref ((list 7) 6 17 19 3 0 14 15) 1) 17);
[hear] (= (list-ref ((list 10) 17 3 1 4 15 0 3 10 13 9) 2)
1);
[hear] (= (list-ref ((list 4) 8 0 6 18) 0) 8);
[hear] (= (list-ref
((list 10) 13 19 19 15 13 11 15 11 3 7)
6)
15);
[hear] (= (list-ref ((list 5) 10 13 7 10 5) 1) 13);
[hear] (= (list-ref ((list 2) 5 2) 1) 2);
[hear] (= (list-ref ((list 1) 14) 0) 14);
[hear] (list= ((list 0)) ((list 0)));
[hear] (list= ((list 1) 7) ((list 1) 7));
[hear] (list= ((list 2) 9 4) ((list 2) 9 4));
[hear] (list= ((list 3) 1 2 13) ((list 3) 1 2 13));
[hear] (list= ((list 4) 17 17 9 6) ((list 4) 17 17 9 6));
# 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) 3));
[hear] (not / list= ((list 1) 7) ((list 2) 4 7));
[hear] (not / list= ((list 1) 7) ((list 2) 7 0));
[hear] (not /
list= ((list 2) 17 10) ((list 3) 1 17 10));
[hear] (not /
list= ((list 2) 17 10) ((list 3) 17 10 3));
[hear] (not /
list= ((list 3) 12 11 3) ((list 4) 5 12 11 3));
[hear] (not /
list= ((list 3) 12 11 3) ((list 4) 12 11 3 1));
[hear] (not /
list= ((list 4) 8 11 3 17)
((list 5) 1 8 11 3 17));
[hear] (not /
list= ((list 4) 8 11 3 17)
((list 5) 8 11 3 17 3));
# some helpful functions
[hear] (list= (prepend 12 ((list 0))) ((list 1) 12));
[hear] (list= (prepend 5 ((list 1) 15)) ((list 2) 5 15));
[hear] (list= (prepend 16 ((list 2) 13 17))
((list 3) 16 13 17));
[hear] (list= (prepend 13 ((list 3) 12 4 11))
((list 4) 13 12 4 11));
[hear] (list= (prepend 12 ((list 4) 7 16 4 18))
((list 5) 12 7 16 4 18));
[hear] (list= (prepend 6 ((list 5) 15 19 17 17 6))
((list 6) 6 15 19 17 17 6));
[hear] (list= (prepend 12 ((list 6) 18 3 18 11 7 9))
((list 7) 12 18 3 18 11 7 9));
[hear] (list= (prepend 15 ((list 7) 19 14 13 16 8 1 10))
((list 8) 15 19 14 13 16 8 1 10));
[hear] (define pair /
? x /
? y /
(list 2) (x) (y));
[hear] (define first / ? lst / head / lst);
[hear] (define second /
? lst /
head /
tail /
lst);
[hear] (list= (pair 3 8) ((list 2) 3 8));
[hear] (= (first / pair 3 8) 3);
[hear] (= (second / pair 3 8) 8);
[hear] (list= (pair 7 4) ((list 2) 7 4));
[hear] (= (first / pair 7 4) 7);
[hear] (= (second / pair 7 4) 4);
[hear] (list= (pair 9 7) ((list 2) 9 7));
[hear] (= (first / pair 9 7) 9);
[hear] (= (second / pair 9 7) 7);
[hear] (define list-find-helper /
? lst /
? key /
? fail /
? idx /
if (= (list-length / lst) 0)
(fail 0)
(if (= (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 5) 5 4 2 1 0) 4 (example-fail))
1);
[hear] (= (list-find ((list 1) 5) 5 (example-fail)) 0);
[hear] (= (list-find
((list 5) 5 4 3 17 8)
4
(example-fail))
1);
[hear] (= (list-find ((list 4) 10 3 3 2) 10 (example-fail))
0);
[hear] (= (list-find
((list 7) 18 8 12 5 13 13 0)
13
(example-fail))
4);
[hear] (= (list-find
((list 6) 0 10 14 15 3 17)
15
(example-fail))
3);
[hear] (= (list-find
((list 9) 15 10 16 0 16 2 16 8 9)
10
(example-fail))
1);
[hear] (= (list-find ((list 3) 10 18 14) 18 (example-fail))
1);
[hear] (= (list-find ((list 2) 13 13) 13 (example-fail))
0);
[hear] (= (list-find
((list 7) 13 19 13 19 9 19 1)
13
(example-fail))
0);
[hear] (= (list-find ((list 4) 1 7 16 15) 6 (example-fail))
100);
[hear] (= (list-find
((list 6) 5 10 13 7 12 19)
8
(example-fail))
100);
[hear] (= (list-find
((list 8) 19 7 13 1 11 12 8 2)
16
(example-fail))
100);