| 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. |