Debian Codegraph @

reals/fast/LazyNat.v

raw
1 (*
2 Copyright © 2006-2008 Russell O’Connor
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of
5 this proof and associated documentation files (the "Proof"), to deal in
6 the Proof without restriction, including without limitation the rights to
7 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
8 the Proof, and to permit persons to whom the Proof is furnished to do so,
9 subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in all
12 copies or substantial portions of the Proof.
13
14 THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
16 FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
17 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
18 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF.
20 *)
21
22 Require Export Coq.PArith.BinPos.
23
24 (* Backwards compatibility for Hint Rewrite locality attributes *)
25 Set Warnings "-unsupported-attributes".
26
27 (**
28 * Lazy Nat
29 This s a lazified version of the natural number that allow one to delay
30 computation until demanded. This is useful for large natural numbers
31 (often upper bounds) where only a small number of terms are actually needed
32 for compuation.
33 *)
34 Inductive LazyNat : Set :=
35 | LazyO : LazyNat
36 | LazyS : (unit -> LazyNat) -> LazyNat.
37
38 (**
39 ** Successor
40 *)
41 Definition lazyS (n:LazyNat) : LazyNat := LazyS (fun _ => n).
42
43 (** Convert a nat to a lazy nat *)
44 Fixpoint LazifyNat (n : nat) {struct n} : LazyNat :=
45 match n with
46 | O => LazyO
47 | S p => LazyS (fun _ => (LazifyNat p))
48 end.
49
50 (**
51 ** Predecessor
52 *)
53 Definition LazyPred (n:LazyNat) : LazyNat :=
54 match n with
55 | LazyO => LazyO
56 | LazyS n' => (n' tt)
57 end.
58
59 Lemma LazifyPred : forall n, LazifyNat (pred n) = LazyPred (LazifyNat n).
60 Proof.
61 induction n; reflexivity.
62 Qed.
63
64 (**
65 ** Addition
66 *)
67 Fixpoint LazyPlus (n m : LazyNat) {struct n} : LazyNat :=
68 match n with
69 | LazyO => m
70 | LazyS p => LazyS (fun _ => LazyPlus (p tt) m)
71 end.
72
73 Lemma LazifyPlus : forall n m, (LazifyNat (n + m) = LazyPlus (LazifyNat n) (LazifyNat m))%nat.
74 Proof.
75 induction n.
76 reflexivity.
77 simpl.
78 intros m.
79 rewrite IHn.
80 reflexivity.
81 Qed.
82
83 (**
84 ** Multiplication
85 *)
86 Fixpoint Pmult_LazyNat (x:positive) (pow2:LazyNat) {struct x} : LazyNat :=
87 match x with
88 | xI x' => (LazyPlus pow2 (Pmult_LazyNat x' (LazyPlus pow2 pow2)))%nat
89 | xO x' => Pmult_LazyNat x' (LazyPlus pow2 pow2)%nat
90 | xH => pow2
91 end.
92
93 Lemma LazifyPmult_LazyNat : forall x pow2, LazifyNat (Pmult_nat x pow2) = Pmult_LazyNat x (LazifyNat pow2).
94 Proof.
95 induction x; simpl; intros pow2; repeat (rewrite LazifyPlus||rewrite IHx); reflexivity.
96 Qed.
97
98 (** Convert a positive to a lazy nat. This is the most common way of
99 generating lazy nats. The simplest fixpoint to do this is not lazy,
100 because the weak head normal form for x=2^k is fully computed. To
101 get LazyS constructors sooner, we could also define a double function
102 on LazyNat. *)
103 Definition LazyNat_of_P (x:positive) := Pmult_LazyNat x (LazyS (fun _ => LazyO)).
104
105 Lemma LazifyNat_of_P : forall x, LazifyNat (nat_of_P x) = LazyNat_of_P x.
106 Proof.
107 intros x.
108 refine (LazifyPmult_LazyNat _ _).
109 Qed.
110 (* begin hide *)
111 #[global]
112 Hint Rewrite <- LazifyNat_of_P LazifyPmult_LazyNat LazifyPlus LazifyPred : UnLazyNat.
113 (* end hide *)
114
115 Fixpoint Pplus_LazyNat (p:positive)(n:LazyNat) {struct n} : positive :=
116 match n with
117 | LazyO => p
118 | (LazyS n') => (Pplus_LazyNat (Pos.succ p) (n' tt))
119 end.