(\f -> fmap f id) 总是等同于 arr 吗？

Question

Category 的某些实例也是 Functor 的实例。例如：

{-# LANGUAGE ExistentialQuantification, TupleSections #-}

import Prelude hiding (id, (.))
import Control.Category
import Control.Arrow

data State a b = forall s. State (s -> a -> (s, b)) s

apply :: State a b -> a -> b
apply (State f s) = snd . f s

assoc :: (a, (b, c)) -> ((a, b), c)
assoc (a, (b, c)) = ((a, b), c)

instance Category State where
    id = State (,) ()
    State g t . State f s = State (\(s, t) -> assoc . fmap (g t) . f s) (s, t)

(.:) :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b)
(.:) = fmap . fmap

instance Functor (State a) where
    fmap g (State f s) = State (fmap g .: f) s

instance Arrow State where
    arr f = fmap f id
    first (State f s) = State (\s (x, y) -> fmap (,y) (f s x)) s

此处 arr f = fmap f id instance Arrow State。 Category 也是 Functor 的所有实例都是如此吗？类型签名是：

arr               ::                 Arrow    a  => (b -> c) -> a b c
(\f -> fmap f id) :: (Functor (a t), Category a) => (b -> c) -> a b c

我觉得他们应该是等价的。

Answer 1

首先要弄清楚Arrow C是什么意思。嗯，这是两个完全不同的东西的结合——在我的书中，

well-pointed monoidal categories.class.
categories which generalise Hask.class.

arr来自后者。 “泛化”Hask？这意味着只是有一个从类别 Hask 到 C 的映射。 – 从数学上讲，从一个类别映射到另一个类别正是 functor 所做的！（标准 Functor class 实际上只涵盖了一种非常特殊的函子，即 Hask 上的内函子。） arr 是一个非内函子，即“规范嵌入函子” Hask → C.

由此看来，前两个箭头定律

arr id = id
arr (f >>> g) = arr f >>> arr g

只是函子定律。

现在，如果您要为类别实施 Functor 实例，这意味着什么？为什么，我敢说它只是意味着你在表达相同的规范嵌入函子，但是通过 C 的必要表示返回 Hask （这使它成为一个整体的内函子）。因此，我认为是的，\f -> fmap f id 应该等同于 arr，因为基本上它们是表达同一事物的两种方式。

Answer 2

这里有一个推导来补充leftaroundabout的解释。为清楚起见，我将为 (->) 保留 (.) 和 id，并为一般 Category 方法使用 (<<<) 和 id'。

我们从preComp开始，也称为(>>>):

preComp :: Category y => y a b -> (y b c -> y a c)
preComp v = \u -> u <<< v

fmap 通过 Hask 内函子之间的自然转换进行通勤。对于也有一个 Functor 实例的 Category，preComp v 是一个自然变换（从 y b 到 y a），因此它与 fmap.由此可见：

fmap f . preComp v = preComp v . fmap f
fmap f (u <<< v) = fmap f u <<< v
fmap f (id' <<< v) = fmap f id' <<< v
fmap f v = fmap f id' <<< v

那是我们的候选人arr！所以让我们定义arr' f = fmap f id'。我们现在可以验证 arr' 是否遵循第一箭头定律...

-- arr id = id'
arr' id
fmap id id'
id'

...还有第二个：

-- arr (g . f) = arr g <<< arr f
arr' (g . f)
fmap (g . f) id'
(fmap g . fmap f) id'
fmap g (fmap f id')
fmap g (arr' f)
fmap g id' <<< arr' f -- Using the earlier result.
arr' g <<< arr' f

我想我们能做到的就这些了。其他五个箭头定律涉及 first，正如 leftaroundabout 指出的 arr 和 first 是独立的。

(\f -> fmap f id) 总是等同于 arr 吗？

Is (\f -> fmap f id) always equivalent to arr?

haskell

functor

category-theory

arrows

category-abstractions