是否有一个不能守法的Functor申请？

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)

似乎使这个相当棘手.

pigworker(康纳·麦克布莱德)前面举了一个例子的Functor,是不是Applicative,但他依靠pure这样做,这不是可用Apply.

**后来我意识到实际上可能有一个明智的(虽然有点奇怪)Apply实例Handler,从概念上收集同时异常.

---

更新

Edward Kmett现在接受了我提出的另外两条法律Apply(用于验证我对该Apply (Coyoneda f)实例所做的优化):

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

看看这些增加是否会改变这个问题的答案将会很有趣.

Answer 1

两个仿函数(Data.Functor.Sum来自transformers)的"总和" 似乎就是一个例子.

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

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 = ..... ?

Answer 2

是的,有Functor没有Apply实例的s .考虑两个函数的总和(它们是代数数据类型中的指数):

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

Functor所有is和js 都有一个实例:

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

但并没有Apply所有is和js的实例

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

没有办法填补空白____.要做到这一点,我们必须了解一些关于i -> b和j -> b,但没有办法查看每个类型f :: i -> a -> b或x :: j -> aHaskell.直觉拒绝这个答案; 如果你知道任何事情,i或者j就像他们居住在一个单一的值,那么你可以写一个i实例j

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都是Apply.这种EitherExp类型没有任何东西居住.我们甚至没有办法知道每种类型都是i或j.

我们的直觉实际上非常好; 当我们可以检查如何构造类型时,对于代数数据类型,没有Inhabited没有Void实例的s .以下是两个可能更令我们直觉感到满意的答案.

不......

...代数数据类型.有3种可能性.结构无效,结构可以是空的,或者结构不能为空.如果结构是空的那么它就是Inhabited一个Void.如果它可以为空,请选择任何空实例并不断返回以进行任何应用.如果它不能为空,那么它的结构,每一个不能为空的总和,一个守法的应用可以通过应用中的一个值进行^†从第一个到的一个值从第二和返回它在一些不变的结构中.

适用法律非常宽松.申请不需要任何意义.它不需要是"zip-y".它并不需要是Functor当事情很像结合Apply从absurd; 没有一个概念Apply可以写出要求它有意义的法律.

当结构可以是空的

选择任何空实例并不断返回以进行任何应用

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 <.>

当结构不能为空时

如果结构fmap不能为空,则存在函数pure.选择另一个函数Applicative,它总是在任何地方构造相同的非空结构,并定义:

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 (.)

关于定义pure指数类型函数,还应该说一点.对于功能f,有两种可能性.无论extract :: forall a. f a -> a是有人居住还是不居住.如果它有人居住,选择一些居民c :: forall a. a -> f a^†并定义

extract f = f i

如果extract无人居住(它是无效的)那么i -> a单位类型是单值i.i只是另一个精巧的空类型,没有任何is; 把它当作一个可以为空的结构.

当结构无效时

当结构无效时,没有办法构造它.我们可以从每个可能的构造(没有传递给它)到任何其他类型编写单个函数.

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

虚空结构可以i -> as的absurd.以同样的方式,他们可以拥有一个Void -> a实例

(<.>) = absurd

我们可以轻而易举地证明,对所有人a来说Functor,和fmap f = absurd

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

没有Apply,u或者说v这个说法是空洞的.

^†有一些关于接受选择公理的注意事项,以选择w指数类型的索引u

是的......

......对于Haskell.试想一下,有另一个基地v以外w,让我们把它a.然后a -> b是一个Monad但永远不会是一个IO.

......为现实世界.如果你有一台可以发送功能的机器(或Hask以外的类别中的箭头),但不能将两台机器组合在一起或提取它们的运行状态,那么它们就是没有应用的Functor.