[222] | 1 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
[234] | 2 | (* Vector.ma: Fixed length polymorphic vectors, and routine operations on *) |
---|
| 3 | (* them. *) |
---|
[222] | 4 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 5 | |
---|
[229] | 6 | include "Util.ma". |
---|
[224] | 7 | |
---|
[241] | 8 | include "Nat.ma". |
---|
| 9 | include "List.ma". |
---|
| 10 | include "Cartesian.ma". |
---|
[248] | 11 | include "Maybe.ma". |
---|
[260] | 12 | include "Plogic/equality.ma". |
---|
[222] | 13 | |
---|
[231] | 14 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 15 | (* The datatype. *) |
---|
| 16 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 17 | |
---|
[228] | 18 | ninductive Vector (A: Type[0]): Nat → Type[0] ≝ |
---|
| 19 | Empty: Vector A Z |
---|
| 20 | | Cons: ∀n: Nat. A → Vector A n → Vector A (S n). |
---|
[222] | 21 | |
---|
[240] | 22 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 23 | (* Syntax. *) |
---|
| 24 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 25 | |
---|
[262] | 26 | notation "[[ list0 x sep ; ]]" |
---|
| 27 | non associative with precedence 90 |
---|
| 28 | for ${fold right @'vnil rec acc @{'vcons $x $acc}}. |
---|
| 29 | |
---|
| 30 | interpretation "Vector vnil" 'vnil = (Empty ?). |
---|
| 31 | interpretation "Vector vcons" 'vcons hd tl = (Cons ? ? hd tl). |
---|
[256] | 32 | interpretation "Vector cons" 'cons hd tl = (Cons ? ? hd tl). |
---|
[228] | 33 | |
---|
[231] | 34 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 35 | (* Lookup. *) |
---|
| 36 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
[240] | 37 | |
---|
[261] | 38 | naxiom succ_less_than_injective: |
---|
| 39 | ∀m, n: Nat. |
---|
[265] | 40 | less_than_p (S m) (S n) → m < n. |
---|
[261] | 41 | |
---|
| 42 | naxiom nothing_less_than_Z: |
---|
| 43 | ∀m: Nat. |
---|
| 44 | ¬(m < Z). |
---|
| 45 | |
---|
[240] | 46 | nlet rec get_index (A: Type[0]) (n: Nat) |
---|
[261] | 47 | (v: Vector A n) (m: Nat) (lt: m < n) on m: A ≝ |
---|
| 48 | (match m with |
---|
| 49 | [ Z ⇒ |
---|
| 50 | match v return λx.λ_. Z < x → A with |
---|
| 51 | [ Empty ⇒ λabsd1: Z < Z. ? |
---|
| 52 | | Cons p hd tl ⇒ λprf1: Z < S p. hd |
---|
| 53 | ] |
---|
| 54 | | S o ⇒ |
---|
| 55 | (match v return λx.λ_. S o < x → A with |
---|
| 56 | [ Empty ⇒ λprf: S o < Z. ? |
---|
| 57 | | Cons p hd tl ⇒ λprf: S o < S p. get_index A p tl o ? |
---|
| 58 | ]) |
---|
| 59 | ]) lt. |
---|
| 60 | ##[ ncases (nothing_less_than_Z Z); #K; ncases (K absd1) |
---|
| 61 | ##| ncases (nothing_less_than_Z (S o)); #K; ncases (K prf) |
---|
| 62 | ##| napply succ_less_than_injective; nassumption |
---|
| 63 | ##] |
---|
| 64 | nqed. |
---|
| 65 | |
---|
| 66 | nlet rec get_index_weak (A: Type[0]) (n: Nat) |
---|
[240] | 67 | (v: Vector A n) (m: Nat) on m ≝ |
---|
| 68 | match m with |
---|
| 69 | [ Z ⇒ |
---|
| 70 | match v with |
---|
| 71 | [ Empty ⇒ Nothing A |
---|
| 72 | | Cons p hd tl ⇒ Just A hd |
---|
| 73 | ] |
---|
| 74 | | S o ⇒ |
---|
| 75 | match v with |
---|
| 76 | [ Empty ⇒ Nothing A |
---|
[261] | 77 | | Cons p hd tl ⇒ get_index_weak A p tl o |
---|
[240] | 78 | ] |
---|
| 79 | ]. |
---|
[222] | 80 | |
---|
[240] | 81 | interpretation "Vector get_index" 'get_index v n = (get_index ? ? v n). |
---|
[262] | 82 | |
---|
[261] | 83 | nlet rec set_index (A: Type[0]) (n: Nat) (v: Vector A n) (m: Nat) (a: A) (lt: m < n) on m: Vector A n ≝ |
---|
| 84 | (match m with |
---|
[259] | 85 | [ Z ⇒ |
---|
[261] | 86 | match v return λx.λ_. Z < x → Vector A x with |
---|
| 87 | [ Empty ⇒ λabsd1: Z < Z. Empty A |
---|
| 88 | | Cons p hd tl ⇒ λprf1: Z < S p. (a :: tl) |
---|
[259] | 89 | ] |
---|
| 90 | | S o ⇒ |
---|
[261] | 91 | (match v return λx.λ_. S o < x → Vector A x with |
---|
| 92 | [ Empty ⇒ λprf: S o < Z. Empty A |
---|
| 93 | | Cons p hd tl ⇒ λprf: S o < S p. hd :: (set_index A p tl o a ?) |
---|
| 94 | ]) |
---|
| 95 | ]) lt. |
---|
| 96 | napply succ_less_than_injective. |
---|
| 97 | nassumption. |
---|
| 98 | nqed. |
---|
[259] | 99 | |
---|
| 100 | nlet rec set_index_weak (A: Type[0]) (n: Nat) |
---|
| 101 | (v: Vector A n) (m: Nat) (a: A) on m ≝ |
---|
[240] | 102 | match m with |
---|
| 103 | [ Z ⇒ |
---|
| 104 | match v with |
---|
| 105 | [ Empty ⇒ Nothing (Vector A n) |
---|
| 106 | | Cons o hd tl ⇒ Just (Vector A n) (? (Cons A o a tl)) |
---|
| 107 | ] |
---|
| 108 | | S o ⇒ |
---|
| 109 | match v with |
---|
| 110 | [ Empty ⇒ Nothing (Vector A n) |
---|
| 111 | | Cons p hd tl ⇒ |
---|
[259] | 112 | let settail ≝ set_index_weak A p tl o a in |
---|
[240] | 113 | match settail with |
---|
| 114 | [ Nothing ⇒ Nothing (Vector A n) |
---|
| 115 | | Just j ⇒ Just (Vector A n) (? (Cons A p hd j)) |
---|
| 116 | ] |
---|
| 117 | ] |
---|
| 118 | ]. |
---|
| 119 | //. |
---|
| 120 | nqed. |
---|
| 121 | |
---|
| 122 | nlet rec drop (A: Type[0]) (n: Nat) |
---|
| 123 | (v: Vector A n) (m: Nat) on m ≝ |
---|
| 124 | match m with |
---|
| 125 | [ Z ⇒ Just (Vector A n) v |
---|
| 126 | | S o ⇒ |
---|
| 127 | match v with |
---|
| 128 | [ Empty ⇒ Nothing (Vector A n) |
---|
| 129 | | Cons p hd tl ⇒ ? (drop A p tl o) |
---|
| 130 | ] |
---|
| 131 | ]. |
---|
| 132 | //. |
---|
| 133 | nqed. |
---|
[268] | 134 | |
---|
[311] | 135 | nlet rec split (A: Type[0]) (m,n: Nat) on m |
---|
[268] | 136 | : Vector A (m+n) → (Vector A m) × (Vector A n) |
---|
| 137 | ≝ |
---|
| 138 | match m return λm. Vector A (m+n) → (Vector A m) × (Vector A n) with |
---|
| 139 | [ Z ⇒ λv.〈[[ ]], v〉 |
---|
| 140 | | S m' ⇒ λv. |
---|
| 141 | match v return λl.λ_:Vector A l.l = S (m' + n) → (Vector A (S m')) × (Vector A n) with |
---|
| 142 | [ Empty ⇒ λK.⊥ |
---|
| 143 | | Cons o he tl ⇒ λK. |
---|
[311] | 144 | match split A m' n (tl⌈Vector A (m'+n)↦Vector A o⌉) with |
---|
[268] | 145 | [ mk_Cartesian v1 v2 ⇒ 〈he::v1, v2〉 ]] (?: (S (m' + n)) = S (m' + n))]. |
---|
| 146 | //; ndestruct; //. |
---|
| 147 | nqed. |
---|
[316] | 148 | |
---|
[322] | 149 | ndefinition head: ∀A:Type[0]. ∀n. Vector A (S n) → A × (Vector A n) |
---|
| 150 | ≝ λA,n,v. |
---|
| 151 | match v return λl.λ_:Vector A l.l = S n → A × (Vector A n) with |
---|
| 152 | [ Empty ⇒ λK.⊥ |
---|
| 153 | | Cons o he tl ⇒ λK. 〈he,(tl⌈Vector A n ↦ Vector A o⌉)〉 |
---|
| 154 | ] (? : S ? = S ?). |
---|
| 155 | //; ndestruct; //. |
---|
| 156 | nqed. |
---|
| 157 | |
---|
| 158 | ndefinition from_singl: ∀A:Type[0]. Vector A (S Z) → A ≝ |
---|
| 159 | λA,v. first … (head … v). |
---|
[240] | 160 | |
---|
[231] | 161 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 162 | (* Folds and builds. *) |
---|
[246] | 163 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
[231] | 164 | |
---|
[228] | 165 | nlet rec fold_right (A: Type[0]) (B: Type[0]) (n: Nat) |
---|
[222] | 166 | (f: A → B → B) (x: B) (v: Vector A n) on v ≝ |
---|
| 167 | match v with |
---|
| 168 | [ Empty ⇒ x |
---|
| 169 | | Cons n hd tl ⇒ f hd (fold_right A B n f x tl) |
---|
| 170 | ]. |
---|
[322] | 171 | |
---|
[320] | 172 | nlet rec fold_right_i (A: Type[0]) (B: Type[0]) (C: Type[0]) |
---|
[328] | 173 | (n: Nat) (f: A → B → C → C) (c: C) |
---|
| 174 | (v: Vector A n) (q: Vector B n) on v ≝ |
---|
| 175 | (match v return λx.λ_. x = n → C with |
---|
[320] | 176 | [ Empty ⇒ |
---|
| 177 | match q return λx.λ_. Z = x → C with |
---|
[328] | 178 | [ Empty ⇒ λprf: Z = Z. c |
---|
[320] | 179 | | Cons o hd tl ⇒ λabsd. ? |
---|
| 180 | ] |
---|
| 181 | | Cons o hd tl ⇒ |
---|
| 182 | match q return λx.λ_. S o = x → C with |
---|
[328] | 183 | [ Empty ⇒ λabsd: S o = Z. ? |
---|
[320] | 184 | | Cons p hd' tl' ⇒ λprf: S o = S p. |
---|
[328] | 185 | fold_right_i A B C o f (f hd hd' c) tl ? |
---|
[320] | 186 | ] |
---|
[328] | 187 | ]) (refl ? n). |
---|
| 188 | ##[##1,2: |
---|
| 189 | ndestruct; |
---|
| 190 | ##| ndestruct (prf); |
---|
| 191 | napply tl'; |
---|
| 192 | ##] |
---|
| 193 | nqed. |
---|
[322] | 194 | |
---|
[228] | 195 | nlet rec fold_left (A: Type[0]) (B: Type[0]) (n: Nat) |
---|
[222] | 196 | (f: A → B → A) (x: A) (v: Vector B n) on v ≝ |
---|
| 197 | match v with |
---|
| 198 | [ Empty ⇒ x |
---|
| 199 | | Cons n hd tl ⇒ f (fold_left A B n f x tl) hd |
---|
| 200 | ]. |
---|
| 201 | |
---|
[231] | 202 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 203 | (* Maps and zips. *) |
---|
| 204 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 205 | |
---|
| 206 | nlet rec map (A: Type[0]) (B: Type[0]) (n: Nat) |
---|
| 207 | (f: A → B) (v: Vector A n) on v ≝ |
---|
[222] | 208 | match v with |
---|
[231] | 209 | [ Empty ⇒ Empty B |
---|
| 210 | | Cons n hd tl ⇒ (f hd) :: (map A B n f tl) |
---|
[222] | 211 | ]. |
---|
| 212 | |
---|
[240] | 213 | nlet rec zip_with (A: Type[0]) (B: Type[0]) (C: Type[0]) (n: Nat) |
---|
[228] | 214 | (f: A → B → C) (v: Vector A n) (q: Vector B n) on v ≝ |
---|
| 215 | (match v return (λx.λr. x = n → Vector C x) with |
---|
| 216 | [ Empty ⇒ λ_. Empty C |
---|
| 217 | | Cons n hd tl ⇒ |
---|
| 218 | match q return (λy.λr. S n = y → Vector C (S n)) with |
---|
| 219 | [ Empty ⇒ ? |
---|
[229] | 220 | | Cons m hd' tl' ⇒ |
---|
[228] | 221 | λe: S n = S m. |
---|
[240] | 222 | (f hd hd') :: (zip_with A B C n f tl ?) |
---|
[228] | 223 | ] |
---|
| 224 | ]) |
---|
| 225 | (refl ? n). |
---|
| 226 | ## |
---|
| 227 | [ #e; |
---|
[229] | 228 | ndestruct(e); |
---|
[228] | 229 | ## |
---|
[229] | 230 | | ndestruct(e); |
---|
| 231 | napply tl' |
---|
[228] | 232 | ## |
---|
| 233 | ] |
---|
[230] | 234 | nqed. |
---|
| 235 | |
---|
[240] | 236 | ndefinition zip ≝ |
---|
| 237 | λA, B: Type[0]. |
---|
| 238 | λn: Nat. |
---|
| 239 | λv: Vector A n. |
---|
| 240 | λq: Vector B n. |
---|
| 241 | zip_with A B (Cartesian A B) n (mk_Cartesian A B) v q. |
---|
| 242 | |
---|
[231] | 243 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 244 | (* Building vectors from scratch *) |
---|
| 245 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 246 | |
---|
| 247 | nlet rec replicate (A: Type[0]) (n: Nat) (h: A) on n ≝ |
---|
| 248 | match n return λn. Vector A n with |
---|
| 249 | [ Z ⇒ Empty A |
---|
| 250 | | S m ⇒ h :: (replicate A m h) |
---|
| 251 | ]. |
---|
| 252 | |
---|
[230] | 253 | nlet rec append (A: Type[0]) (n: Nat) (m: Nat) |
---|
| 254 | (v: Vector A n) (q: Vector A m) on v ≝ |
---|
| 255 | match v return (λn.λv. Vector A (n + m)) with |
---|
| 256 | [ Empty ⇒ q |
---|
| 257 | | Cons o hd tl ⇒ hd :: (append A o m tl q) |
---|
| 258 | ]. |
---|
[231] | 259 | |
---|
[272] | 260 | notation "hvbox(l break @@ r)" |
---|
| 261 | right associative with precedence 47 |
---|
| 262 | for @{ 'vappend $l $r }. |
---|
[231] | 263 | |
---|
[272] | 264 | interpretation "Vector append" 'vappend v1 v2 = (append ??? v1 v2). |
---|
| 265 | |
---|
[231] | 266 | nlet rec scan_left (A: Type[0]) (B: Type[0]) (n: Nat) |
---|
| 267 | (f: A → B → A) (a: A) (v: Vector B n) on v ≝ |
---|
| 268 | a :: |
---|
| 269 | (match v with |
---|
| 270 | [ Empty ⇒ Empty A |
---|
| 271 | | Cons o hd tl ⇒ scan_left A B o f (f a hd) tl |
---|
| 272 | ]). |
---|
[230] | 273 | |
---|
[231] | 274 | nlet rec scan_right (A: Type[0]) (B: Type[0]) (n: Nat) |
---|
| 275 | (f: A → B → A) (b: B) (v: Vector A n) on v ≝ |
---|
| 276 | match v with |
---|
| 277 | [ Empty ⇒ ? |
---|
| 278 | | Cons o hd tl ⇒ f hd b :: (scan_right A B o f b tl) |
---|
| 279 | ]. |
---|
| 280 | //. |
---|
| 281 | nqed. |
---|
| 282 | |
---|
| 283 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 284 | (* Other manipulations. *) |
---|
| 285 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 286 | |
---|
| 287 | nlet rec length (A: Type[0]) (n: Nat) (v: Vector A n) on v ≝ |
---|
| 288 | match v with |
---|
| 289 | [ Empty ⇒ Z |
---|
| 290 | | Cons n hd tl ⇒ S $ length A n tl |
---|
| 291 | ]. |
---|
| 292 | |
---|
[230] | 293 | nlet rec reverse (A: Type[0]) (n: Nat) |
---|
| 294 | (v: Vector A n) on v ≝ |
---|
| 295 | match v return (λm.λv. Vector A m) with |
---|
| 296 | [ Empty ⇒ Empty A |
---|
| 297 | | Cons o hd tl ⇒ ? (append A o ? (reverse A o tl) (Cons A Z hd (Empty A))) |
---|
| 298 | ]. |
---|
[248] | 299 | nrewrite < (succ_plus ? ?). |
---|
| 300 | nrewrite > (plus_zero ?). |
---|
[230] | 301 | //. |
---|
| 302 | nqed. |
---|
| 303 | |
---|
[231] | 304 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 305 | (* Conversions to and from lists. *) |
---|
| 306 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 307 | |
---|
[236] | 308 | nlet rec list_of_vector (A: Type[0]) (n: Nat) |
---|
| 309 | (v: Vector A n) on v ≝ |
---|
| 310 | match v return λn.λv. List A with |
---|
[260] | 311 | [ Empty ⇒ ? (cic:/matita/ng/List/List.con(0,1,1) A) |
---|
[240] | 312 | | Cons o hd tl ⇒ hd :: (list_of_vector A o tl) |
---|
[230] | 313 | ]. |
---|
[240] | 314 | //. |
---|
| 315 | nqed. |
---|
[231] | 316 | |
---|
[236] | 317 | nlet rec vector_of_list (A: Type[0]) (l: List A) on l ≝ |
---|
[231] | 318 | match l return λl. Vector A (length A l) with |
---|
[260] | 319 | [ Empty ⇒ ? (cic:/matita/ng/Vector/Vector.con(0,1,1) A) |
---|
[237] | 320 | | Cons hd tl ⇒ ? (hd :: (vector_of_list A tl)) |
---|
[231] | 321 | ]. |
---|
[237] | 322 | nnormalize. |
---|
[231] | 323 | //. |
---|
[237] | 324 | //. |
---|
[231] | 325 | nqed. |
---|
| 326 | |
---|
| 327 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 328 | (* Rotates and shifts. *) |
---|
| 329 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
[230] | 330 | |
---|
[231] | 331 | nlet rec rotate_left (A: Type[0]) (n: Nat) |
---|
| 332 | (m: Nat) (v: Vector A n) on m: Vector A n ≝ |
---|
[230] | 333 | match m with |
---|
| 334 | [ Z ⇒ v |
---|
| 335 | | S o ⇒ |
---|
| 336 | match v with |
---|
| 337 | [ Empty ⇒ Empty A |
---|
| 338 | | Cons p hd tl ⇒ |
---|
[231] | 339 | rotate_left A (S p) o (? (append A p ? tl (Cons A ? hd (Empty A)))) |
---|
[230] | 340 | ] |
---|
| 341 | ]. |
---|
[248] | 342 | nrewrite < (succ_plus ? ?). |
---|
| 343 | nrewrite > (plus_zero ?). |
---|
[230] | 344 | //. |
---|
| 345 | nqed. |
---|
[231] | 346 | |
---|
| 347 | ndefinition rotate_right ≝ |
---|
| 348 | λA: Type[0]. |
---|
| 349 | λn, m: Nat. |
---|
| 350 | λv: Vector A n. |
---|
| 351 | reverse A n (rotate_left A n m (reverse A n v)). |
---|
[230] | 352 | |
---|
[240] | 353 | ndefinition shift_left_1 ≝ |
---|
| 354 | λA: Type[0]. |
---|
| 355 | λn: Nat. |
---|
| 356 | λv: Vector A n. |
---|
| 357 | λa: A. |
---|
| 358 | match v with |
---|
| 359 | [ Empty ⇒ ? |
---|
| 360 | | Cons o hd tl ⇒ reverse A n (? (Cons A o a (reverse A o tl))) |
---|
| 361 | ]. |
---|
| 362 | //. |
---|
| 363 | nqed. |
---|
| 364 | |
---|
| 365 | ndefinition shift_right_1 ≝ |
---|
| 366 | λA: Type[0]. |
---|
| 367 | λn: Nat. |
---|
| 368 | λv: Vector A n. |
---|
| 369 | λa: A. |
---|
| 370 | reverse A n (shift_left_1 A n (reverse A n v) a). |
---|
| 371 | |
---|
| 372 | ndefinition shift_left ≝ |
---|
| 373 | λA: Type[0]. |
---|
| 374 | λn, m: Nat. |
---|
| 375 | λv: Vector A n. |
---|
| 376 | λa: A. |
---|
| 377 | iterate (Vector A n) (λx. shift_left_1 A n x a) v m. |
---|
| 378 | |
---|
| 379 | ndefinition shift_right ≝ |
---|
| 380 | λA: Type[0]. |
---|
| 381 | λn, m: Nat. |
---|
| 382 | λv: Vector A n. |
---|
| 383 | λa: A. |
---|
| 384 | iterate (Vector A n) (λx. shift_right_1 A n x a) v m. |
---|
[315] | 385 | |
---|
| 386 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 387 | (* Decidable equality. *) |
---|
| 388 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 389 | |
---|
| 390 | nlet rec eq_v (A: Type[0]) (n: Nat) (f: A → A → Bool) (b: Vector A n) (c: Vector A n) on b ≝ |
---|
| 391 | (match b return λx.λ_. n = x → Bool with |
---|
| 392 | [ Empty ⇒ |
---|
| 393 | match c return λx.λ_. x = Z → Bool with |
---|
| 394 | [ Empty ⇒ λ_. true |
---|
| 395 | | Cons p hd tl ⇒ λabsd.? |
---|
| 396 | ] |
---|
| 397 | | Cons o hd tl ⇒ |
---|
| 398 | match c return λx.λ_. x = S o → Bool with |
---|
| 399 | [ Empty ⇒ λabsd. ? |
---|
| 400 | | Cons p hd' tl' ⇒ |
---|
| 401 | λprf. |
---|
| 402 | if (f hd hd') then |
---|
| 403 | (eq_v A o f tl ?) |
---|
| 404 | else |
---|
| 405 | false |
---|
| 406 | ] |
---|
| 407 | ]) (refl ? n). |
---|
| 408 | ##[##1, 3: |
---|
| 409 | ndestruct (absd); |
---|
| 410 | ndestruct (prf); |
---|
| 411 | napply tl'; |
---|
| 412 | ##|##2: |
---|
| 413 | ndestruct (absd); |
---|
| 414 | ##] |
---|
| 415 | nqed. |
---|
[240] | 416 | |
---|
[231] | 417 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 418 | (* Lemmas. *) |
---|
| 419 | (* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= *) |
---|
| 420 | |
---|
[230] | 421 | nlemma map_fusion: |
---|
| 422 | ∀A, B, C: Type[0]. |
---|
| 423 | ∀n: Nat. |
---|
| 424 | ∀v: Vector A n. |
---|
| 425 | ∀f: A → B. |
---|
| 426 | ∀g: B → C. |
---|
| 427 | map B C n g (map A B n f v) = map A C n (λx. g (f x)) v. |
---|
| 428 | #A B C n v f g. |
---|
| 429 | nelim v. |
---|
| 430 | nnormalize. |
---|
| 431 | @. |
---|
| 432 | #N H V H2. |
---|
| 433 | nnormalize. |
---|
| 434 | nrewrite > H2. |
---|
| 435 | @. |
---|
| 436 | nqed. |
---|
| 437 | |
---|
| 438 | nlemma length_correct: |
---|
| 439 | ∀A: Type[0]. |
---|
| 440 | ∀n: Nat. |
---|
| 441 | ∀v: Vector A n. |
---|
| 442 | length A n v = n. |
---|
| 443 | #A n v. |
---|
| 444 | nelim v. |
---|
| 445 | nnormalize. |
---|
| 446 | @. |
---|
| 447 | #N H V H2. |
---|
| 448 | nnormalize. |
---|
| 449 | nrewrite > H2. |
---|
| 450 | @. |
---|
| 451 | nqed. |
---|
| 452 | |
---|
| 453 | nlemma map_length: |
---|
| 454 | ∀A, B: Type[0]. |
---|
| 455 | ∀n: Nat. |
---|
| 456 | ∀v: Vector A n. |
---|
| 457 | ∀f: A → B. |
---|
| 458 | length A n v = length B n (map A B n f v). |
---|
| 459 | #A B n v f. |
---|
| 460 | nelim v. |
---|
| 461 | nnormalize. |
---|
| 462 | @. |
---|
| 463 | #N H V H2. |
---|
| 464 | nnormalize. |
---|
| 465 | nrewrite > H2. |
---|
| 466 | @. |
---|
[328] | 467 | nqed. |
---|