显示`newtype T a = T(a - > Int)`是一个不是Functor的Type Constructor

Question

据称这newtype T a = T (a -> Int)是一个不是仿函数的类型构造函数(但它是一个逆变函子).怎么会这样？或者什么是逆变函子(我认为这很明显为什么这不能成为一个普通的函子)？

Answer 1

假设T是一个仿函数.然后我们有

fmap :: (a -> b) -> T a -> T b

现在,让我们尝试实现它.

instance Functor T where
  fmap f (T g) = T $ \x -> _y

显然,我们有这样的事情入手,并结合价值f,g以及x以某种方式计算值y这是正确的类型.我们怎么做？好吧,请注意我已经打电话给它_y,告诉GHC我需要帮助找出放在那里的东西.GHC有什么要说的？

<interactive>:7:28: error:
    • Found hole: _y :: Int
      Or perhaps ‘_y’ is mis-spelled, or not in scope
    • In the expression: _y
      In the second argument of ‘($)’, namely ‘\ x -> _y’
      In the expression: T $ \ x -> _y
    • Relevant bindings include
        x :: b (bound at <interactive>:7:23)
        g :: a -> Int (bound at <interactive>:7:13)
        f :: a -> b (bound at <interactive>:7:8)
        fmap :: (a -> b) -> T a -> T b (bound at <interactive>:7:3)

那么现在我们清楚一切相关的类型吧？我们需要以Int某种方式返回,我们必须构建它是:

        x :: b
        g :: a -> Int
        f :: a -> b

嗯,好吧,我们唯一可以创造的东西Int是g,所以让我们填补它,留下g的论点是空白的,请GHC寻求更多的帮助:

instance Functor T where
  fmap f (T g) = T $ \x -> g _y

<interactive>:7:31: error:
    • Found hole: _y :: a
      Where: ‘a’ is a rigid type variable bound by
               the type signature for:
                 fmap :: forall a b. (a -> b) -> T a -> T b
               at <interactive>:7:3
      Or perhaps ‘_y’ is mis-spelled, or not in scope
    • In the first argument of ‘g’, namely ‘(_y)’
      In the expression: g (_y)
      In the second argument of ‘($)’, namely ‘\ x -> g (_y)’
    • Relevant bindings include
        x :: b (bound at <interactive>:7:23)
        g :: a -> Int (bound at <interactive>:7:13)
        f :: a -> b (bound at <interactive>:7:8)
        fmap :: (a -> b) -> T a -> T b (bound at <interactive>:7:3)

好吧,我们可以自己预测:要打电话g,我们需要a从某个地方获得类型的价值.但是我们a在范围中没有任何类型的值,并且我们没有任何返回类型值的函数a!我们陷入了困境:现在我们不可能产生一种我们想要的类型的价值,即使我们在每一步都做了唯一可能的事情:我们没有任何东西可以备份并尝试不同的方式.

为什么会这样？因为如果我给你一个类型的函数a -> Int并说"但顺便说一句,这里是一个函数a -> b,请给我一个函数来b -> Int代替",你实际上不能使用函数a -> b,因为没有人给你任何as打电话给它!如果我给你一个功能b -> a,那将是非常有帮助的,对吧？你可以b -> Int从那时开始生成一个函数,首先调用b -> a函数得到一个函数a,然后调用原a -> Int函数来得到想要的函数Int.

这就是逆变函数的意义所在:我们反转传递给函数的箭头fmap,因此它可以映射你需要的东西(函数参数)而不是你"拥有"的东西(具体值,函数的返回值等) ).

旁白:我早些时候声称我们在每一步都做了"唯一可能的事情",这有点像.我们不能建立一个Int出来的f,g和x,当然,我们可以弥补各种数字出来的空气.我们对类型一无所知b,所以我们不能Int以某种方式得到它的结果,但我们可以说"让我们总是返回零",这在技术上满足了类型检查器:

instance Functor T where
  fmap f (T g) = T $ const 0

显然,这看起来非常错误的,因为它看起来f和g应该是非常重要的,我们忽略了他们!但它打字检查,所以我们没事,对吧？

不,这违反了Functor法律之一:

fmap id = id

我们可以很容易地证明这一点:

fmap id (T $ const 5) = (T $ const 0) /= (T $ const 5)

而现在我们已经尝试了所有的东西:我们必须建立一个Int完全没有使用我们的b类型的唯一方法是从无中心化,并且所有这些用途都将是同构的使用const,这将违反Functor法则.

Answer 2

特定

newtype T a = T (a -> Int)

让我们尝试Contravariant为这个数据类型构建实例.

这是有问题的类型类:

class Contravariant f where
  contramap :: (a -> b) -> f b -> f a

基本上,contramap是类似于fmap,但而不是提升的功能a -> b到f a -> f b,它抬起它f b -> f a.

让我们开始编写实例......

instance Contravariant T where
  contramap g (T f) = ?

我们填写之前?,让我们想想是什么类型的g和f有:

g :: a -> b
f :: b -> Int

为清楚起见,我们不妨提一下

f a ~ T (a -> Int)
f b ~ T (b -> Int)

所以我们可以填写?如下:

instance Contravariant T where
  contramap g (T f) = T (f . g)

是超级迂腐,你可能会重命名g为aToB和f作为bToInt.

instance Contravariant T where
  contramap aToB (T bToInt) = T (bToInt . aToB)

你可以写一个Contravariant实例的原因T a归结a为在逆变位置的事实T (a -> Int).说服自己T a不是a 的最好方法Functor是尝试(并且失败)自己编写Functor实例.

Answer 3

这是另一个观点.正如liminalisht所示,T是Contravariant.我们可以告诉我们有关协变和逆变的类型吗？

import Data.Void


change1, change1', change2 :: (Functor f, Contravariant f) => f a -> f b
change1 = contramap (const ()) . fmap (const ())
change1' = (() >$) . (() <$)
change2 = fmap absurd . contramap absurd

前两个实现基本相同(change1'是优化change1); 他们每个人使用的事实()是Hask的"终端对象" .change2而是使用Void"初始对象" 这一事实.

这些函数替换所有a以s f a与b•不用任何知道任何事情a,b或者他们之间的关系,使一切一样.应该很清楚,这种方法f a并不真正依赖a.也就是说,f's参数必须是幻像.这是不是对的情况下T,所以它不能同时协变的.