Является ли применение многогранного типа инъективным?

Является ли применение многогранного типа инъективным?

Когда мы включаемPolyKindsмы знаем что f a ~ g b подразумевает f ~ g а также a ~ b?

мотивация

Пытаясь ответить на другой вопрос, я уменьшил проблему до такой степени, что я получил следующую ошибку только с PolyKinds включен.

Could not deduce (c1 ~ c)
from the context ((a, c z) ~ (c1 a1, c1 b))

Если бы приложение типа polykinded было инъективным, мы могли бы вывести c1 ~ c следующее.

(a,   c z) ~ (c1 a1,   c1 b)
(a,) (c z) ~ (c1 a1,) (c1 b) {- switch to prefix notation -}
      c z  ~           c1 b  {- f a ~ g b implies a ~ b -}
      c    ~           c1    {- f a ~ g b implies f ~ g -}
      c1   ~           c     {- ~ is reflexive -}

Тип приложения является инъективным

В Haskell тип application является инъективным. Если f a ~ g b затем f ~ g а также a ~ b, Мы можем доказать это себе, составив следующее

{-# LANGUAGE GADTs #-}

import Control.Applicative

second :: a -> a -> a
second _ = id

typeApplicationIsInjective :: (Applicative f, f a ~ g b) => f a -> g b -> f b
typeApplicationIsInjective fa gb = second <$> fa <*> gb

Вид приложения типа не является инъективным

Тип приложения типа не является инъективным. Если мы рассмотрим следующее, которое имеет вид (* -> *) -> *,

newtype HoldingInt f = HoldingInt (f Int)

Мы можем спросить GHCI, что-то вроде (* -> *) -> * имеет отношение к чему-то * -> *, который *

> :k HoldingInt
HoldingInt :: (* -> *) -> *
> :k Maybe
Maybe :: * -> *
> :k HoldingInt Maybe
HoldingInt Maybe :: *

Это то же самое, что-то вроде * -> * применяется к чему-то вроде *

> :k Maybe
Maybe :: * -> *
> :k Int
Int :: *
> :k Maybe Int
Maybe Int :: *

Следовательно, неверно, что заимствование синтаксиса изKindSignaturesПервый набор добрых подписей подразумевает что-либо во втором.

f :: kf, g :: kg, a :: ka, b :: kb, f a :: k, g b :: k
g :: kf, f :: kg, b :: ka, a :: kb
Источник

2 ответа

Решение

Приложение типа Polykinded является инъективным извне, но, конечно, не инъективным изнутри Haskell.

Под "инъективным извне" я подразумеваю, что когда бы Refl с типом f a :~: g b, то это должно быть так, что f равно g а также a равно bи поскольку мы знаем, что типы разных видов никогда не бывают одинаковыми, они должны быть одинаковыми.

Проблема в том, что GHC имеет только однородные ограничения на равенство типов и вообще не имеет ограничений на равенство типов. Механизм кодирования GADT с использованием принуждений существует только на уровне типа и повышенного уровня. Вот почему мы не можем выразить гетерогенное равенство и почему мы не можем продвигать ГАДЦ.

{-# LANGUAGE PolyKinds, GADTs, TypeOperators #-}

data HEq (a :: i) (b :: k) :: * where
  HRefl :: HEq a a
-- ERROR: Data constructor ‘HRefl’ cannot be GADT-like in its *kind* arguments

Кроме того, вот простой пример GHC, не предполагающий инъективность:

sym1 :: forall f g a b. f a :~: g b -> g b :~: f a
sym1 Refl = Refl
-- ERROR: could not deduce (g ~ f), could not deduce (b ~ a)

Если мы аннотируем a а также b с таким же видом, это проверяет.

В этой статье говорится о вышеупомянутых ограничениях и о том, как их можно устранить в GHC (они описывают систему с унифицированными приведениями типа / типа и гетерогенными ограничениями равенства).

Источник

Если приложение уровня типа имеет разные виды, то эти два типа не могут быть показаны равными. Вот доказательства:

GHC.Prim> () :: ((Any :: * -> *) Any) ~ ((Any :: (* -> *) -> *) Any) => ()
<interactive>:6:1:
    Couldn't match kind ‘*’ with ‘* -> *’
    Expected type: Any Any
      Actual type: Any Any
    In the expression:
        () :: ((Any :: * -> *) Any) ~ ((Any :: (* -> *) -> *) Any) => ()
    In an equation for ‘it’:
        it
          = () :: ((Any :: * -> *) Any) ~ ((Any :: (* -> *) -> *) Any) => ()

<interactive>:6:7:
    Couldn't match kind ‘*’ with ‘* -> *’
    Expected type: Any Any
      Actual type: Any Any
    In the ambiguity check for: Any Any ~ Any Any => ()
    To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
    In an expression type signature:
      ((Any :: * -> *) Any) ~ ((Any :: (* -> *) -> *) Any) => ()
    In the expression:
        () :: ((Any :: * -> *) Any) ~ ((Any :: (* -> *) -> *) Any) => ()

(Даже включив предложенный AllowAmbiguousTypes расширение дает ту же ошибку проверки типов - просто без предложения.)

Следовательно, если два типа могут быть показаны равными, то приложения уровня типов в одной и той же структурной позиции по обе стороны равенства имеют одинаковый вид.

Если вы хотите получить доказательство, а не доказательство, вам нужно будет записать осторожное индуктивное доказательство о системе, описанной в разделе " Проверка типов с открытыми функциями типов". Изучение рисунка 3 показывает мне, что инвариант "все типы приложений в ~ имеют одинаковый вид по обе стороны от ~" сохраняется, хотя ни я, ни статья не доказывают это тщательно, поэтому есть некоторый шанс, что не так.

Источник
Другие вопросы по тегам