多金属型应用是否是内射的？

Question

多金属型应用是否是内射的？

当我们能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))

如果多金属型应用是单射的,我们可以推导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中,类型应用是单射的.如果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

Answer 1

Polykinded类型应用从外部是单射的,但在Haskell内部肯定不是单射的.

通过"来自外部的内射",我的意思是,只要有一个Refl类型f a :~: g b,那么它必须f是等于g和a等于的情况b,并且因为我们知道不同种类的类型永远不相等,所以种类也必须是相同.

问题是GHC只有同类型等式约束,并且根本没有类型的等式约束.使用强制编码GADT的机制仅存在于类型和提升类型级别.这就是为什么我们不能表达异质平等,以及为什么我们不能推广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中消除这些限制(它们描述了具有统一类型/类型强制和异构等式约束的系统).

Answer 2

如果类型级应用程序具有不同的类型,则这两种类型不能显示为相等.这是证据:

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的检查向我表明,不变的"所有类型的应用程序在〜的两侧都有相同的类型"被保留,尽管我和论文都没有仔细证明这一点,所以它有可能是不是这样.