首先,让我为每个问题提供简短的答案。然后,我会将每个答案扩展为更长的详细答案,但这些简短的答案有望帮助导航这些答案。
不,Alternative
也Monoid
没有不同的意思;适用于同时具有 of和 ofAlternative
结构的类型。“挑选”和“组合”是同一个更广泛概念的两种不同直觉。Applicative
Monoid
Alternative
包含empty
以及<|>
因为设计师认为这将是有用的,并且因为这会产生一个幺半群。在挑选方面,empty
对应于做出不可能的选择。
我们两者都需要Alternative
,Monoid
因为前者比后者遵守(或应该)更多的法律;这些定律与类型构造函数的单曲面和应用结构有关。另外,Alternative
cannot 依赖于内部类型,whileMonoid
可以。
MonadPlus
略强于Alternative
,因为它必须遵守更多的规律;除了应用结构之外,这些定律还将单曲面结构与一元结构联系起来。如果你有这两者的实例,它们应该是一致的。
不是Alternative
意味着完全不同的东西Monoid
吗?
并不真地!您感到困惑的部分原因是 HaskellMonoid
类使用了一些非常糟糕(嗯,不够通用)的名称。这就是数学家定义幺半群的方式(非常明确):
定义。一个幺半群是一个集合M配备了一个可区分的元素ε ∈ M和一个二元算子 · : M × M → M,用并列表示,这样以下两个条件成立:
- ε是恒等式:对于所有m ∈ M,m ε = ε m = m。
- · 是关联的:对于所有m ₁, m ₂, m ₃ ∈ M , ( m ₁<em>m₂) m ₃ = m ₁( m ₂<em>m₃)。
就是这样。在 Haskell 中,ε 是拼写的mempty
,而 · 是拼写的mappend
(或者,现在是<>
),而集合M是中的类型M
。instance Monoid M where ...
查看这个定义,我们看到它没有提到“组合”(或“挑选”)。它说了关于 · 和关于ε的事情,但仅此而已。现在,将事物与这种结构结合起来确实很有效:ε对应于没有事物,而m ₁<em>m₂ 表示如果我将m ₁ 和m ₂ 的东西放在一起,我可以得到一个包含所有它们的新事物东西。但这里有另一种直觉:ε对应于根本没有选择,m ₁<em>m₂ 对应于m ₁ 和m ₂ 之间的选择。这就是“挑选”的直觉。请注意,两者都遵守幺半群定律:
- 一无所有和别无选择都是身份。
- 如果我没有东西并将它与一些东西混合在一起,我最终会再次得到同样的东西。
- 如果我在没有选择(不可能的事情)和其他选择之间做出选择,我必须选择其他(可能的)选择。
- 将收藏集中在一起并做出选择都是关联的。
- 如果我有三个集合,我将前两个放在一起然后第三个,或者最后两个放在一起然后第一个都没关系。无论哪种方式,我最终都会得到相同的整体系列。
- 如果我可以在三件事之间进行选择,那么我是否(a)首先在第一或第二和第三之间进行选择,然后,如果需要,在第一和第二之间进行选择,或者(b)首先在第一和第二之间进行选择并不重要和第二或第三,然后,如果我需要,在第二和第三之间。无论哪种方式,我都可以选择我想要的。
(注意:我在这里玩得又快又松;这就是为什么它是直觉。例如,重要的是要记住 · 不必是可交换的,上面掩盖了这一点:完全有可能m ₁<em>m₂ ≠ m ₂ <em>m₁.)
看哪:这两种事情(以及许多其他事情——乘以数字真的是“组合”还是“挑选”?)都遵循相同的规则。拥有直觉对于发展理解很重要,但决定实际情况的是规则和定义。
最好的部分是这两种直觉可以由同一个载体来解释!令M为包含空集的某个集合(不是所有集合的集合!),令ε为空集 ∅,令 · 为并集 ∪。很容易看出 ∅ 是 ∪ 的恒等式,并且 ∪ 是关联的,因此我们可以得出 ( M ,∅,∪) 是幺半群的结论。现在:
- 如果我们将集合视为事物的集合,那么 ∪ 对应于将它们聚集在一起以获得更多事物——“组合”直觉。
- 如果我们认为集合代表可能的动作,那么 ∪ 对应于增加可供选择的可能动作池——“选择”直觉。
这正是[]
Haskell 中正在发生的事情:[a]
是 a Monoid
for all a
,并且[]
作为应用函子(和 monad)用于表示不确定性。组合直觉和挑选直觉都在同一类型上重合:mempty = empty = []
和mappend = (<|>) = (++)
。
因此,Alternative
该类只是用来表示对象,这些对象 (a) 是应用函子,并且 (b) 当以一种类型实例化时,它们具有遵循某些规则的值和二进制函数。有哪些规则?幺半群规则。为什么?因为事实证明它很有用:-)
为什么Alternative
需要一个空的方法/成员?
好吧,刻薄的答案是“因为Alternative
代表一个幺半群结构”。但真正的问题是:为什么是幺半群结构?为什么不只是一个半群,一个没有ε的幺半群?一个答案是声称幺半群更有用。我认为很多人(但也许不是Edward Kmett)会同意这一点;几乎所有时间,如果你有一个明智的(<|>)
/ mappend
/·,你就可以定义一个明智的empty
/ mempty
/ ε。另一方面,具有额外的通用性很好,因为它可以让你在伞下放置更多的东西。
您还想知道这如何与“挑选”直觉相结合。请记住,在某种意义上,正确的答案是“知道何时放弃'挑选'直觉”,我认为您可以将两者统一起来。考虑[]
,非确定性的应用函子。如果我将两个类型的值[a]
与结合起来(<|>)
,则对应于不确定地选择左侧的动作或右侧的动作。但有时,您将无法在一侧采取任何行动——这很好。同样,如果我们考虑解析器,(<|>)
表示一个解析器,它解析左边的内容或右边的内容(它“挑选”)。如果你有一个总是失败的解析器,那最终就是一个身份:如果你选择它,你会立即拒绝那个选择并尝试另一个。
所有这一切,请记住,完全有可能拥有一个几乎类似的类Alternative
,但缺少empty
. 那将是完全有效的——它甚至可以是一个超类Alternative
——但碰巧不是 Haskell 所做的。大概这是出于对有用的猜测。
为什么Alternative
类型类需要一个Applicative
约束,为什么它需要一种* -> *
?... 为什么不只是 [使用] liftA2 mappend
?
好吧,让我们考虑这三个提议的更改中的每一个:摆脱对;的Applicative
约束。Alternative
改变Alternative
' 的论点的种类;并使用liftA2 mappend
代替<|>
和pure mempty
代替empty
。我们将首先查看第三个更改,因为它是最不同的。假设我们完全摆脱了Alternative
这个类,并用两个简单的函数替换了这个类:
fempty :: (Applicative f, Monoid a) => f a
fempty = pure mempty
(>|<) :: (Applicative f, Monoid a) => f a -> f a -> f a
(>|<) = liftA2 mappend
我们甚至可以保留 和 的some
定义many
。这确实给了我们一个幺半群结构,这是真的。但它似乎给了我们错误的一个。应该Just fst >|< Just snd
失败,因为(a,a) -> a
不是Monoid
? 不,但这就是上面代码的结果。我们想要的幺半群实例是一个与内部类型无关的实例(借用Matthew Farkas-Dyck在一个非常相关的 haskell-cafe 讨论中的术语,该讨论提出了一些非常相似的问题);该Alternative
结构是关于由f
' 结构确定的幺半群,而不是f
' 参数的结构。
现在我们认为我们想Alternative
作为某种类型类离开,让我们看看两种建议的改变它的方法。如果我们改变种类,我们必须摆脱Applicative
约束;Applicative
只讲善事* -> *
,所以没有办法提及。这留下了两个可能的变化;第一个更小的变化是摆脱Applicative
约束,但不理会这种约束:
class Alternative' f where
empty' :: f a
(<||>) :: f a -> f a -> f a
另一个更大的变化是摆脱Applicative
约束并改变种类:
class Alternative'' a where
empty'' :: a
(<|||>) :: a -> a -> a
在这两种情况下,我们都必须摆脱some
/ many
,但这没关系;(Applicative f, Alternative' f) => f a -> f [a]
我们可以将它们定义为类型为或的独立函数(Applicative f, Alternative'' (f [a])) => f a -> f [a]
。
Monoid
现在,在第二种情况下,我们更改类型变量的种类,我们看到我们的类与(或者,如果您仍想删除empty''
, )完全相同Semigroup
,因此拥有一个单独的类没有任何优势。事实上,即使我们不理会 kind 变量但移除Applicative
约束,也会Alternative
变成forall a. Monoid (f a)
,尽管我们无法在 Haskell 中编写这些量化的约束,即使使用所有花哨的 GHC 扩展也不行。(注意,这表达了上面提到的内在类型不可知论。)因此,如果我们可以做出这些改变中的任何一个,那么我们就没有理由保留Alternative
(除了能够表达那个量化的约束,但这似乎很难令人信服) .
所以问题归结为“Alternative
部件和作为两者的实例的部件之间是否存在关系?Applicative
” f
虽然文档中没有任何内容,但我要表明立场并说是的——或者至少,应该有。我认为这Alternative
应该遵守一些与Applicative
(除了幺半群定律之外)相关的定律;特别是,我认为这些法律类似于
- (的)右分配
<*>
: (f <|> g) <*> a = (f <*> a) <|> (g <*> a)
- 右吸收(对于
<*>
): empty <*> a = empty
- 左分布(的
fmap
): f <$> (a <|> b) = (f <$> a) <|> (f <$> b)
- 左吸收(对于
fmap
): f <$> empty = empty
[]
这些定律对于and Maybe
, and (假装它的MonadPlus
实例是一个Alternative
实例)似乎是正确的IO
,但我没有做过任何证明或详尽的测试。(例如,我最初认为左分配性适用于<*>
,但这对 的“执行效果”顺序错误[]
。)但是,通过类比,确实MonadPlus
期望遵守类似的定律(尽管显然有一些含糊不清)。我原本想主张第三定律,这似乎很自然:
- 左吸收(对于
<*>
): a <*> empty = empty
然而,尽管我相信[]
并Maybe
遵守这条法律,但我IO
并不相信,而且我认为(原因将在接下来的几段中显而易见)最好不要要求它。
事实上,Edward Kmett 似乎有一些幻灯片,他支持类似的观点。为此,我们需要简短地题外话,涉及一些更多的数学术语。最后一张幻灯片,“我想要更多的结构”,说“一个 Monoid 是一个 Applicative,就像一个正确的 Seminearring 是一个 Alternative”,“如果你扔掉 Applicative 的论点,你会得到一个 Monoid,如果你扔摆脱 Alternative 的论点,您将获得 RightSemiNearRing。”</p>
正确的半婚宴?“正确的半婚宴是如何参与其中的?” 我听到你哭了。 好,
定义。右半半圆(也是右半圆,但前者似乎在 Google 上使用得更多)是四元组 ( R , +,·,0) 其中 ( R ,+,0) 是幺半群, ( R ,·)是一个半群,并且以下两个条件成立:
- · 在 + 上是右分配的:对于所有r , s , t ∈ R , ( s + t ) r = sr + tr。
- 0 是右吸收的 ·:对于所有r ∈ R,0 r = 0。
类似地定义左近半球。
现在,这不太适用,因为<*>
它不是真正的关联运算符或二元运算符——类型不匹配。我认为这就是 Edward Kmett 在谈到“抛弃争论”时所要表达的意思。另一种选择可能是说(我不确定这是否正确)我们实际上希望 ( f a
, <|>
, <*>
, empty
) 形成一个右半环体,其中“-oid”后缀表示二元运算符只能应用于特定的元素对(à la groupoids)。而且我们还想说 ( f a
, <|>
, <$>
, empty
) 是一个左近半环体,尽管可以想象这可以从Applicative
规律和正确的近半环状结构。但现在我已经进入了我的脑海,这无论如何都不是很重要。
无论如何,这些定律比幺半群定律更强大,意味着完全有效的Monoid
实例将变为无效Alternative
实例。标准库中有(至少)两个这样的例子:Monoid a => (a,)
和Maybe
. 让我们快速看一下它们中的每一个。
给定任意两个幺半群,它们的乘积是一个幺半群;因此,元组可以以Monoid
明显的方式作为一个实例(重新格式化基本包的源):
instance (Monoid a, Monoid b) => Monoid (a,b) where
mempty = (mempty, mempty)
(a1,b1) `mappend` (a2,b2) = (a1 `mappend` a2, b1 `mappend` b2)
Applicative
类似地,我们可以通过累积 monoid 元素(重新格式化基本包的 source )将其第一个组件是一个 monoid 元素的元组变成一个实例:
instance Monoid a => Applicative ((,) a) where
pure x = (mempty, x)
(u, f) <*> (v, x) = (u `mappend` v, f x)
然而,元组不是 的一个实例Alternative
,因为它们不可能——Monoid a => (a,b)
所有类型都存在over 的幺半群结构b
,并且Alternative
的幺半群结构必须是内部类型不可知的。不仅必须b
是 monad,为了能够表达(f <> g) <*> a
,我们需要使用Monoid
函数的实例,它是形式的函数Monoid b => a -> b
。即使在我们拥有所有必要的单曲面结构的情况下,它也违反了所有四个Alternative
定律。要看到这一点, letssf n = (Sum n, (<> Sum n))
和 let ssn = (Sum n, Sum n)
。然后,写(<>)
for mappend
,我们得到以下结果(可以在 GHCi 中检查,偶尔使用类型注释):
- 正确分配:
(ssf 1 <> ssf 1) <*> ssn 1 = (Sum 3, Sum 4)
(ssf 1 <*> ssn 1) <> (ssf 1 <*> ssn 1) = (Sum 4, Sum 4)
- 正确的吸收:
mempty <*> ssn 1 = (Sum 1, Sum 0)
mempty = (Sum 0, Sum 0)
- 左分布:
(<> Sum 1) <$> (ssn 1 <> ssn 1) = (Sum 2, Sum 3)
((<> Sum 1) <$> ssn 1) <> ((<> Sum 1) <$> ssn 1) = (Sum 2, Sum 4)
- 左吸收:
(<> Sum 1) <$> mempty = (Sum 0, Sum 1)
mempty = (Sum 1, Sum 1)
接下来,考虑Maybe
。就目前而言,Maybe
'Monoid
和Alternative
实例不同意。(虽然我在本节开头提到的 haskell-cafe 讨论建议改变这一点,但semigroups 包中有一个Option
新类型会产生相同的效果。)因为基础包没有半群类,它只是提升了幺半群,所以我们得到(重新格式化基础包的源):Monoid
Maybe
Nothing
instance Monoid a => Monoid (Maybe a) where
mempty = Nothing
Nothing `mappend` m = m
m `mappend` Nothing = m
Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)
另一方面,作为Alternative
,Maybe
代表失败的优先选择,因此我们得到(再次重新格式化基本包的 source):
instance Alternative Maybe where
empty = Nothing
Nothing <|> r = r
l <|> _ = l
事实证明,只有后者符合Alternative
法律。该Monoid
实例的失败不如(,)
's; 它确实遵守关于 的定律<*>
,尽管几乎是偶然的——它来自Monoid
for 函数的唯一实例的行为,它(如上所述)将返回幺半群的函数提升到读者应用函子中。如果你解决它(这都是非常机械的),你会发现所有的右分配和右吸收<*>
都适用于Alternative
和Monoid
实例,左吸收也适用于fmap
。对于该实例,左分布fmap
确实成立Alternative
,如下所示:
f <$> (Nothing <|> b)
= f <$> b by the definition of (<|>)
= Nothing <|> (f <$> b) by the definition of (<|>)
= (f <$> Nothing) <|> (f <$> b) by the definition of (<$>)
f <$> (Just a <|> b)
= f <$> Just a by the definition of (<|>)
= Just (f a) by the definition of (<$>)
= Just (f a) <|> (f <$> b) by the definition of (<|>)
= (f <$> Just a) <|> (f <$> b) by the definition of (<$>)
但是,Monoid
实例失败;(<>)
为写作mappend
,我们有:
(<> Sum 1) <$> (Just (Sum 0) <> Just (Sum 0)) = Just (Sum 1)
((<> Sum 1) <$> Just (Sum 0)) <> ((<> Sum 1) <$> Just (Sum 0)) = Just (Sum 2)
现在,这个例子有一个警告。如果您只要求Alternative
s 与 s 兼容<*>
,而不是与s 兼容<$>
,那么Maybe
很好。上面提到的 Edward Kmett 的幻灯片没有提及<$>
,但我认为要求有关它的法律似乎也是合理的;尽管如此,我找不到任何支持我的东西。
因此,我们可以得出结论,作为Alternative
a 的要求比作为 a的Monoid
要求更高,因此它需要不同的类。最纯粹的例子是具有内部类型不可知Monoid
实例的类型和Applicative
彼此不兼容的实例;但是,基本包中没有任何此类类型,我想不出任何类型。(可能不存在,尽管我会感到惊讶。)然而,这些内部类型的诺斯替示例说明了为什么两个类型类必须不同。
MonadPlus
类型类的意义何在?
MonadPlus
, like Alternative
, 是加强的Monoid
,但相对于Monad
而不是Applicative
。根据 Edward Kmett 在他对“类型类,和?之间的区别MonadPlus
Alternative
Monoid
MonadPlus
Alternative
empty <*> a
empty >>= f
”问题的回答中,也比强:例如,法律并不暗示这一点。 AndrewC提供了两个例子:Maybe
和它的对偶。由于存在两套潜在的法律,MonadPlus
这一事实使问题变得复杂。普遍认为MonadPlus
应该与mplus
和形成一个幺半群,mempty
并且应该满足左零定律,mempty >>= f = mempty
. 然而,一些MonadPlus
ses 满足左分布, mplus a b >>= f = mplus (a >>= f) (b >>= f)
; 和其他人满足左接,mplus (return a) b = return a
。(请注意,左零/分布MonadPlus
类似于Alternative
;的右分布/吸收比(<*>)
更类似于。)左分布可能“更好”,因此任何满足左捕获的实例,例如,都是但不是第一种的。由于 left catch 依赖于排序,你可以想象一个 newtype 包装器,它的实例是右偏而不是左偏的:(=<<)
(>>=)
MonadPlus
Maybe
Alternative
MonadPlus
Maybe
Alternative
a <|> Just b = Just b
. 这既不满足左分布也不满足左捕获,但将是一个完全有效的Alternative
.
但是,由于任何类型a都MonadPlus
应该使其实例与其实例重合(我相信这与它是s 的 sAlternative
所要求的ap
和(<*>)
相等的方式相同),您可以想象将类定义为Monad
Applicative
MonadPlus
class (Monad m, Alternative m) => MonadPlus' m
该类不需要声明新函数;这只是对给定类型所遵守empty
的法律的承诺。(<|>)
这种设计技术没有在 Haskell 标准库中使用,但在一些更具有数学头脑的包中用于类似目的;例如,lattices包使用它来表达一个lattice只是通过吸收定律链接的相同类型的连接半格和相遇半格的想法。
Alternative
即使您想保证Alternative
并且Monoid
始终重合,您也不能这样做的原因是种类不匹配。所需的类声明将具有以下形式
class (Applicative f, forall a. Monoid (f a)) => Alternative''' f
但是(如上所述)甚至 GHC Haskell 都不支持量化约束。
另外,请注意,拥有Alternative
as 的超类MonadPlus
需要Applicative
成为 的超类Monad
,所以祝你好运。如果你遇到这个问题,总会有WrappedMonad
newtype,它以明显的方式将 anyMonad
变成 an Applicative
;有一个instance MonadPlus m => Alternative (WrappedMonad m) where ...
正是你所期望的。