src/ZF/List.thy

do require perl;

(*  Title:      ZF/List
    ID:         $Id$
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
    Copyright   1994  University of Cambridge

Lists in Zermelo-Fraenkel Set Theory 

map is a binding operator -- it applies to meta-level functions, not 
object-level functions.  This simplifies the final form of term_rec_conv,
although complicating its derivation.
*)

List = Datatype + 

consts
  list       :: i=>i
  
datatype
  "list(A)" = Nil | Cons ("a:A", "l: list(A)")


syntax
 "[]"        :: i                                       ("[]")
 "@List"     :: is => i                                 ("[(_)]")

translations
  "[x, xs]"     == "Cons(x, [xs])"
  "[x]"         == "Cons(x, [])"
  "[]"          == "Nil"


constdefs
  hd      :: i=>i
  "hd(l)       == list_case(0, %x xs. x, l)"
  
  tl      :: i=>i
  "tl(l)       == list_case(Nil, %x xs. xs, l)"
  
  drop       :: [i,i]=>i
  "drop(i,l)   == rec(i, l, %j r. tl(r))"

  list_rec   :: [i, i, [i,i,i]=>i] => i
  "list_rec(l,c,h) == Vrec(l, %l g. list_case(c, %x xs. h(x, xs, g`xs), l))"

  map        :: [i=>i, i] => i
  "map(f,l)    == list_rec(l,  Nil,  %x xs r. Cons(f(x), r))"

  length :: i=>i
  "length(l)   == list_rec(l,  0,  %x xs r. succ(r))"

  set_of_list :: i=>i
  "set_of_list(l)   == list_rec(l,  0,  %x xs r. cons(x,r))"

consts  (*Cannot use constdefs because @ is not an identifier*)
  "@"        :: [i,i]=>i                        (infixr 60)
defs
  app_def       "xs@ys       == list_rec(xs, ys, %x xs r. Cons(x,r))"


constdefs
  rev :: i=>i
  "rev(l)      == list_rec(l,  Nil,  %x xs r. r @ [x])"

  flat       :: i=>i
  "flat(ls)    == list_rec(ls, Nil,  %l ls r. l @ r)"

  list_add   :: i=>i
  "list_add(l) == list_rec(l, 0,  %x xs r. x#+r)"

end