¿Cómo leer esta "prueba" de GHC Core?


Escribí este pequeño fragmento de Haskell para averiguar cómo GHC demuestra que para los números naturales, solo se pueden reducir a la mitad los pares: {[17]]}

{-# 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)

Las partes relevantes del núcleo se convierten en:

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 }

Conozco el flujo general de fundición de los tipos a través de instancias de la familia de tipos Flip, pero hay algunas cosas que no puedo seguir completamente:

  • ¿Cuál es el significado de @~ <Nat.Flip x_apH>_N ? ¿es la instancia Flip para x? ¿En qué difiere eso de @ (Nat.Flip x_apH)? Estoy interesado en < > y _N

Respecto al primer lanzamiento en halve:

  • ¿Qué hacer dt_dK6, dt1_dK7 y dt2_dK8 representan? Entiendo que son algún tipo de prueba de equivalencia, pero ¿cuál es cuál?
  • Entiendo que Sym se ejecuta a través de una equivalencia hacia atrás
  • ¿Qué hacen los ;? ¿Se aplican las pruebas de equivalencia de forma secuencial?
  • ¿Qué son estos _N y _R sufijos?
  • Son TFCo:R:Flip[0] y TFCo:R:Flip[1] las instancias de Flip?
Author: Bhavin Solanki, 2014-10-23

1 answers

@~ es la aplicación de coerción.

Los corchetes angulares denotan una coerción reflexiva de su tipo contenido con papel dado por la letra subrayada.

Así, <Nat.Flip x_ap0H>_N es una prueba de igualdad de que Nat.Flip x_apH es igual a Nat.Flip x_apH nominalmente (como tipos iguales no solo representaciones iguales).

PS tiene muchos argumentos. Nos fijamos en el constructor inteligente $WPS y podemos ver que los dos primeros son los tipos de x e y respectivamente. Tenemos pruebas de que el argumento constructor es Flip x (en este caso, tenemos Flip x ~ Even. Entonces tenemos las pruebas x ~ Flip y y y ~ Flip x. El argumento final es un valor de ParNat x.

Ahora caminaré a través del primer molde de tipo Nat.ParNat x_aIX ~# Nat.ParNat 'Nat.Odd

Empezamos con (Nat.ParNat ...)_R. Esta es una aplicación constructor de tipo. Eleva la prueba de x_aIX ~# 'Nat.Odd a Nat.ParNat x_aIX ~# Nat.ParNat 'Nat.Odd. El R significa que hace esto representacionalmente significando que los tipos son isomorfos pero no los mismos (en este caso son los mismos pero no necesitamos ese conocimiento para realizar el cast).

Ahora nos fijamos en el cuerpo principal de la prueba (dt1_dK7 ; (Nat.Flip (dt2_dK8 ; Sym dt_dK6))_N; Nat.TFCo:R:Flip[0]). ; significa transitividad, es decir, aplicar estas pruebas en orden.

dt1_dK7 es una prueba de x_aIX ~# Nat.Flip y_aIY.

Si miramos (dt2_dK8 ; Sym dt_dK6). dt2_dK8 muestra y_aIY ~# Nat.Flip x_aIX. dt_dK6 es del tipo 'Nat.Even ~# Nat.Flip x_aIX. Por lo que Sym dt_dK6 es de tipo Nat.Flip x_aIX ~# 'Nat.Even y (dt2_dK8 ; Sym dt_dK6) es de tipo y_aIY ~# 'Nat.Even

Así que (Nat.Flip (dt2_dK8 ; Sym dt_dK6))_N es una prueba de que Nat.Flip y_aIY ~# Nat.Flip 'Nat.Even.

Nat.TFCo:R:Flip[0] es la primera regla de flip que es Nat.Flip 'Nat.Even ~# 'Nat.Odd'.

Poniendo estos juntos obtenemos (dt1_dK7 ; (Nat.Flip (dt2_dK8 ; Sym dt_dK6))_N; Nat.TFCo:R:Flip[0]) tiene tipo x_aIX #~ 'Nat.Odd.

El segundo reparto más complicado es un poco más difícil de resolver, pero debería funcionar en el mismo principio.

 6
Author: Alex,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-08-16 14:22:41