equal
deleted
inserted
replaced
1 (* Title: ZF/List |
1 (* Title: ZF/List |
2 ID: $Id$ |
2 ID: $Id$ |
3 Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
3 Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
4 Copyright 1994 University of Cambridge |
4 Copyright 1994 University of Cambridge |
5 |
5 |
6 Lists in Zermelo-Fraenkel Set Theory |
6 Lists in Zermelo-Fraenkel Set Theory |
7 |
7 |
8 map is a binding operator -- it applies to meta-level functions, not |
8 map is a binding operator -- it applies to meta-level functions, not |
11 *) |
11 *) |
12 |
12 |
13 List = Datatype + |
13 List = Datatype + |
14 |
14 |
15 consts |
15 consts |
16 "@" :: [i,i]=>i (infixr 60) |
16 "@" :: [i,i]=>i (infixr 60) |
17 list_rec :: [i, i, [i,i,i]=>i] => i |
17 list_rec :: [i, i, [i,i,i]=>i] => i |
18 map :: [i=>i, i] => i |
18 map :: [i=>i, i] => i |
19 length,rev :: i=>i |
19 length,rev :: i=>i |
20 flat :: i=>i |
20 flat :: i=>i |
21 list_add :: i=>i |
21 list_add :: i=>i |
22 hd,tl :: i=>i |
22 hd,tl :: i=>i |
23 drop :: [i,i]=>i |
23 drop :: [i,i]=>i |
24 |
24 |
25 (* List Enumeration *) |
25 (* List Enumeration *) |
26 "[]" :: i ("[]") |
26 "[]" :: i ("[]") |
27 "@List" :: is => i ("[(_)]") |
27 "@List" :: is => i ("[(_)]") |
28 |
28 |
29 list :: i=>i |
29 list :: i=>i |
30 |
30 |
31 |
31 |
32 datatype |
32 datatype |
33 "list(A)" = Nil | Cons ("a:A", "l: list(A)") |
33 "list(A)" = Nil | Cons ("a:A", "l: list(A)") |
34 |
34 |
39 "[]" == "Nil" |
39 "[]" == "Nil" |
40 |
40 |
41 |
41 |
42 defs |
42 defs |
43 |
43 |
44 hd_def "hd(l) == list_case(0, %x xs.x, l)" |
44 hd_def "hd(l) == list_case(0, %x xs.x, l)" |
45 tl_def "tl(l) == list_case(Nil, %x xs.xs, l)" |
45 tl_def "tl(l) == list_case(Nil, %x xs.xs, l)" |
46 drop_def "drop(i,l) == rec(i, l, %j r. tl(r))" |
46 drop_def "drop(i,l) == rec(i, l, %j r. tl(r))" |
47 |
47 |
48 list_rec_def |
48 list_rec_def |
49 "list_rec(l,c,h) == Vrec(l, %l g.list_case(c, %x xs. h(x, xs, g`xs), l))" |
49 "list_rec(l,c,h) == Vrec(l, %l g.list_case(c, %x xs. h(x, xs, g`xs), l))" |
50 |
50 |
51 map_def "map(f,l) == list_rec(l, Nil, %x xs r. Cons(f(x), r))" |
51 map_def "map(f,l) == list_rec(l, Nil, %x xs r. Cons(f(x), r))" |