Wie lese ich diesen GHC Core "Beweis"?

Question 1

Ich habe dieses kleine Stück Haskell geschrieben, um herauszufinden, wie GHC beweist, dass man für natürliche Zahlen nur die geraden halbieren kann:

{-# LANGUAGE DataKinds, GADTs, KindSignatures, TypeFamilies #-}
module Nat where

data Nat = Z | S Nat

data Parity = Even | Odd

type family Flip (x :: Parity) :: Parity where
  Flip Even = Odd
  Flip Odd  = Even

data ParNat :: Parity -> * where
  PZ :: ParNat Even
  PS :: (x ~ Flip y, y ~ Flip x) => ParNat x -> ParNat (Flip x)

halve :: ParNat Even -> Nat
halve PZ     = Z
halve (PS a) = helper a
  where helper :: ParNat Odd -> Nat
        helper (PS b) = S (halve b)

Die relevanten Teile des Kerns werden:

Nat.$WPZ :: Nat.ParNat 'Nat.Even
Nat.$WPZ = Nat.PZ @ 'Nat.Even @~ <'Nat.Even>_N

Nat.$WPS
  :: forall (x_apH :: Nat.Parity) (y_apI :: Nat.Parity).
     (x_apH ~ Nat.Flip y_apI, y_apI ~ Nat.Flip x_apH) =>
     Nat.ParNat x_apH -> Nat.ParNat (Nat.Flip x_apH)
Nat.$WPS =
  \ (@ (x_apH :: Nat.Parity))
    (@ (y_apI :: Nat.Parity))
    (dt_aqR :: x_apH ~ Nat.Flip y_apI)
    (dt_aqS :: y_apI ~ Nat.Flip x_apH)
    (dt_aqT :: Nat.ParNat x_apH) ->
    case dt_aqR of _ { GHC.Types.Eq# dt_aqU ->
    case dt_aqS of _ { GHC.Types.Eq# dt_aqV ->
    Nat.PS
      @ (Nat.Flip x_apH)
      @ x_apH
      @ y_apI
      @~ <Nat.Flip x_apH>_N
      @~ dt_aqU
      @~ dt_aqV
      dt_aqT
    }
    }

Rec {
Nat.halve :: Nat.ParNat 'Nat.Even -> Nat.Nat
Nat.halve =
  \ (ds_dJB :: Nat.ParNat 'Nat.Even) ->
    case ds_dJB of _ {
      Nat.PZ dt_dKD -> Nat.Z;
      Nat.PS @ x_aIX @ y_aIY dt_dK6 dt1_dK7 dt2_dK8 a_apK ->
        case a_apK
             `cast` ((Nat.ParNat
                        (dt1_dK7
                         ; (Nat.Flip (dt2_dK8 ; Sym dt_dK6))_N
                         ; Nat.TFCo:R:Flip[0]))_R
                     :: Nat.ParNat x_aIX ~# Nat.ParNat 'Nat.Odd)
        of _
        { Nat.PS @ x1_aJ4 @ y1_aJ5 dt3_dKa dt4_dKb dt5_dKc b_apM ->
        Nat.S
          (Nat.halve
             (b_apM
              `cast` ((Nat.ParNat
                         (dt4_dKb
                          ; (Nat.Flip
                               (dt5_dKc
                                ; Sym dt3_dKa
                                ; Sym Nat.TFCo:R:Flip[0]
                                ; (Nat.Flip (dt_dK6 ; Sym dt2_dK8))_N
                                ; Sym dt1_dK7))_N
                          ; Sym dt_dK6))_R
                      :: Nat.ParNat x1_aJ4 ~# Nat.ParNat 'Nat.Even)))
        }
    }
end Rec }

Ich kenne den allgemeinen Ablauf des Castings der Typen durch Instanzen der Flip-Typfamilie, aber es gibt einige Dinge, denen ich nicht vollständig folgen kann:

Was bedeutet das @~ <Nat.Flip x_apH>_N? ist es die Flip-Instanz für x? Wie unterscheidet sich das von @ (Nat.Flip x_apH)? Ich interessiere mich sowohl für < >als auch_N

In Bezug auf die erste Besetzung in halve:

Was dt_dK6, dt1_dK7und dt2_dK8steht für? Ich verstehe, dass es sich um eine Art Äquivalenzbeweis handelt, aber welches ist welches?
Ich verstehe, dass dies Symdurch eine Äquivalenz rückwärts verläuft
Was machen die ;? Werden die Äquivalenznachweise nur nacheinander angewendet?
Was sind das _Nund _RSuffixe?
Sind TFCo:R:Flip[0]und TFCo:R:Flip[1]die Instanzen von Flip?

Question 2

@~ ist Zwangsanwendung.

Die spitzen Klammern bezeichnen einen reflexiven Zwang ihres enthaltenen Typs mit der durch den unterstrichenen Buchstaben gegebenen Rolle.

Dies <Nat.Flip x_ap0H>_Nist also ein Gleichheitsnachweis, Nat.Flip x_apHder Nat.Flip x_apHnominell gleich ist (als gleiche Typen nicht nur gleiche Darstellungen).

PS hat viele Argumente. Wir schauen uns den intelligenten Konstruktor an $WPSund sehen, dass die ersten beiden die Typen von x bzw. y sind. Wir haben Beweise dafür, dass das Konstruktorargument ist Flip x(in diesem Fall haben wir Flip x ~ Even. Wir haben dann die Beweise x ~ Flip yund y ~ Flip x. Das letzte Argument ist ein Wert von ParNat x.

Ich werde jetzt durch die erste Besetzung des Typs gehen Nat.ParNat x_aIX ~# Nat.ParNat 'Nat.Odd

Wir beginnen mit (Nat.ParNat ...)_R. Dies ist eine Typkonstruktoranwendung. Es hebt den Beweis von x_aIX ~# 'Nat.Oddzu Nat.ParNat x_aIX ~# Nat.ParNat 'Nat.Odd. Das Rbedeutet, dass dies repräsentativ bedeutet, dass die Typen isomorph, aber nicht gleich sind (in diesem Fall sind sie gleich, aber wir benötigen dieses Wissen nicht, um die Besetzung durchzuführen).

Nun betrachten wir den Hauptteil des Beweises (dt1_dK7 ; (Nat.Flip (dt2_dK8 ; Sym dt_dK6))_N; Nat.TFCo:R:Flip[0]). ;bedeutet Transitivität, dh diese Beweise in der richtigen Reihenfolge anwenden.

dt1_dK7ist ein Beweis für x_aIX ~# Nat.Flip y_aIY.

Wenn wir schauen (dt2_dK8 ; Sym dt_dK6). dt2_dK8zeigt y_aIY ~# Nat.Flip x_aIX. dt_dK6ist vom Typ 'Nat.Even ~# Nat.Flip x_aIX. Also Sym dt_dK6ist vom Typ Nat.Flip x_aIX ~# 'Nat.Evenund (dt2_dK8 ; Sym dt_dK6)ist vom Typy_aIY ~# 'Nat.Even

Somit (Nat.Flip (dt2_dK8 ; Sym dt_dK6))_Nist ein Beweis dafür Nat.Flip y_aIY ~# Nat.Flip 'Nat.Even.

Nat.TFCo:R:Flip[0]ist die erste Flip-Regel, die ist Nat.Flip 'Nat.Even ~# 'Nat.Odd'.

Wenn wir diese zusammenstellen, haben wir (dt1_dK7 ; (Nat.Flip (dt2_dK8 ; Sym dt_dK6))_N; Nat.TFCo:R:Flip[0])Typ x_aIX #~ 'Nat.Odd.

Die zweite kompliziertere Besetzung ist etwas schwieriger zu erarbeiten, sollte aber nach dem gleichen Prinzip funktionieren.

Answer 1