7 imports AList |
7 imports AList |
8 begin |
8 begin |
9 |
9 |
10 text {* This was based on some existing fragments in the AFP-Collection framework. *} |
10 text {* This was based on some existing fragments in the AFP-Collection framework. *} |
11 |
11 |
|
12 subsection {* Preliminaries *} |
|
13 |
|
14 lemma distinct_map_fst_filter: |
|
15 "distinct (map fst xs) ==> distinct (map fst (List.filter P xs))" |
|
16 by (induct xs) auto |
|
17 |
12 subsection {* Type @{text "('key, 'value) alist" } *} |
18 subsection {* Type @{text "('key, 'value) alist" } *} |
13 |
19 |
14 typedef (open) ('key, 'value) alist = "{xs :: ('key \<times> 'value) list. distinct (map fst xs)}" |
20 typedef (open) ('key, 'value) alist = "{xs :: ('key \<times> 'value) list. (distinct o map fst) xs}" |
15 morphisms impl_of Alist |
21 morphisms impl_of Alist |
16 proof |
22 proof |
17 show "[] \<in> {xs. distinct (map fst xs)}" by simp |
23 show "[] \<in> {xs. (distinct o map fst) xs}" by simp |
18 qed |
24 qed |
|
25 |
|
26 setup_lifting type_definition_alist |
19 |
27 |
20 lemma alist_ext: "impl_of xs = impl_of ys \<Longrightarrow> xs = ys" |
28 lemma alist_ext: "impl_of xs = impl_of ys \<Longrightarrow> xs = ys" |
21 by(simp add: impl_of_inject) |
29 by(simp add: impl_of_inject) |
22 |
30 |
23 lemma alist_eq_iff: "xs = ys \<longleftrightarrow> impl_of xs = impl_of ys" |
31 lemma alist_eq_iff: "xs = ys \<longleftrightarrow> impl_of xs = impl_of ys" |
29 lemma Alist_impl_of [code abstype]: "Alist (impl_of xs) = xs" |
37 lemma Alist_impl_of [code abstype]: "Alist (impl_of xs) = xs" |
30 by(rule impl_of_inverse) |
38 by(rule impl_of_inverse) |
31 |
39 |
32 subsection {* Primitive operations *} |
40 subsection {* Primitive operations *} |
33 |
41 |
34 definition lookup :: "('key, 'value) alist \<Rightarrow> 'key \<Rightarrow> 'value option" |
42 (* FIXME: improve quotient_definition so that type annotations on the right hand sides can be removed *) |
35 where [code]: "lookup xs = map_of (impl_of xs)" |
|
36 |
43 |
37 definition empty :: "('key, 'value) alist" |
44 quotient_definition lookup :: "('key, 'value) alist \<Rightarrow> 'key \<Rightarrow> 'value option" |
38 where [code del]: "empty = Alist []" |
45 where "lookup" is "map_of :: ('key * 'value) list \<Rightarrow> 'key \<Rightarrow> 'value option" .. |
39 |
46 |
40 definition update :: "'key \<Rightarrow> 'value \<Rightarrow> ('key, 'value) alist \<Rightarrow> ('key, 'value) alist" |
47 quotient_definition empty :: "('key, 'value) alist" |
41 where [code del]: "update k v xs = Alist (AList.update k v (impl_of xs))" |
48 where "empty" is "[] :: ('key * 'value) list" by simp |
|
49 |
|
50 quotient_definition update :: "'key \<Rightarrow> 'value \<Rightarrow> ('key, 'value) alist \<Rightarrow> ('key, 'value) alist" |
|
51 where "update" is "AList.update :: 'key \<Rightarrow> 'value \<Rightarrow> ('key * 'value) list \<Rightarrow> ('key * 'value) list" |
|
52 by (simp add: distinct_update) |
42 |
53 |
43 (* FIXME: we use an unoptimised delete operation. *) |
54 (* FIXME: we use an unoptimised delete operation. *) |
44 definition delete :: "'key \<Rightarrow> ('key, 'value) alist \<Rightarrow> ('key, 'value) alist" |
55 quotient_definition delete :: "'key \<Rightarrow> ('key, 'value) alist \<Rightarrow> ('key, 'value) alist" |
45 where [code del]: "delete k xs = Alist (AList.delete k (impl_of xs))" |
56 where "delete" is "AList.delete :: 'key \<Rightarrow> ('key * 'value) list \<Rightarrow> ('key * 'value) list" |
|
57 by (simp add: distinct_delete) |
46 |
58 |
47 definition map_entry :: "'key \<Rightarrow> ('value \<Rightarrow> 'value) \<Rightarrow> ('key, 'value) alist \<Rightarrow> ('key, 'value) alist" |
59 quotient_definition map_entry :: "'key \<Rightarrow> ('value \<Rightarrow> 'value) \<Rightarrow> ('key, 'value) alist \<Rightarrow> ('key, 'value) alist" |
48 where [code del]: "map_entry k f xs = Alist (AList.map_entry k f (impl_of xs))" |
60 where "map_entry" is "AList.map_entry :: 'key \<Rightarrow> ('value \<Rightarrow> 'value) \<Rightarrow> ('key * 'value) list \<Rightarrow> ('key * 'value) list" |
|
61 by (simp add: distinct_map_entry) |
49 |
62 |
50 definition filter :: "('key \<times> 'value \<Rightarrow> bool) \<Rightarrow> ('key, 'value) alist \<Rightarrow> ('key, 'value) alist" |
63 quotient_definition filter :: "('key \<times> 'value \<Rightarrow> bool) \<Rightarrow> ('key, 'value) alist \<Rightarrow> ('key, 'value) alist" |
51 where [code del]: "filter P xs = Alist (List.filter P (impl_of xs))" |
64 where "filter" is "List.filter :: ('key \<times> 'value \<Rightarrow> bool) \<Rightarrow> ('key * 'value) list \<Rightarrow> ('key * 'value) list" |
|
65 by (simp add: distinct_map_fst_filter) |
52 |
66 |
53 definition map_default :: "'key => 'value => ('value => 'value) => ('key, 'value) alist => ('key, 'value) alist" |
67 quotient_definition map_default :: "'key => 'value => ('value => 'value) => ('key, 'value) alist => ('key, 'value) alist" |
54 where |
68 where "map_default" is "AList.map_default :: 'key => 'value => ('value => 'value) => ('key * 'value) list => ('key * 'value) list" |
55 "map_default k v f xs = Alist (AList.map_default k v f (impl_of xs))" |
69 by (simp add: distinct_map_default) |
56 |
70 |
57 lemma impl_of_empty [code abstract]: "impl_of empty = []" |
71 (* FIXME: theorems are still used in Multiset; make code certificates available to the user *) |
|
72 lemma impl_of_empty: "impl_of empty = []" |
58 by (simp add: empty_def Alist_inverse) |
73 by (simp add: empty_def Alist_inverse) |
59 |
74 |
60 lemma impl_of_update [code abstract]: "impl_of (update k v xs) = AList.update k v (impl_of xs)" |
75 lemma impl_of_update: "impl_of (update k v xs) = AList.update k v (impl_of xs)" |
61 by (simp add: update_def Alist_inverse distinct_update) |
76 by (simp add: update_def Alist_inverse distinct_update) |
62 |
77 |
63 lemma impl_of_delete [code abstract]: |
78 lemma impl_of_filter: |
64 "impl_of (delete k al) = AList.delete k (impl_of al)" |
|
65 unfolding delete_def by (simp add: Alist_inverse distinct_delete) |
|
66 |
|
67 lemma impl_of_map_entry [code abstract]: |
|
68 "impl_of (map_entry k f xs) = AList.map_entry k f (impl_of xs)" |
|
69 unfolding map_entry_def by (simp add: Alist_inverse distinct_map_entry) |
|
70 |
|
71 lemma distinct_map_fst_filter: |
|
72 "distinct (map fst xs) ==> distinct (map fst (List.filter P xs))" |
|
73 by (induct xs) auto |
|
74 |
|
75 lemma impl_of_filter [code abstract]: |
|
76 "impl_of (filter P xs) = List.filter P (impl_of xs)" |
79 "impl_of (filter P xs) = List.filter P (impl_of xs)" |
77 unfolding filter_def by (simp add: Alist_inverse distinct_map_fst_filter) |
80 unfolding filter_def by (simp add: Alist_inverse distinct_map_fst_filter) |
78 |
|
79 lemma impl_of_map_default [code abstract]: |
|
80 "impl_of (map_default k v f xs) = AList.map_default k v f (impl_of xs)" |
|
81 by (auto simp add: map_default_def Alist_inverse distinct_map_default) |
|
82 |
81 |
83 subsection {* Abstract operation properties *} |
82 subsection {* Abstract operation properties *} |
84 |
83 |
85 (* FIXME: to be completed *) |
84 (* FIXME: to be completed *) |
86 |
85 |