haskell - 具有不同幺半群结构的松散幺半群仿函数

Question

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

在范畴论方面，可以证明 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 似乎使 sum 变成其他幺半群结构变得不那么有趣了。被独特地确定，所以你真的有更多的半群在进行。但仍然:

其他像上面这样的宽松单曲面仿函数是否研究过或有用？

有没有像 Applicative 这样的简洁替代演示文稿？一？

Answer 1

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 的技巧相同- 将接口(interface)中的显式类型和构造函数替换为可以传递类型或构造函数以恢复原始接口(interface)的内容。

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然后得到不错的 <*>运算符(operator)通过提升功能应用 ($) :: (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

运算符(operator)

我们希望找到 (**) 的替代方案.总和有另一种选择，例如 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 ing 已经完成了，那么我们可以看到

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

结论

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

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

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