464 done |
464 done |
465 thus "finite {xs. convex_map\<cdot>d\<cdot>xs = xs}" |
465 thus "finite {xs. convex_map\<cdot>d\<cdot>xs = xs}" |
466 by (rule finite_range_imp_finite_fixes) |
466 by (rule finite_range_imp_finite_fixes) |
467 qed |
467 qed |
468 |
468 |
469 subsection {* Convex powerdomain is a domain *} |
469 subsection {* Convex powerdomain is bifinite *} |
470 |
470 |
471 lemma approx_chain_convex_map: |
471 lemma approx_chain_convex_map: |
472 assumes "approx_chain a" |
472 assumes "approx_chain a" |
473 shows "approx_chain (\<lambda>i. convex_map\<cdot>(a i))" |
473 shows "approx_chain (\<lambda>i. convex_map\<cdot>(a i))" |
474 using assms unfolding approx_chain_def |
474 using assms unfolding approx_chain_def |
478 proof |
478 proof |
479 show "\<exists>(a::nat \<Rightarrow> 'a convex_pd \<rightarrow> 'a convex_pd). approx_chain a" |
479 show "\<exists>(a::nat \<Rightarrow> 'a convex_pd \<rightarrow> 'a convex_pd). approx_chain a" |
480 using bifinite [where 'a='a] |
480 using bifinite [where 'a='a] |
481 by (fast intro!: approx_chain_convex_map) |
481 by (fast intro!: approx_chain_convex_map) |
482 qed |
482 qed |
483 |
|
484 definition |
|
485 convex_approx :: "nat \<Rightarrow> udom convex_pd \<rightarrow> udom convex_pd" |
|
486 where |
|
487 "convex_approx = (\<lambda>i. convex_map\<cdot>(udom_approx i))" |
|
488 |
|
489 lemma convex_approx: "approx_chain convex_approx" |
|
490 using convex_map_ID finite_deflation_convex_map |
|
491 unfolding convex_approx_def by (rule approx_chain_lemma1) |
|
492 |
|
493 definition convex_defl :: "udom defl \<rightarrow> udom defl" |
|
494 where "convex_defl = defl_fun1 convex_approx convex_map" |
|
495 |
|
496 lemma cast_convex_defl: |
|
497 "cast\<cdot>(convex_defl\<cdot>A) = |
|
498 udom_emb convex_approx oo convex_map\<cdot>(cast\<cdot>A) oo udom_prj convex_approx" |
|
499 using convex_approx finite_deflation_convex_map |
|
500 unfolding convex_defl_def by (rule cast_defl_fun1) |
|
501 |
|
502 instantiation convex_pd :: ("domain") liftdomain |
|
503 begin |
|
504 |
|
505 definition |
|
506 "emb = udom_emb convex_approx oo convex_map\<cdot>emb" |
|
507 |
|
508 definition |
|
509 "prj = convex_map\<cdot>prj oo udom_prj convex_approx" |
|
510 |
|
511 definition |
|
512 "defl (t::'a convex_pd itself) = convex_defl\<cdot>DEFL('a)" |
|
513 |
|
514 definition |
|
515 "(liftemb :: 'a convex_pd u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb" |
|
516 |
|
517 definition |
|
518 "(liftprj :: udom \<rightarrow> 'a convex_pd u) = u_map\<cdot>prj oo udom_prj u_approx" |
|
519 |
|
520 definition |
|
521 "liftdefl (t::'a convex_pd itself) = u_defl\<cdot>DEFL('a convex_pd)" |
|
522 |
|
523 instance |
|
524 using liftemb_convex_pd_def liftprj_convex_pd_def liftdefl_convex_pd_def |
|
525 proof (rule liftdomain_class_intro) |
|
526 show "ep_pair emb (prj :: udom \<rightarrow> 'a convex_pd)" |
|
527 unfolding emb_convex_pd_def prj_convex_pd_def |
|
528 using ep_pair_udom [OF convex_approx] |
|
529 by (intro ep_pair_comp ep_pair_convex_map ep_pair_emb_prj) |
|
530 next |
|
531 show "cast\<cdot>DEFL('a convex_pd) = emb oo (prj :: udom \<rightarrow> 'a convex_pd)" |
|
532 unfolding emb_convex_pd_def prj_convex_pd_def defl_convex_pd_def cast_convex_defl |
|
533 by (simp add: cast_DEFL oo_def cfun_eq_iff convex_map_map) |
|
534 qed |
|
535 |
|
536 end |
|
537 |
|
538 text {* DEFL of type constructor = type combinator *} |
|
539 |
|
540 lemma DEFL_convex: "DEFL('a::domain convex_pd) = convex_defl\<cdot>DEFL('a)" |
|
541 by (rule defl_convex_pd_def) |
|
542 |
|
543 |
483 |
544 subsection {* Join *} |
484 subsection {* Join *} |
545 |
485 |
546 definition |
486 definition |
547 convex_join :: "'a convex_pd convex_pd \<rightarrow> 'a convex_pd" where |
487 convex_join :: "'a convex_pd convex_pd \<rightarrow> 'a convex_pd" where |