src/HOL/ex/Simult.thy

expanded tabs

(*  Title: 	HOL/ex/Simult
    ID:         $Id$
    Author: 	Lawrence C Paulson, Cambridge University Computer Laboratory
    Copyright   1993  University of Cambridge

A simultaneous recursive type definition: trees & forests

This is essentially the same data structure that on ex/term.ML, which is
simpler because it uses list as a new type former.  The approach in this
file may be superior for other simultaneous recursions.

The inductive definition package does not help defining this sort of mutually
recursive data structure because it uses Inl, Inr instead of In0, In1.
*)

Simult = SList +

types    'a tree
         'a forest

arities  tree,forest :: (term)term

consts
  TF          :: 'a item set => 'a item set
  FNIL        :: 'a item
  TCONS,FCONS :: ['a item, 'a item] => 'a item
  Rep_Tree    :: 'a tree => 'a item
  Abs_Tree    :: 'a item => 'a tree
  Rep_Forest  :: 'a forest => 'a item
  Abs_Forest  :: 'a item => 'a forest
  Tcons       :: ['a, 'a forest] => 'a tree
  Fcons       :: ['a tree, 'a forest] => 'a forest
  Fnil        :: 'a forest
  TF_rec      :: ['a item, ['a item , 'a item, 'b]=>'b,     
                 'b, ['a item , 'a item, 'b, 'b]=>'b] => 'b
  tree_rec    :: ['a tree, ['a, 'a forest, 'b]=>'b,          
                 'b, ['a tree, 'a forest, 'b, 'b]=>'b] => 'b
  forest_rec  :: ['a forest, ['a, 'a forest, 'b]=>'b,        
                  'b, ['a tree, 'a forest, 'b, 'b]=>'b] => 'b

defs
     (*the concrete constants*)
  TCONS_def 	"TCONS M N == In0(M $ N)"
  FNIL_def	"FNIL      == In1(NIL)"
  FCONS_def	"FCONS M N == In1(CONS M N)"
     (*the abstract constants*)
  Tcons_def 	"Tcons a ts == Abs_Tree(TCONS (Leaf a) (Rep_Forest ts))"
  Fnil_def  	"Fnil       == Abs_Forest(FNIL)"
  Fcons_def 	"Fcons t ts == Abs_Forest(FCONS (Rep_Tree t) (Rep_Forest ts))"

  TF_def	"TF(A) == lfp(%Z. A <*> Part Z In1 
                           <+> ({Numb(0)} <+> Part Z In0 <*> Part Z In1))"

rules
  (*faking a type definition for tree...*)
  Rep_Tree 	   "Rep_Tree(n): Part (TF(range Leaf)) In0"
  Rep_Tree_inverse "Abs_Tree(Rep_Tree(t)) = t"
  Abs_Tree_inverse "z: Part (TF(range Leaf)) In0 ==> Rep_Tree(Abs_Tree(z)) = z"
    (*faking a type definition for forest...*)
  Rep_Forest 	     "Rep_Forest(n): Part (TF(range Leaf)) In1"
  Rep_Forest_inverse "Abs_Forest(Rep_Forest(ts)) = ts"
  Abs_Forest_inverse 
	"z: Part (TF(range Leaf)) In1 ==> Rep_Forest(Abs_Forest(z)) = z"


defs
     (*recursion*)
  TF_rec_def	
   "TF_rec M b c d == wfrec (trancl pred_sexp) M   
               (Case (Split(%x y g. b x y (g y))) 
	              (List_case (%g.c) (%x y g. d x y (g x) (g y))))"

  tree_rec_def
   "tree_rec t b c d == 
   TF_rec (Rep_Tree t) (%x y r. b (Inv Leaf x) (Abs_Forest y) r) 
          c (%x y rt rf. d (Abs_Tree x) (Abs_Forest y) rt rf)"

  forest_rec_def
   "forest_rec tf b c d == 
   TF_rec (Rep_Forest tf) (%x y r. b (Inv Leaf x) (Abs_Forest y) r) 
          c (%x y rt rf. d (Abs_Tree x) (Abs_Forest y) rt rf)"
end