34

应用函子在 Haskeller 中广为人知并深受喜爱，因为它们能够在有效的上下文中应用函数。

在范畴论术语中，可以证明 的方法Applicative：

pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b

等同于有一个Functor fwith 操作：

unit :: f ()
(**) :: (f a, f b) -> f (a,b)

这个想法是写pure你只需用给定的值替换()in ，并将你的函数和参数压缩到一个元组中，然后在它上面映射一个合适的应用程序函数。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

通过唯一确定，将 sum 转换为其他幺半群结构似乎变得不那么有趣了unit :: Void -> f Void，所以你真的有更多的半群在进行。但仍然：

  • 其他像上面这样的宽松单曲面函子是否研究过或有用？
  • 有没有像他们一样的简洁的替代演示Applicative？
4

3 回答 3

18

“整洁的替代呈现”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's 参数的顺序并部分应用它们，你会得到什么。

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到它的两个参数上，并结合这两个映射的结果。如果我们引入一个 new 运算符，<||> :: f c -> f c -> f c它只是假设fmaping 已经完成，那么我们可以看到

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类相同，只是我们不要求Functorbe Applicative。

结论

它只是一个Functor适用Monoid于所有类型的。它相当于以下内容：

class (Functor f, forall a. Monoid (f a)) => MonoidalFunctor f

forall a. Monoid (f a)约束是伪代码；我不知道如何在 Haskell 中表达这样的约束。

于 2014-04-27T07:00:21.503 回答
15

在你甚至可以谈论幺半群函子之前，你需要确保你在一个幺半群类别中。碰巧Hask在以下方面是一个幺半群：

  • ()作为身份
  • (,)作为双函子
  • 识别同构类型，即(a,()) ≅ ((),a) ≅ a和(a,(b,c)) ≅ ((a,b),c)。

()正如您所观察到的，当您交换Void和(,)时，它也是一个幺半群类别Either。
然而，monoidal 并不能让你走得太远——让Hask如此强大的原因在于它是笛卡尔封闭的。这为我们提供了 currying 和相关技术，没有这些 applicative 几乎毫无用处。

一个幺半群类别可以是笛卡尔封闭的，当且仅当它的身份是一个终端对象，即一个类型上恰好存在一个（当然，我们在这里忽略⟂）箭头。A -> ()任何类型都有一个功能A，即const (). 然而没有任何功能A -> Void。相反，Void是初始对象：它恰好存在一个箭头，即absurd :: Void -> a方法。这样的幺半群类别不能是笛卡尔封闭的。
现在，当然，您可以通过转动箭头方向轻松地在初始和终端之间切换。这总是把你放在对偶结构中，所以我们得到一个cocartesian 封闭类​​别. 但这意味着您还需要翻转单曲面函子中的箭头。那些被称为决定性函子（并概括comonads）。凭借 Conor 令人惊叹的命名方案，

class (Functor f) => Decisive f where
  nogood :: f Void -> Void
  orwell :: f (Either s t) -> Either (f s) (f t)
于 2014-04-26T21:44:39.147 回答
8

我在范畴论方面的背景非常有限，但是 FWIW，你的 PtS 课程让我想起了Alternativeclass，它基本上看起来像这样：

class Applicative f => Alternative f where
  empty :: f a
  (<|>) :: f a -> f a -> f a

唯一的问题当然Alternative是Applicative. 但是，也许可以想象它被分开呈现，Applicative那么与的组合很容易让人联想到具有非交换环状结构的函子，两个幺半群结构作为环的操作？Applicative和AlternativeIIRC之间也有分配规律。

于 2014-04-27T06:02:42.613 回答