应用函子在 Haskellers 中广为人知并深受喜爱,因为它们能够在有效的上下文中应用函数。
用范畴论的术语来说,可以证明Applicative
的方法:
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
等效于对操作进行Functor f
:
unit :: f ()
(**) :: (f a, f b) -> f (a,b)
这个想法是,要编写pure
,您只需将 unit
中的()
替换为给定的值,并且编写(<*>)
您将函数和参数压缩到元组中,然后在其上映射合适的应用程序函数。
此外,这种对应关系将Applicative
定律变成了关于unit
和(**)
的自然幺半定律,所以实际上应用函子正是范畴理论家所说的松幺半函子(松弛是因为(**)
只是一个自然变换而不是同构(。
好的,太好了。这是众所周知的。但这只是松散的幺半函子家族之一——那些尊重产品的幺半结构的函子。松幺半函子涉及源和目标中的两种幺半结构选择:如果您将乘积转换为总和,您将获得以下结果:
class PtS f where
unit :: f Void
(**) :: f a -> f b -> f (Either a b)
-- some example instances
instance PtS Maybe where
unit = Nothing
Nothing ** Nothing = Nothing
Just a ** Nothing = Just (Left a)
Nothing ** Just b = Just (Right b)
Just a ** Just b = Just (Left a) -- ick, but it does satisfy the laws
instance PtS [] where
unit = []
xs ** ys = map Left xs ++ map Right ys
似乎将总和转换为其他幺半结构会因为唯一确定而变得不那么有趣unit :: Void -> f Void
所以你真的有更多的半群在进行。但仍然:
- 像上面研究过的其他松幺半函子还是有用的?
- 有没有像
Applicative
那样的整洁的替代演示文稿?
Applicative
的"整洁替代表示"基于以下两个等价
pure a = fmap (const a) unit
unit = pure ()
ff <*> fa = fmap ((f,a) -> f a) $ ff ** fa
fa ** fb = pure (,) <*> fa <*> fb
为Applicative
获取这种"整洁的替代表示"的技巧与zipWith
的技巧相同 - 将接口中的显式类型和构造函数替换为类型或构造函数可以传递到的内容以恢复原始接口是什么。
unit :: f ()
替换为 pure
,我们可以替换类型 ()
和构造函数() :: ()
以恢复unit
.
pure :: a -> f a
pure () :: f ()
类似地(尽管不是那么简单(将类型(a,b)
和构造函数(,) :: a -> b -> (a,b)
替换为liftA2
以恢复**
。
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 (,) :: f a -> f b -> f (a,b)
然后,Applicative
通过将函数应用程序($) :: (a -> b) -> a -> b
提升到函子中来获得漂亮的<*>
运算符。
(<*>) :: f (a -> b) -> f a -> f b
(<*>) = liftA2 ($)
要为PtS
找到一个"整洁的替代演示文稿",我们需要找到
- 我们可以替换
Void
的类型来恢复unit
我们可以替换类型和构造函数 Either a b
Left :: a -> Either a b
和Right :: b -> Either a b
的东西来恢复**
(如果你注意到我们已经有了构造函数Left
的东西,Right
可以传递给你,你可能会弄清楚我们可以用什么替换**
,而无需遵循我使用的步骤;直到我解决了它之后我才注意到这一点(
单位
这立即为我们提供了unit
的替代方案:
empty :: f a
empty = fmap absurd unit
unit :: f Void
unit = empty
算子
我们想找到(**)
的替代品。除了像Either
这样的总和之外,还有一种替代方法,允许将它们写成产品的函数。它在面向对象的编程语言中显示为访问者模式,其中不存在总和。
data Either a b = Left a | Right b
{-# LANGUAGE RankNTypes #-}
type Sum a b = forall c. (a -> c) -> (b -> c) -> c
这就是如果你改变either
的参数顺序并部分应用它们会得到的。
either :: (a -> c) -> (b -> c) -> Either a b -> c
toSum :: Either a b -> Sum a b
toSum e = forA forB -> either forA forB e
toEither :: Sum a b -> Either a b
toEither s = s Left Right
我们可以看到Either a b ≅ Sum a b
.这允许我们重写(**)
的类型
(**) :: f a -> f b -> f (Either a b)
(**) :: f a -> f b -> f (Sum a b)
(**) :: f a -> f b -> f ((a -> c) -> (b -> c) -> c)
现在很清楚**
是做什么的。它延迟fmap
到其两个参数上的内容,并组合这两个映射的结果。如果我们引入一个新的运算符,<||> :: f c -> f c -> f c
它只是假设fmap
已经完成,那么我们可以看到
fmap (f -> f forA forB) (fa ** fb) = fmap forA fa <||> fmap forB fb
或者回到Either
方面:
fa ** fb = fmap Left fa <||> fmap Right fb
fa1 <||> fa2 = fmap (either id id) $ fa1 ** fa2
因此,我们可以用下面的类表达PtS
可以表达的一切,而所有可以实现PtS
的东西都可以实现下面的类:
class Functor f => AlmostAlternative f where
empty :: f a
(<||>) :: f a -> f a -> f a
这几乎可以肯定与Alternative
类相同,只是我们不要求Applicative
Functor
。
结论
这只是一个适合所有类型的Monoid
的Functor
。它等效于以下内容:
class (Functor f, forall a. Monoid (f a)) => MonoidalFunctor f
forall a. Monoid (f a)
约束是伪代码;我不知道在 Haskell 中表达这种约束的方法。
在你谈论幺半函子之前,你需要确保你属于幺半函子类别。碰巧Hask是以下一种幺半范畴:
-
()
身份 -
(,)
作为双函子 - 识别同构类型,即
(a,()) ≅ ((),a) ≅ a
,(a,(b,c)) ≅ ((a,b),c)
。
就像你观察到的,当你用()
换Void
,用(,)
换Either
时,这也是一个幺半的范畴。
然而,幺半并不能让你走得太远——哈斯克之所以如此强大,是因为它是笛卡尔闭合的。这给了我们柯里和相关技术,没有这些技术,应用将几乎毫无用处。
幺半范畴可以是笛卡尔闭合的,因为它的恒等式是一个终端对象,即一个类型,其上正好存在一个(当然,我们在这里忽略⟂(箭头。对于任何类型的A
,都有一个函数A -> ()
,即const ()
。但是,没有功能A -> Void
。相反,Void
是初始对象:正好存在一个箭头,即absurd :: Void -> a
方法。这样的幺半范畴不可能是笛卡尔式的封闭。
当然,现在您可以通过旋转箭头方向轻松地在初始和终端之间切换。这总是把你放在对偶结构中,所以我们得到了一个笛卡尔封闭的类别。但这意味着您还需要翻转幺半函子中的箭头。这些被称为决定性函子(并推广共通(。凭借康纳如此惊人的命名方案,
class (Functor f) => Decisive f where
nogood :: f Void -> Void
orwell :: f (Either s t) -> Either (f s) (f t)
我在范畴论方面的背景非常有限,但是 FWIW,您的 PtS 类让我想起了Alternative
类,它基本上看起来像这样:
class Applicative f => Alternative f where
empty :: f a
(<|>) :: f a -> f a -> f a
当然,唯一的问题是Alternative
是Applicative
的延伸。 然而,也许可以想象它是单独呈现的,与Applicative
的组合很容易让人联想到具有非交换环状结构的函子,其中两个幺半群结构作为环的操作?IIRC Applicative
和Alternative
之间也有分配法。