Typy zawierające klauzule/przeprogramować w agdzie, lub, jak użyć przepisać zamiast subst?

Question

Pierwsze kilka nudnych import:

import Relation.Binary.PropositionalEquality as PE 
import Relation.Binary.HeterogeneousEquality as HE 
import Algebra 
import Data.Nat 
import Data.Nat.Properties 
open PE 
open HE using (_≅_) 
open CommutativeSemiring commutativeSemiring using (+-commutativeMonoid) 
open CommutativeMonoid +-commutativeMonoid using() renaming (comm to +-comm) 

Teraz załóżmy, że mam typ indeksowane przez, powiedzmy, Naturals.

postulate Foo : ℕ -> Set 

I że chcę udowodnić pewne równości o funkcjach operujących na tego typu Foo. Ponieważ agda nie jest bardzo inteligentna, będą to heterogeniczne równości. Prostym przykładem może być

foo : (m n : ℕ) -> Foo (m + n) -> Foo (n + m) 
foo m n x rewrite +-comm n m = x 

bar : (m n : ℕ) (x : Foo (m + n)) -> foo m n x ≅ x 
bar m n x = {! ?0 !} 

Celem w barze jest

Goal: (foo m n x | n + m | .Data.Nat.Properties.+-comm n m) ≅ x 
———————————————————————————————————————————————————————————— 
x : Foo (m + n) 
n : ℕ 
m : ℕ 

Jakie są te | s robi w celu? I jak mogę nawet zacząć konstruować termin tego typu?

W tym przypadku mogę obejść problem ręcznie, zastępując go przez subst, ale to staje się naprawdę brzydkie i żmudne dla większych typów i równań.

foo' : (m n : ℕ) -> Foo (m + n) -> Foo (n + m) 
foo' m n x = PE.subst Foo (+-comm m n) x 

bar' : (m n : ℕ) (x : Foo (m + n)) -> foo' m n x ≅ x 
bar' m n x = HE.≡-subst-removable Foo (+-comm m n) x 

Answer 1

Rury te wskazują, że redukcja jest zawieszone w oczekiwaniu na wynik wyrażenia w pytaniu, a to zazwyczaj sprowadza się do tego, że trzeba było with blok, którego wynik trzeba wiedzieć, aby kontynuować. Dzieje się tak dlatego, że konstrukt rewrite rozwija się tylko do with danego wyrażenia wraz z dowolnymi wartościami pomocniczymi, które mogą być potrzebne do jego działania, po czym następuje dopasowanie na refl.

W tym przypadku oznacza to tylko tyle, że trzeba wprowadzić +-comm n m w with bloku i wzorca meczu na refl (i prawdopodobnie będziesz musiał przynieść n + m w zakresie też, jak to sugeruje, więc równość ma coś porozmawiać o). Model oceny Agdy jest dość prosty, a jeśli dopasujesz wzór do czegoś (z wyjątkiem dopasowania faux pattern na rekordach), nie zmniejszy się, dopóki nie dopasujesz wzoru do tego samego. Możesz nawet być w stanie uciec przepisywaniu tego samego wyrażenia w swoim dowodzie, ponieważ robi to, co ci przedstawiłem.

Dokładniej, jeśli określają:

f : ... 
f with a | b | c 
... | someDataConstructor | boundButNonConstructorVariable | someRecordConstructor = ... 

a następnie odwołać się do f jako wyraz, otrzymasz rur ty obserwowane pod kątem ekspresji a tylko, dlatego, że pasuje na someDataConstructor, więc na bardzo najmniej, aby uzyskać f, aby zmniejszyć, trzeba wprowadzić a, a następnie dopasować na someDataConstructor z niego. Z drugiej strony, b i c, mimo że zostały one wprowadzone w tym samym bloku, nie oceniają zatrzymania, ponieważ b nie pasuje do wzoru, a 's someRecordConstructor jest statycznie uważany za jedyny możliwy konstruktor, ponieważ jest to rekord wpisz z eta.