(* 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