1 : (5 : (3 : (8 : nil))) = [1, 5, 3, 8]

intsfrom n == n : intsfrom (n+1)

> intsfrom 5
5 : intsfrom (5+1)
print [ 5
intsfrom (5+1)
(5+1) : intsfrom ((5+1)+1)
print ,
6 : intsfrom (6+1)
print 6
intsfrom (6+1)
(6 + 1) : intsfrom ((6+1)+1)
print ,
7 : intsfrom (7+1)
print 7

[ 5, 6, 7, 8, 9, 10, 11, 12, 13, ....
....
....
.... control-C
> notdiv a == { x -> x % a /= 0 }
> (notdiv 3) 7
{ x -> x % 3 /= 0 } 7
7 % 3 /= 0
1 /= 0
true
> filter f [] == []
> filter f (a : b) == a : filter f b <| f a |> filter f b
> filter (notdiv 3) (3 : 4 : 6 : 8 : [])
     f = (notdiv 3)
     a = 3
     b = (4 : 6 : 8 : [])
filter (notdiv 3) (4 : 6 : 8 : [])
     f = (notdiv 3)
     a = 4
     b = (6 : 8 : [])
4 : filter (notdiv 3) (6 : 8 : [])
     f = notdiv 3
     a = 6
     b = (8 : [])
4 : filter (notdiv 3) (8 : [])
     f = notdiv 3
     a = 8
     b = []
4 : 8 : filter (notdiv 3) []
4 : 8 : []
filter (notdiv 3) [3, 4, 6, 8] -> [ 4, 8 ]

filter { x -> x % 3 /= 0 } [3, 4, 6, 8]


era (a : b) = a : era (filter (notdiv a) b)
> era (intsfrom 2)
era (2 : instfrom 3)
2 : era (filter (notdiv 2) (intsfrom 3))
2 : era (filter (notdiv 2) (3: (intsfrom 4)))
2 : era (3 : filter (notdiv 2) (intsfrom 4))
2 : 3 : era (filter (notdiv 3) (filter (notdiv 2 (intsfrom 4))))
intsfrom -> I
filter -> F
notdiv -> N
2 : 3 : era (F (N 3) (F (N 2) (I 4))))
2 : 3 : era (F (N 3) (F (N 2) (4 : I 5)))))
evaluate leftmost evaluatable thing first
LEFT DERIVATION
2 : 3 : era (F (N 3) (F (N 2) (I 5)))))
2 : 3 : era (F (N 3) (F (N 2) (5 :(I 6))))))
2 : 3 : era (F (N 3) (5 : F (N 2) (I 6))))))
2 : 3 : era (5 : F (N 3) (F (N 2) (I 6))))))
2 : 3 : 5 : era (F (N 5) (F (N 3) (F (N 2) (I 6))))))
pretend it's a right derivation
2 : 3 : 5 : era (F (N 5) (F (N 3) (F (N 2) [6,7,8,9,10,...])))))
2 : 3 : 5 : era (F (N 5) (F (N 3) [7,9,11,13,15,17,...])))
2 : 3 : 5 : era [7,11,13,17,19,23,...]))
2 : 3: 5: 7: era [11,13,17,19,23,29,31,...
era = sieve of Eratsothenes

2 3 5 7 11 13 17 19 23 


era (a : b) = a : era (filter (notdiv a) b)
era (intsfrom 2)

LAZY EVALUATION = don't evaluate anything until it's needed.






e.g.  
   insert 7 [2,4,6,9,10,13]
 = [2,4,6,7,9,10,13]

insert n [] == [ n ]
insert n (a : b) == a : (insert n b)
                    <| a < n |>
                    n : a : b

insert 7 (2:4:6:9:10:13:[])        -- n=7 a=2 b=4,6,9,...
2 : insert 7 (4:6:9:10:13:[])      -- n=7 a=4 b=6,9,10,13
2 : 4 : insert 7 (6:9:10:13:[])    -- n=7 a=6 b=9,10,13
2 : 4 : 6 : insert 7 (9:10:13:[])  -- n=7 a=9 b=10,13
2 : 4 : 6 : 7 : 8 : 10 : 13 : []
[ 2, 4, 6, 7, 8, 10, 13 ]

sort [] == []
sort (a : b) == insert a (sort b)


oddsplit [0,1,2,3,4,5,6,7] = [1,3,5,7]
evensplit [0,1,2,3,4,5,6,7] = [0,2,4,6]
oddsplit [1,2,3,4,5,6,7] = [2,4,6]
0 : oddsplit [1,2,3,4,5,6,7] = [0,2,4,6]

evensplit [] == []
evensplit (a : b) == a : oddsplit b

oddsplit [] == []
oddsplit (a : b) == evensplit b

es [a,b,c,d,e,f,g]
a : os [b,c,d,e,f,g]
a : es [c,d,e,f,g]
a : c : os [d,e,f,g]
a : c : es [e,f,g]
a : c : e : os [f,g]
a : c : e : es [g]
a : c : e : g : os []
a : c : e : g : []
[a,c,e,g]





merge [] [] == []
merge (a:b) [] == (a:b)
merge [] (c:d) == (c:d)
merge (a:b) (c:d) == a : merge b (c:d)
                     <| a < c |>
                     c : merge (a:b) d


merge [2,5,6] [1,3,4]
1 : merge [2,5,6] [3,4]
1 : 2 : merge [5,6] [3,4]
1 : 2 : 3 : merge [5,6] [4]
1 : 2 : 3 : 4 : merge [5,6] []
1 : 2 : 3 : 4 : 5 : 6 : []

msort [] == []
msort [a] == [a]
msort x == merge (msort (evensplit x)) (msort (oddsplit x))