为什么`((,)r)`一个非适用的Functor？

Question

来自不适用的仿函数:

一个类型构造函数,它是一个Functor但不是Applicative.一个简单的例子是一对:

instance Functor ((,) r) where
    fmap f (x,y) = (x, f y)

但是如何在Applicative不对其施加额外限制的情况下定义其实例是没有办法的r.特别是,没有办法如何定义pure :: a -> (r, a)任意的r.

问题1:为什么会这样？以下是如何pure使用f类型的函数a -> b:

(pure f) (pure x, pure y) = (pure x, pure f y)

从那里,定义pure :: a -> (r, a)可能取决于什么r.例如,如果r是Integer,则可以定义

pure x = (0 :: Integer, x)

在您的实例声明中.那么问题是什么？

问题2:我们可以说一般来说,如果F是仿函数,那么<*>总是可以定义,但pure可能并不总是被定义？

Answer 1

假设我们有

pure :: forall r a. a -> (r, a)

那么,特别是我们有

magic :: forall r. r
magic = fst (pure ())

现在,我们可以专门化类型变量r来获取

magic :: Void

哪里Void是没有构造函数的数据类型,这意味着

magic = undefined

但作为类型变量(和它们专门类型)没有发挥运行时间的作用,这意味着magic是始终不确定.

我们发现,((,) r)可以Applicative只对居住 r.而且还有更多.对于任何这样的实例,我们都可以写

munge :: r -> r -> r
munge r0 r1 = fst ( pure (\ _ _ -> ()) <*> (r0, ()) <*> (r1, ()) )

在上面定义一个二元运算符r.该Applicative法有效地告诉我们,munge必须是结合运算符吸收magic两边.

这是说有是一个明智的实例

instance Monoid r => Applicative ((,) r) where
  pure a              = (mempty, a)
  (r0, f) <*> (r1, s) = (mappend r0 r1, f s)

(正是你从中获得pure=return; (<*>)=ap的东西Monad (Writer r)).

当然,一些学者会认为定义是合法的(如果没有帮助)

instance Monoid r where
  mempty = undefined
  mappend _ _ = undefined
  -- Monoid laws clearly hold

但我认为任何明智的类型类实例都应该对语言的已定义片段做出非常重要的贡献.

Answer 2

答案1:

(pure f) (pure x, pure y) = (pure x, pure f y)

我不明白你的意思.它看起来像废话:pure f是一对,你不能应用一对,就好像它是一个函数.

从那里,定义pure :: a -> (r, a)可能取决于什么r.

这正是问题所在.r是完全一般的; 实例声明说((,) r)是所有类型r的Functor .这意味着你必须以某种方式实现一个pure :: a -> (r, a)适用于r调用者可能选择的任何类型的单个.这是不可能的,因为没有办法r从空气中想出一个任意的.

或者如你的引言所说:

特别是,没有办法如何定义pure :: a -> (r, a)任意的r.

如果你尝试做类似的事情

pure x = (0 :: Integer, x)

你收到一个错误:

Couldn't match expected type ‘r’ with actual type ‘Integer’
  ‘r’ is a rigid type variable bound by
      the instance declaration
      at ...

答案2:

会是什么<*>样子的对？这将是一个功能

(<*>) :: (r, a -> b) -> (r, a) -> (r, b)
(r1, f) (r2, x) = (???, f x)

但是你对这???部分做了什么？你必须在r那里放一个值,幸运的是你有一些可用的(r1,r2).问题是(对于任意r)没有通用的方法来组合两个值,所以你必须选择其中一个.

这就是你遇到法律问题的地方:

pure id <*> v = v

这项法律规定我们必须选择r2保留v.

u <*> pure y = pure ($ y) <*> u

既然我们要挑r2中<*>,这一法律的右侧表示,结果将包含r的一部分u.但那与左手边发生了冲突,这表示我们得到了r所返回的任何东西pure y.(u是一个完全任意的对,所以返回的固定值pure永远不会匹配它.)

因此,我们有一个矛盾,这意味着我们甚至不能定义<*>为((,) r).因此,你的第二个问题的答案是"不".

也就是说,有一个标准Applicative的对实例,但它需要r是Monoid:

instance (Monoid r) => Applicative ((,) r) where
    pure x = (mempty, x)
    (r1, f) (r2, x) = (mappend r1 r2, f x)