Monoidal Functor是适用的,但是Applicative定义中的Monoid类型类是什么？

Question

适用于Monoidal Functor:

mappend :: f         -> f   -> f
$       ::  (a -> b) ->   a ->   b
<*>     :: f(a -> b) -> f a -> f b

但是我没有在应用类型类的定义中看到有关Monoid的任何参考,你能告诉我为什么吗？

定义:

class Functor f => Applicative (f :: * -> *) where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
  GHC.Base.liftA2 :: (a -> b -> c) -> f a -> f b -> f c
  (*>) :: f a -> f b -> f b
  (<*) :: f a -> f b -> f a
  {-# MINIMAL pure, ((<*>) | liftA2) #-}

在这个定义中没有提到结构Monoid,但是当你这样做时

> ("ab",(+1)) <*> ("cd", 5) 
>("abcd", 6)

在实现Applicative的这个实例时,你可以清楚地看到使用Structural Monoid"(,)String".

显示使用"结构Monoid"的另一个示例:

Prelude Data.Monoid> (2::Integer,(+1)) <*> (1::Integer,5)

<interactive>:35:1: error:
    • Could not deduce (Monoid Integer) arising from a use of ‘<*>’
      from the context: Num b
        bound by the inferred type of it :: Num b => (Integer, b)
        at <interactive>:35:1-36
    • In the expression: (2 :: Integer, (+ 1)) <*> (1 :: Integer, 5)
      In an equation for ‘it’:
          it = (2 :: Integer, (+ 1)) <*> (1 :: Integer, 5)

Answer 1

用"幺半体函子"引用的Monoid幺半群不是幺半群,即一个价值级的幺半群.这是一个类型级别的monoid.即,镗孔产品幺半群

type Mempty = ()
type a <> b = (a,b)

(您可能会注意到,这并不是严格意义上的幺半群;只有当您考虑((a,b),c)并且(a,(b,c))作为相同类型时才会这样.它们确实足够同构.)

要了解这与此有什么关系Applicative,请分别说明.monoidal仿函数,我们需要用其他术语来编写类.

class Functor f => Monoidal f where
  pureUnit :: f Mempty
  fzip :: f a -> f b -> f (a<>b)

-- an even more “general nonsense”, equivalent formulation is
-- upure :: Mempty -> f Mempty
-- fzipt :: (f a<>f b) -> f (a<>b)
-- i.e. the functor maps a monoid to a monoid (in this case the same monoid).
-- That's really the mathematical idea behind this all.

IOW

class Functor f => Monoidal f where
  pureUnit :: f ()
  fzip :: f a -> f b -> f (a,b)

这是一个简单的练习,用于定义标准Applicative类的通用实例Monoidal,反之亦然.

关于("ab",(+1)) <*> ("cd", 5):这与Applicative一般情况下没有太大关系,但仅与作者应用具体相关.实例是

instance Monoid a => Monoidal ((,) a) where
  pureUnit = (mempty, ())
  fzip (p,a) (q,b) = (p<>q, (a,b))

Answer 2

也许你正在寻找的幺半群就是这个.

newtype AppM f m = AppM (f m) deriving Show

instance (Applicative f, Monoid m) => Monoid (AppM f m) where
  mempty                      = AppM (pure mempty)
  mappend (AppM fx) (AppM fy) = AppM (pure mappend <*> fx <*> fy)

作为评论,在下面,观察,它可以在名称下的reducers库中找到Ap.这是至关重要的Applicative,所以让我们打开它.

特别要注意的是,因为()很简单Monoid,所以AppM f ()也是a Monoid.这就是潜伏在背后的幺半群Applicative f.

我们本来可以坚持Monoid (f ())作为一个超级类别Applicative,但那可能会使王室犯规.

> mappend (AppM [(),()]) (AppM [(),(),()])
AppM [(),(),(),(),(),()]

底层的幺半群Applicative []是自然数的乘法,而列表的"明显的" 幺半群结构是连接,专门用于添加自然数.

数学警告.依赖类型警告.假Haskell警告.

一种看待正在发生的事情的方法是考虑那些恰好是雅培,阿尔滕基希和加尼的依赖性意义上的容器.我们很快就会在Haskell中拥有这些.我只是假装未来已经到来.

data (<|) (s :: *)(p :: s -> *) (x :: *) where
  (:<|:) :: pi (a :: s) -> (p a -> x) -> (s <| p) x

数据结构(s <| p)的特点是

• 形状 s告诉你容器的样子.
• 位置 p,告诉你一个给定的形状,你可以把数据.

上面的类型说,为这样的结构提供数据是选择一个形状,然后用数据填充所有位置.

容器的介绍[]是Nat <| Fin在哪里

data Nat = Z | S Nat
data Fin (n :: Nat) where
  FZ :: Fin (S n)
  FS :: Fin n -> Fin (S n)

所以它Fin n具有确切的n价值.也就是说,列表的形状是它的长度,它告诉您填充列表需要多少元素.

您可以Functor f通过拍摄找到Haskell的形状f ().通过使数据微不足道,位置无关紧要.在Haskell中一般地构建GADT位置要困难得多.

Parametricity告诉我们容器之间的多态函数

forall x. (s <| p) x -> (s' <| p') x

必须由

• f :: s -> s'将输入形状映射到输出形状的函数
• 函数g :: pi (a :: s) -> p' (f a) -> p a映射(对于给定的输入形状)输出位置返回到输出元素将来自的输入位置.

morph f g (a :<|: d) = f a :<|: (d . g a)

(偷偷地说,我们这些接受过基本汉考克训练的人也将"形状"视为"命令"和"位置"作为"有效反应".容器之间的态度恰恰是"设备驱动".但我离题了. )

按照类似的思路思考,制作容器需要Applicative什么？对于初学者,

pure :: x -> (s <| p) x

这是等价的

pure :: (() <| Const ()) x -> (s <| p) x

这必须由

f :: () -> s   -- a constant in s
g :: pi (a :: ()) -> p (f ()) -> Const () a  -- trivial

其中f = const neutral一些

neutral :: s

现在,怎么样

(<*>) :: (s <| p) (x -> y) -> (s <| p) x -> (s <| p) y

？同样,参数化告诉我们两件事.首先,计算输出形状的唯一有用数据是两个输入形状.我们必须有一个功能

outShape :: s -> s -> s

其次,我们用a填充输出位置的唯一方法y是从第一个输入中选择一个位置,以在"x - > y"中找到一个函数,然后在第二个输入中找到一个位置以获得其参数.

inPos :: pi (a :: s)(b :: s) -> p (outShape a b) -> (p a, p b)

也就是说,我们总是可以识别确定输出位置输出的输入位置对.

适用法律告诉我们neutral并且outShape必须遵守幺半群定律,而且,我们可以如下提升幺半群

mappend (a :<|: f) (b :<|: g) = outShape a b :<|: \ z ->
  let (x, y) = inPos a b z
  in  mappend (f x) (g y)

这里还有更多要说的内容,但为此,我需要对容器上的两个操作进行对比.

组成

(s <| p) . (s' <| p')  =  ((s <| p) s') <| \ (a :<|: f) -> Sigma (p a) (p' . f)

Sigma从属对的类型在哪里

data Sigma (p :: *)(q :: p -> *) where
  Pair :: pi (a :: p) -> q a -> Sigma p q

究竟是什么意思？

• 你选择一个外形
• 你为每个外部位置选择一个内部形状
• 然后,复合位置是一对外部位置和一个适合于位于那里的内部形状的内部位置

或者,在汉考克

• 你选择一个外部命令
• 在选择内部命令之前,您可以等待查看外部响应
• 然后,复合响应是对外部命令的响应,然后是对策略选择的内部命令的响应

或者,更加公然

• 当您创建列表列表时,内部列表可以具有不同的长度

所述join的Monad变平的组合物.潜伏在它背后不仅仅是形状上的幺半群,而是一个整合算子.那是,

join :: ((s <| p) . (s <| p)) x -> (s <| p) x

要求

integrate :: (s <| p) s -> s

您的免费monad为您提供策略树,您可以使用一个命令的结果来选择策略的其余部分.好像你正在使用20世纪70年代的电传打字机进行交互.

与此同时...

张量

两个容器的张量(也由于汉考克)给出了

(s <| p) >< (s' <| p')  =  (s, s') <| \ (a, b) -> (p a, p' b)

那是

• 你选择两种形状
• 然后,一个位置是一对位置,每个位置一个

要么

• 你选择了两个命令,没有看到任何响应
• 然后是一对响应

要么

• [] >< []是矩形矩阵的类型:"内部"列表必须都具有相同的长度

后者是一个线索,为什么><很难在Haskell中获取,但在依赖类型设置中很容易.

与组合一样,张量是一个幺半群,其身份函子是其中性元素.如果我们用Monad张量替换基础组合,我们得到了什么？

pure :: Id x -> (s <| p) x
mystery :: ((s <| p) >< (s <| p)) x -> (s <| p) x

但无论如何mystery呢？这不是一个谜,因为我们知道在容器之间制作多态函数是一种相当严格的方法.必须有

f :: (s, s) -> s
g :: pi ((a, b) :: (s, s)) -> p (f (a, b)) -> (p a, p b)

这些正是我们<*>之前所说的.

Applicative是由张量生成的有效编程的概念,其中由张量Monad生成.您没有/需要等待外部响应来选择内部命令的事实是Applicative程序更容易并行化的原因.

眼看[] >< []矩形矩阵告诉我们为什么<*>对表是建立在乘法的顶部.

免费的applicative functor是带有旋钮的免费monoid.对于容器,

Free (s <| p) = [s] <| All p

哪里

All p [] = ()
All p (x : xs) = (p x, All p xs)

所以"命令"是一个很大的命令列表,就像一副穿孔卡片.在选择卡片组之前,您无法看到任何输出."响应"是您的lineprinter输出.这是20世纪60年代.

你去吧 Applicative张量而不是构成的本质要求潜在的幺半群,以及与幺半群相容的元素的重组.

Answer 3

我想用s中发现的更多 s 示例来补充 Conor McBride（猪工）的指导性答案。\n据观察，某些函子的实例类似于相应的实例；\n例如，我们有以下类比:MonoidApplicativeApplicativeMonoid

\n\n

Applicative \xe2\x86\x92 Monoid\n---------------------\nList        \xe2\x86\x92 Product\nMaybe       \xe2\x86\x92 All\nEither a    \xe2\x86\x92 First a\nState s     \xe2\x86\x92 Endo s\n

\n\n

根据康纳的评论，我们可以理解为什么我们有这些对应关系。\n我们使用以下观察结果：

\n\n

\n
1. 容器的形状在应用操作下Applicative形成。Monoid<*>
\n
2. 函子的形状F由下式给出F 1（其中1表示单位()。
\n

\n\n

对于上面列出的每个Applicative函子，我们通过使用单位元素实例化函子来计算它们的形状。\n我们得到...

\n\n

List其形状为Nat：

\n\n

List a = \xce\xbc r . 1 + a \xc3\x97 r\nList 1 = \xce\xbc r . 1 + 1 \xc3\x97 r\n       \xe2\x89\x85 \xce\xbc r . 1 + r\n       \xe2\x89\x85 Nat\n

\n\n

Maybe其形状为Bool：

\n\n

Maybe a = 1 + a\nMaybe 1 = 1 + 1\n        \xe2\x89\x85 Bool\n

\n\n

Either其形状为Maybe：

\n\n

Either a b = a + b\nEither a 1 = a + 1\n           \xe2\x89\x85 Maybe a\n

\n\n

State其形状为Endo：

\n\n

State s a = (a \xc3\x97 s) ^ s\nState s 1 = (1 \xc3\x97 s) ^ s\n          \xe2\x89\x85 s ^ s\n          \xe2\x89\x85 Endo s\n

\n\n\n\n

形状的类型Monoid与开头列出的 s 底层的类型完全匹配。\n有一件事仍然让我困惑：其中一些类型允许多个Monoid实例（例如，Bool可以制成MonoidasAll或Any），但我不完全确定为什么我们得到其中一个实例而不是另一个。我的猜测是，这与应用定律以及它们如何与容器 \xe2\x80\x93 其位置的其他组件交互有关。

\n