松散monoidal函数与不同monoidal结构 [英] Lax monoidal functors with a different monoidal structure

问题描述

在类别理论术语中，它可以用于显示 Applicative 的方法：

  pure :: a  - > f a 
（*）:: f（a  - > b） - > f a  - > fb 
  

相当于有一个 Functor f 与操作：



  unit :: f（）
（**）::（fa，fb） - > f（a，b）
  

想法是编写 pure code>你只需用给定的值替换 unit 中的（），然后写<$ c

$ p>（<*>）将函数和参数压缩到一个元组中，然后将合适的应用函数映射到元组上。 >此外，这种通信将应用法律变成关于单位和的自然monoidal-ish法则。 （**），所以实际上一个应用函子恰好是一个类别理论家称之为宽松的monoidal函子（因为（**）只是一种自然变化，而不是一种同构）。

好吧，很好，很好。这是众所周知的。但是，这只是一个宽松的monoidal仿函数族 - 那些尊重 product 的monoidal结构的函数族。宽松的monoidal函子包含源和目的地的两种monoidal结构选择：如果您将产品转换为和，您将获得以下结果：

  class PtS f where 
 unit :: f Void 
（**）:: fa  - > f b  - > f（或者ab）
 
  - 一些示例实例
实例PtS可能其中
 unit = Nothing 
 Nothing ** Nothing = Nothing 
只是* * Nothing = Just（Left a）
 Nothing ** Just b = Just（Right b）
 Just a ** Just b = Just（Left a） -  ick，但确实符合法律
 
实例PtS []其中
 unit = [] 
 xs ** ys = map左xs ++ map右ys 
  

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

• 其他松散monoidal函数类似上面的研究或有用吗？


• 对他们来说是一个很好的替代表达方式，例如 Applicative one？

解决方案

Applicative 的整洁替代表示法基于以下两个等同性

  pure a = fmap（const a）unit 
 unit = pure（）
 
 ff * fa = fmap（\（f，a） - > f a）$ ff ** fa 
 fa ** fb =纯（，）* fa * fb 
  

获得 Applicative 与 zipWith 的技巧相同 - 在接口中用类型或构造函数可以传入的东西来替换显式类型和构造函数，以恢复原始界面是。

  unit :: f（）
  

替换为 pure ，我们可以用（）和构造函数（）::（）来恢复 unit 。

  pure :: a  - > fa 
 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 then通过提升函数应用程序（$）::（a - > b） - >来获得好的< a - > $ b $ p $（<>）:: f（a - > ; b） - > f a - > fb
（*）= liftA2（$）


要找到整洁的替代表现为 PtS 我们需要找到





• 键入 Void 来恢复单元


• code>或者ab 和构造函数 Left :: a - > b 和 Right :: b - >或者ab 到恢复 **

（如果你注意到我们已经有一些构造函数 Left 和 Right 可以传递给你，我们可以替换 ** ，而不必按照我使用的步骤进行;直到解决问题后我才注意到这一点）

单位

这样，我们就可以替代 unit 作为总和：

  empty：fa 
 empty = fmap荒谬单位
 
单位:: f虚空
单位=空
  

运算符

我们希望找到（**）的替代方案。除了或者之外，还有一种替代方法可以将它们写成产品的函数。它显示为面向对象编程语言中的访问者模式，其中不存在和数。

 数据或者a b = Left a |右b 
 
 { - ＃LANGUAGE RankNTypes＃ - } 
类型Sum a b = forall c。 （a  - > c） - > （b→c）→> c 
  

如果您更改的顺序， code>的参数并部分应用它们。



 或者::（a  - > c） - > （b→c）→>无论是b  - > c 
 
 toSum ::或者b  - >总和b 
 toSum e = \forforA forB  - > forA forB e 
 
 toEither :: Sum a b  - >或者ab 
 to sither s = s Left Right 
  

我们可以看到或者ab≅Sum ab 。这允许我们重写（**）

 （ **）:: fa  - > f b  - > f（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 - > fc ，它只是假设 fmap ing已经完成，那么我们可以看到


  fmap（\ f  - > f forA forB）（fa ** fb）= fmap forA fa< ||> fmap forB fb 
  

或者返回或者：

  fa ** fb = fmap左fa< ||> fmap右fb 
 fa1< ||> fa2 = fmap（id id）$ fa1 ** fa2 
  

所以我们可以表达所有 PtS 可以用下面的类表示，并且可以实现 PtS 的所有内容都可以实现以下类：

  class Functor f =>几乎可选f其中
为空：f a 
（< ||>）:: f a  - > f a  - > fa 
  

这几乎可以肯定地与 Alternative Functor 为 Applicative 。

结论

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

  class（Functor f，forall a。Monoid（f a））=> MonoidalFunctor f 
  

全部a。 Monoid（f a）约束是伪代码;我不知道如何在Haskell中表达约束。

Applicative functors are well-known and well-loved among Haskellers, for their ability to apply functions in an effectful context.

In category-theoretic terms, it can be shown that the methods of Applicative:

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

are equivalent to having a Functor f with the operations:

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

the idea being that to write pure you just replace the () in unit with the given value, and to write (<*>) you squish the function and argument into a tuple and then map a suitable application function over it.

Moreover, this correspondence turns the Applicative laws into natural monoidal-ish laws about unit and (**), so in fact an applicative functor is precisely what a category theorist would call a lax monoidal functor (lax because (**) is merely a natural transformation and not an isomorphism).

Okay, fine, great. This much is well-known. But that's only one family of lax monoidal functors – those respecting the monoidal structure of the product. A lax monoidal functor involves two choices of monoidal structure, in the source and destination: here's what you get if you turn product into sum:

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

It seems like turning sum into other monoidal structures is made less interesting by unit :: Void -> f Void being uniquely determined, so you really have more of a semigroup going on. But still:

• Are other lax monoidal functors like the above studied or useful?
• Is there a neat alternative presentation for them like the Applicative one?

解决方案

The "neat alternative presentation" for Applicative is based on the following two equivalencies

pure a = fmap (const a) unit
unit = pure ()

ff <*> fa = fmap (\(f,a) -> f a) $ ff ** fa
fa ** fb = pure (,) <*> fa <*> fb

The trick to get this "neat alternative presentation" for Applicative is the same as the trick for zipWith - replace explicit types and constructors in the interface with things that the type or constructor can be passed into to recover what the original interface was.

unit :: f ()

Is replaced with pure which we can substitute the type () and the constructor () :: () into to recover unit.

pure :: a  -> f a
pure    () :: f ()

And similarly (though not as straightforward) for substituting the type (a,b) and the constructor (,) :: a -> b -> (a,b) into liftA2 to recover **.

liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2    (,)           :: f a -> f b -> f (a,b)

Applicative then gets the nice <*> operator by lifting function application ($) :: (a -> b) -> a -> b into the functor.

(<*>) :: f (a -> b) -> f a -> f b
(<*>) = liftA2 ($)

To find a "neat alternative presentation" for PtS we need to find

• something we can substitute the type Void into to recover unit
• something we can substitute the type Either a b and the constructors Left :: a -> Either a b and Right :: b -> Either a b into to recover **

(If you notice that we already have something the constructors Left and Right can be passed to you can probably figure out what we can replace ** with without following the steps I used; I didn't notice this until after I solved it)

unit

This immediately gets us an alternative to unit for sums:

empty :: f a
empty = fmap absurd unit

unit :: f Void
unit = empty

operator

We'd like to find an alternative to (**). There is an alternative to sums like Either that allows them to be written as functions of products. It shows up as the visitor pattern in object oriented programming languages where sums don't exist.

data Either a b = Left a | Right b

{-# LANGUAGE RankNTypes #-}
type Sum a b = forall c. (a -> c) -> (b -> c) -> c

It's what you would get if you changed the order of either's arguments and partially applied them.

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

We can see that Either a b ≅ Sum a b. This allows us to rewrite the type for (**)

(**) :: 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)

Now it's clear what ** does. It delays fmaping something onto both of its arguments, and combines the results of those two mappings. If we introduce a new operator, <||> :: f c -> f c -> f c which simply assumes that the fmaping was done already, then we can see that

fmap (\f -> f forA forB) (fa ** fb) = fmap forA fa <||> fmap forB fb

Or back in terms of Either:

fa ** fb = fmap Left fa <||> fmap Right fb
fa1 <||> fa2 = fmap (either id id) $ fa1 ** fa2

So we can express everything PtS can express with the following class, and everything that could implement PtS can implement the following class:

class Functor f => AlmostAlternative f where
    empty  :: f a
    (<||>) :: f a -> f a -> f a

This is almost certainly the same as the Alternative class, except we didn't require that the Functor be Applicative.

Conclusion

It's just a Functor that is a Monoid for all types. It'd be equivalent to the following:

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

The forall a. Monoid (f a) constraint is pseudo-code; I don't know a way to express constraints like this in Haskell.

这篇关于松散monoidal函数与不同monoidal结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！