Aici este o posibilă abordare, care este o încercare de la o interpretare literală a acestui alineat:
Atunci când dovedește o declarație E:N→U despre toate numerele naturale, este suficient să se demonstreze că pentru 0 și pentru succ(n)presupunând că aceasta este valabil și pentru n, de exemplu, vom construi ez:E(0) și es:∏(n:N)E(n)→E(succ(n)).
de la HoTT book (secțiunea 5.1).
Aici este planul ce a fost implementat în codul de mai jos:
Formula ce înseamnă să ai o dovada pentru o declarație că "o proprietate P este valabil pentru toate numerele naturale". Mai jos, vom folosi
trait Forall[N, P[n <: N]]:
inline def apply[n <: N]: P[n]
în cazul în care semnătura apply-metoda în esență, spune "pentru toate n <: Nputem genera dovezi de P[n]".
Rețineți că metoda este declarat a fi inline. Acesta este un mod de a se asigura că dovada ∀n.P(n) este constructivă și executabil la runtime (cu toate Acestea, consultați editarea istorie pentru propuneri alternative cu manual generate martor termeni).
Postulat un fel de inductie pentru numere naturale. Mai jos, vom folosi următoarele formulare:
If
P(0) holds, and
whenever P(i) holds, then also P(i + 1) holds,
then
For all `n`, P(n) holds
Cred că ar trebui să fie posibil să se derive astfel inducție principiile folosind un metaprogram facilități.
Scrie dovezi pentru cazul de bază și inducerea caz de inductie.
???
Profit
Codul arata astfel:
sealed trait Nat
class O extends Nat
class S[N <: Nat] extends Nat
type plus[a <: Nat, b <: Nat] <: Nat = a match
case O => b
case S[n] => S[n plus b]
trait Forall[N, P[n <: N]]:
inline def apply[n <: N]: P[n]
trait NatInductionPrinciple[P[n <: Nat]] extends Forall[Nat, P]:
def base: P[O]
def step: [i <: Nat] => (P[i] => P[S[i]])
inline def apply[n <: Nat]: P[n] =
(inline compiletime.erasedValue[n] match
case _: O => base
case _: S[pred] => step(apply[pred])
).asInstanceOf[P[n]]
given liftCoUpperbounded[U, A <: U, B <: U, S[_ <: U]](using ev: A =:= B):
(S[A] =:= S[B]) = ev.liftCo[[X] =>> Any].asInstanceOf[S[A] =:= S[B]]
type NatPlusZeroEqualsNat[n <: Nat] = (n plus O) =:= n
def trivialLemma[i <: Nat]: ((S[i] plus O) =:= S[i plus O]) =
summon[(S[i] plus O) =:= S[i plus O]]
object Proof extends NatInductionPrinciple[NatPlusZeroEqualsNat]:
val base = summon[(O plus O) =:= O]
val step: ([i <: Nat] => NatPlusZeroEqualsNat[i] => NatPlusZeroEqualsNat[S[i]]) =
[i <: Nat] => (p: NatPlusZeroEqualsNat[i]) =>
given previousStep: ((i plus O) =:= i) = p
given liftPreviousStep: (S[i plus O] =:= S[i]) =
liftCoUpperbounded[Nat, i plus O, i, S]
given definitionalEquality: ((S[i] plus O) =:= S[i plus O]) =
trivialLemma[i]
definitionalEquality.andThen(liftPreviousStep)
def demoNat(): Unit = {
println("Running demoNat...")
type two = S[S[O]]
val ev = Proof[two]
val twoInstance: two = new S[S[O]]
println(ev(twoInstance) == twoInstance)
}
Se compilează, se execută, și printuri:
true
în sensul că ne-am invocat cu succes recursiv definit
metoda pe executabil dovezi termen de tip two plus O =:= two.
Unele comentarii suplimentare
- La
trivialLemma a fost necesar, astfel încât summons în interiorul altor givens nu accidental genera recursiv bucle, care este un pic enervant.
- Separat
liftCo-metoda de S[_ <: U] a fost nevoie, pentru că =:=.liftCo nu permite tipul de constructori cu sus-delimitate tip de parametri.
compiletime.erasedValue + inline match este minunat! Acesta generează în mod automat un fel de runtime-gizmos care permit acest model de potrivire într-o "șterse" de tip. Înainte de a am aflat, am fost încercarea de a construi corespunzătoare martor termeni manual, dar acest lucru nu pare a fi necesar, la toate, este oferit gratuit (a se vedea edita istorie pentru abordarea cu manual construite martor termeni).
