也许你要找的是这个幺半群。
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 ()
也是一个Monoid
。这就是潜在在Applicative f
后面潜藏的Monoid
。
我们本可以坚持要将Monoid(f())
作为Applicative
的超类,但那样会使事情变得混乱。
> mappend (AppM [(),()]) (AppM [(),(),()])
AppM [(),(),(),(),(),()]
Applicative []
的底层单子结构是自然数的
乘法,而列表的“显而易见”的单子结构是连接,它专门用于自然数的
加法。
为了理解发生了什么,可以考虑那些在 Abbott、Altenkirch 和 Ghani 的依赖类型意义下恰好是
容器的 Applicatives。我们很快就能在 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
个值。也就是说,列表的形状是它的 长度,这告诉你需要多少元素来填充列表。
你可以通过取 f ()
来查找 Haskell Functor f
的形状。通过使数据变得微不足道,位置就不重要了。在 Haskell 中通用地构建位置的 GADT 实际上更加困难。
参数性告诉我们,容器之间的多态函数是
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)
(私下里,我们这些接受了基本Hancock培训的人也认为“形状”就是“命令”,“位置”就是“有效响应”。那么,容器之间的同态就恰好是“设备驱动程序”。但我离题了。)
沿着类似的思路,使一个容器成为Applicative
需要什么?首先,
pure :: x -> (s <| p) x
这等同于
pure :: (() <| Const ()) x -> (s <| p) x
必须由此提供
f :: () -> s
g :: pi (a :: ()) -> p (f ()) -> Const () a
其中f = const neutral
对一些内容保持不变。
neutral :: s
现在,关于什么呢?
(<*>) :: (s <| p) (x -> y) -> (s <| p) x -> (s <| p) y
再次强调,参数化告诉我们两件事。首先,计算输出形状的唯一有用数据是两个输入形状。我们必须有一个函数
outShape :: s -> s -> s
其次,我们唯一的方法将输出位置填充为 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
这究竟是什么意思?
- 您选择外部形状
- 您为每个外部位置选择内部形状
- 复合位置是一个外部位置和一个适合于该位置的内部形状的组合
或者,用汉考克语说:
- 您选择外部命令
- 在选择内部命令之前,您可以等待看到外部响应
- 复合响应是对外部命令的响应,后跟由您的策略选择的内部命令的响应
或者更直白地说:
Monad
的join
将组合展开。它背后潜藏着的不仅是形状上的单子,还有一个积分运算符。
join :: ((s <| p) . (s <| p)) x -> (s <| p) x
需要的
integrate :: (s <| p) s -> s
使用自由单子可以得到策略树,您可以使用一个命令的结果来选择剩余的策略,就好像您正在与1970年代的电传打字机进行交互。
同时...
张量
两个容器的张量(也是由汉考克提出的)由以下公式给出:
(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
程序更容易并行化的原因。
将 [] >< []
视为矩形矩阵可以告诉我们为什么列表的 <*>
是建立在乘法基础之上的。
自由应用函子是带旋钮的自由幺半群。对于容器来说,
Free (s <| p) = [s] <| All p
在哪里
All p [] = ()
All p (x : xs) = (p x, All p xs)
因此,“命令”是一长串命令,就像 punch 卡片的一叠牌,您在选择卡片堆之前不会看到任何输出。 "响应" 是您的行式打印机输出。这是上世纪六十年代。
所以,这就是了。 应用程序(Applicative)的本质是张量而不是组合,需要一个底层的幺半群,以及与幺半群兼容的元素重新组合。
f
的类型不正确,无法成为Monoid
。 - Lee*
种类的东西,正如 Lee 所暗示的那样)。 - duplodeApplicative
实例声明中,即instance Monoid a => Applicative ((,) a)
;而该实例声明中的Monoid
约束与Applicative
作为概念中的"monoidal-functor-ness"没有关系。 - Daniel Wagner