有没有不能守法Apply的Functor?

Is there a Functor that cannot be a law-abiding Apply?

A recent question asked generally about boundaries between various Haskell classes. I came up with Handler as an example of a valid Functor with no sensible instance of 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)

这似乎变得相当棘手。

pigworker (Conor McBride) 以前 gave an exampleFunctor 不是 Applicative,但他依靠 pure 这样做,而这在Apply.

** 后来我意识到 Handler 实际上可能有一个合理的(虽然有点奇怪)Apply 实例,它在概念上收集同时发生的异常。


更新

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

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

看看这些添加是否会改变这个问题的答案会很有趣。

两个函子的"sum"(来自transformersData.Functor.Sum)似乎就是一个例子。

可以很容易地映射到一个分支或另一个分支,但是当函子中的函数和函子中的参数位于不同的分支时如何实现<.>

ghci> import Data.Functor.Sum
ghci> import Data.Functor.Identity
ghci> let f = InL (Const ())   :: Sum (Const ()) Identity (Int -> Int)
ghci> let x = InR (Identity 5) :: Sum (Const ()) Identity Int
ghci$ f <.> x = ..... ?

这不是您要找的东西,但它很接近所以我想我会分享它。标准 Writer monad 对其 Apply 实例有一个额外的约束(即 w 类型是 MonoidSemigroup 的实例),即 Functor 实例不存在,因此如果 Foo 不是 Semigroup/Monoid,则 Writer FooFunctor 而不是 Apply

data Writer w a = Writer w a

instance Monoid w => Apply (Writer w) where
  Writer w1 f <.> Writer w2 x = Writer (mappend w1 w2) (f x)

但是,这并不是您所要求的真正示例,因为实际上可以在没有 Monoid 约束的情况下创建 Apply 的守法实例:

instance Apply (Writer w) where
  Writer w1 f <.> Writer w2 x = Writer w1 (f x)

这个实例的问题是它不允许匹配 Applicative 实例,因为没有办法实现 pure 这样你就可以得到左标识,即:

pure id <.> x /= x

这只是为您提供与 Conor 相同的答案的长篇大论:依赖 pure 破坏实例的演示。

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

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

所有 ij 都有一个 Functor 实例:

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

但是所有 ij 都没有 Apply 实例

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

当您只有 f :: i -> a -> bx :: j -> a 时,无法用 i -> bj -> b 填充空白 ____。为此,我们必须对 ij 有所了解,但无法深入了解 Haskell 中的每个类型 ij。直觉拒绝这个答案;如果你知道 任何 关于 ij,就像它们被一个单一的值所占据,那么你可以为 [写一个 Apply 实例=43=]

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 都是 InhabitedVoid 类型不存在任何东西。我们甚至没有办法知道每种类型是 Inhabited 还是 Void

我们的直觉其实很好;当我们可以检查类型的构造方式时,对于代数数据类型,没有 Functor 没有 Apply 实例。以下是两个可能更符合我们直觉的答案。

没有...

... 对于代数数据类型。有3种可能性。结构为空,结构可以为空,或者结构不能为空。如果结构是空的,那么它就是 absurd 一个 Apply。如果它可以为空,则选择任何空实例并 return 它不断地用于任何应用。如果它不能为空则它是每个都不能为空的结构的总和,可以通过从第一个到来自第二个的值之一,然后 return 将其放入某个常量结构中。

适用法律非常宽松。 Apply 不需要有任何意义。它不需要是 "zip-y"。当与 Applicative 中的 pure 这样可疑的东西结合时,它不需要是 fmap;没有 pure 的概念来编写要求它有意义的法律。

当结构可以为空时

选择任何空实例并return它不断地应用

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;将其视为可以为空的结构。

当结构为空时

当结构为空时,就没有办法构造它。我们可以从每个可能的构造(有 none 传递给它)编写一个函数到任何其他类型。

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

空结构可以 Functorfmap f = absurd。以同样的方式,他们可以有一个 Apply 实例

(<.>) = absurd

我们可以简单地证明对于所有 uvw

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

没有uvw,声明为vacuously true


关于接受选择公理以选择指数类型 a 的一些注意事项 a -> b


是的...

... 对于 Haskell。想象一下,除了 IO 之外,还有另一个基数 Monad,我们称它为 OI。那么 Sum IO OIFunctor 但永远不可能是 Apply.

...对于现实世界。如果您有一台可以向其发送函数(或 Hask 以外的类别中的箭头)的机器,但不能将两台机器组合在一起或提取它们的 运行 状态,那么它们是一个没有 Apply 的 Functor。