src/ZF/List.thy
changeset 1478 2b8c2a7547ab
parent 1401 0c439768f45c
child 1806 12708740f58d
equal deleted inserted replaced
1477:4c51ab632cda 1478:2b8c2a7547ab
     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))"