Как читать это доказательство GHC Core?

Я написал этот небольшой фрагмент кода на Haskell, чтобы выяснить, как GHC доказывает, что для натуральных чисел можно разделить только четные числа пополам:

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

Соответствующие части ядра становятся:

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 }

Я знаю общий процесс приведения типов через экземпляры семейства типов Flip, но есть некоторые вещи, которым я не могу полностью следовать:

  • Что означает @~ <Nat.Flip x_apH>_N ? это экземпляр Flip для x? Чем это отличается от @ (Nat.Flip x_apH)? Меня оба интересуют < > и _N

Относительно первого состава в halve:

  • Что означают dt_dK6, dt1_dK7 и dt2_dK8? Я понимаю, что это какие-то доказательства эквивалентности, но что есть что?
  • Я понимаю, что Sym проходит через эквивалентность в обратном порядке
  • Что делают ;? Доказательства эквивалентности просто применяются последовательно?
  • Что это за суффиксы _N и _R?
  • Являются ли TFCo:R:Flip[0] и TFCo:R:Flip[1] экземплярами Flip?

person Mathijs Kwik    schedule 23.10.2014    source источник
comment
Понятия не имею, но предполагаю, что _N и _R являются номинальными и репрезентативными ролями: haskell.org/ghc/docs/latest/html/users_guide/   -  person chi    schedule 23.10.2014
comment
Посетите stackoverflow.com/questions/6121146/reading-ghc-core, надеюсь, вы поняли..   -  person Hemant Ramphul    schedule 07.07.2015


Ответы (1)


@~ является приложением принуждения.

Угловые скобки обозначают рефлексивное принуждение содержащегося в них типа, роль которого указана подчеркнутой буквой.

Таким образом, <Nat.Flip x_ap0H>_N является доказательством равенства того, что Nat.Flip x_apH номинально равно Nat.Flip x_apH (как равные типы, а не просто равные представления).

PS есть много аргументов. Мы смотрим на интеллектуальный конструктор $WPS и видим, что первые два являются типами x и y соответственно. У нас есть доказательство того, что аргумент конструктора равен Flip x (в данном случае у нас есть Flip x ~ Even. Затем у нас есть доказательства x ~ Flip y и y ~ Flip x. Последний аргумент — это значение ParNat x.

Сейчас я пройдусь по первому слепку типа Nat.ParNat x_aIX ~# Nat.ParNat 'Nat.Odd.

Начнем с (Nat.ParNat ...)_R. Это приложение-конструктор типов. Он поднимает доказательство x_aIX ~# 'Nat.Odd до Nat.ParNat x_aIX ~# Nat.ParNat 'Nat.Odd. R означает, что это делается репрезентативно, что означает, что типы изоморфны, но не одинаковы (в этом случае они одинаковы, но нам не нужны эти знания для выполнения приведения).

Теперь смотрим на основную часть доказательства (dt1_dK7 ; (Nat.Flip (dt2_dK8 ; Sym dt_dK6))_N; Nat.TFCo:R:Flip[0]). ; означает транзитивность, т.е. применять эти доказательства по порядку.

dt1_dK7 является доказательством x_aIX ~# Nat.Flip y_aIY.

Если мы посмотрим на (dt2_dK8 ; Sym dt_dK6). dt2_dK8 показывает y_aIY ~# Nat.Flip x_aIX. dt_dK6 относится к типу 'Nat.Even ~# Nat.Flip x_aIX. Таким образом, Sym dt_dK6 относится к типу Nat.Flip x_aIX ~# 'Nat.Even, а (dt2_dK8 ; Sym dt_dK6) относится к типу y_aIY ~# 'Nat.Even.

Таким образом, (Nat.Flip (dt2_dK8 ; Sym dt_dK6))_N является доказательством того, что Nat.Flip y_aIY ~# Nat.Flip 'Nat.Even.

Nat.TFCo:R:Flip[0] — это первое правило флипа, которое равно Nat.Flip 'Nat.Even ~# 'Nat.Odd'.

Сложив их вместе, мы получаем (dt1_dK7 ; (Nat.Flip (dt2_dK8 ; Sym dt_dK6))_N; Nat.TFCo:R:Flip[0]) имеет тип x_aIX #~ 'Nat.Odd.

Второй, более сложный состав, немного сложнее, но он должен работать по тому же принципу.

person Alex    schedule 16.08.2015
comment
На самом деле я просто наградил этот пост, чтобы посмотреть, сможет ли кто-нибудь разобраться в этом беспорядке ^^ молодец, сэр. - person Jiri Trecak; 17.08.2015