haskell - 是否有不能遵守法律的仿函数？

Question

recent question通常询问各种Haskell类之间的边界。我想出了 Handler 作为有效Functor的示例，没有明智的 Apply **实例，其中

class Functor f => Apply f where
  (<.>) :: f (a -> b) -> f a -> f b
  -- optional bits omitted.

但是，我还没有找到一个有效的 Functor的示例，该示例无法成为 Apply的有效(如果没有意义)实例。 Apply仅具有一项法律(请参阅更新)，

(.) <$> u <.> v <.> w = u <.> (v <.> w)

似乎使这一点变得棘手。

pig 工(Conor McBride)以前不是 Functor的 Applicative的 gave an example，但是他依靠 pure这样做，而 Apply中不可用。

**然后我意识到实际上 Apply可能存在一个明智的(尽管有些奇怪) Handler实例，该实例在概念上收集了同时发生的异常。

更新资料

Edward Kmett现在有了 accepted我为 Apply提出的另外两项法律(以验证我对 Apply (Coyoneda f)实例所做的优化):

x <.> (f <$> y) = (. f) <$> x <.> y
f <$> (x <.> y) = (f .) <$> x <.> y

看看这些增加的内容是否改变了这个问题的答案，将是很有趣的。

Answer 1

是的，有Functor，没有Apply实例。考虑两个函数的总和(exponents in algebraic data types):

data EitherExp i j a
    = ToTheI (i -> a)
    | ToTheJ (j -> a)

所有 Functor和 i都有一个 j实例:

instance Functor (EitherExp i j) where
    fmap f (ToTheI g) = ToTheI (f . g)
    fmap f (ToTheJ g) = ToTheJ (f . g)

但是对于所有 Apply和 i没有 j实例

instance Apply (EitherExp i j) where
    ...
    ToTheI f <.> ToTheJ x = ____

当您只有 ____和 i -> b时，无法用 j -> b或 f :: i -> a -> b填充空白 x :: j -> a。为此，我们必须了解有关 i和 j的知识，但是无法在Haskell中查看每种类型 i或 j的内容。直觉拒绝了这个答案；如果您对 i或 j有所了解，例如它们被一个值占用，则可以为 Apply编写一个 EitherExp实例

class Inhabited a where
    something :: a

instance (Inhabited i, Inhabited j) => Apply (EitherExp i j) where
    ...
    ToTheI f <.> ToTheJ x = ToTheI (const ((f something) (x something)))

但是我们不知道每个 i和每个 j都是 Inhabited。 Void 类型不存在任何内容。我们甚至没有办法知道每种类型都是 Inhabited或 Void。

我们的直觉实际上是非常好的。当我们可以检查类型的构造方式时，对于代数数据类型，没有没有 Functor实例的 Apply。接下来是两个答案，它们可能更符合我们的直觉。

不...

...用于代数数据类型。有3种可能性。该结构为空，该结构可以为空，或者该结构不能为空。如果该结构无效，则它是 absurd 就是 Apply。如果可以为空，请选择任何空实例，并在应用时不断返回它。如果它不能为空，那么它是一个结构的总和，每个结构都不能为空，可以通过将第一个值†应用于第二个值†并将其返回来遵守法律以某种恒定的结构。

适用法律非常宽松。 Apply不需要任何意义。它不需要是“zip-y”。当与诸如 fmap中的 pure之类的可疑东西组合时，它不需要是 Applicative；没有 pure的概念可以用来编写要求它有意义的法律。

当结构可以为空时

选择任何空实例，并在适用的情况下不断返回

u <.> v = empty

证明

  (.) <$> u  <.> v  <.> w = u <.> (v <.> w)
(((.) <$> u) <.> v) <.> w = u <.> (v <.> w) -- by infixl4 <$>, infixl4 <.>
(_                ) <.> w = u <.> (_      ) -- by substitution
                    empty = empty           -- by definition of <.>

当结构不能为空时

如果 f结构不能为空，则存在一个函数 extract :: forall a. f a -> a。选择另一个函数 c :: forall a. a -> f a，该函数始终构造相同的非空结构，并在各处填充自变量，并定义:

u <.> v = c (extract u $ extract v)

用自由定理

extract (f <$> u) = f (extract u)
extract . c = id

证明

  (.) <$> u  <.> v  <.> w = u <.> (v <.> w)
(((.) <$> u) <.> v) <.> w = u <.> (v <.> w) -- by infixl4 <$>, infixl4 <.>
(c (extract ((.) <$> u) $ extract v)) <.> w = u <.> (v <.> w) -- by definition
(c ((.) (extract u)     $ extract v)) <.> w = u <.> (v <.> w) -- by free theorem 
c (extract (c ((.) (extract u) $ extract v)) $ extract w) = u <.> (v <.> w) -- by definition
c (           ((.) (extract u) $ extract v)  $ extract w) = u <.> (v <.> w) -- by extract . c = id
c (((.) (extract u) $ extract v) $ extract w) = u <.> c (extract v $ extract w) -- by definition
c (((.) (extract u) $ extract v) $ extract w) = c (extract u $ extract (c (extract v $ extract w))) -- by definition
c (((.) (extract u) $ extract v) $ extract w) = c (extract u $            (extract v $ extract w) ) -- by extract . c = id
let u' = extract u
    v' = extract v
    w' = extract w
c (((.) u' $ v') $ w') = c (u' $ (v' $ w'))
c ((u' . v') $ w') = c (u' $ (v' $ w')) -- by definition of partial application of operators
c (u' $ (v' $ w')) = c (u' $ (v' $ w')) -- by definition of (.)

关于为指数类型，函数定义 extract，应该多说一点。对于函数 i -> a，有两种可能性。 i是有人居住的还是不是。如果有人居住，请选择一个居民 i†并定义

extract f = f i

如果 i无人居住(无效)，则 i -> a是具有单个值 absurd的单位类型。 Void -> a只是另一个精心制作的空类型，不包含任何 a；将其视为可以为空的结构。

当结构无效时

当结构为空时，将无法构造它。我们可以从所有可能的构造(没有要传递给任何其他构造)的任何其他类型编写一个函数。

absurd :: Void -> a
absurd x = case x of {}

空隙结构可以是带有 Functor的 fmap f = absurd。用同样的方式，他们可以拥有一个 Apply实例，

(<.>) = absurd

我们可以证明所有 u， v和 w

(.) <$> u  <.> v  <.> w = u <.> (v <.> w)

没有 u， v或 w，声明为 vacuously true。

†关于接受选择公理为指数类型 a选择索引 a -> b的一些警告

是的

...对于Haskell。想象一下，除了 Monad之外，还有另一个基本的 IO，我们称它为 OI。然后 Sum IO OI是 Functor，但永远不能是 Apply。

...针对现实世界。如果您有一台可以向其发送功能(或Hask以外的类别中的箭头)但不能将其中两台计算机组合在一起或无法提取其运行状态的计算机，则它们是没有应用的函子。