75

我一直在浏览Typeclassopedia来学习类型类。我被困在理解中Alternative(并且MonadPlus,就此而言)。

我遇到的问题:

  • 'pedia 说“Alternative 类型类适用于也具有幺半群结构的 Applicative 函子。” 我不明白——Alternative 不是意味着与 Monoid 完全不同的东西吗?即,我将 Alternative 类型类的要点理解为在两件事之间进行选择,而我将 Monoids 理解为关于组合事物。

  • 为什么 Alternative 需要empty方法/成员?我可能是错的,但它似乎根本没有被使用......至少在我能找到的代码中。而且这似乎不符合课堂的主题——如果我有两件事,并且需要选择一个,我需要一个“空”做什么?

  • 为什么 Alternative 类型类需要一个 Applicative 约束,为什么它需要一种* -> *?为什么不只是有<|> :: a -> a -> a?所有实例仍然可以以相同的方式实现......我认为(不确定)。它提供了 Monoid 没有的什么价值?

  • MonadPlus类型类的意义何在?我不能通过同时使用 aMonad和来解锁它的所有优点Alternative吗?为什么不直接放弃呢?(我确定我错了,但我没有任何反例)

希望所有这些问题都是连贯的......!


赏金更新:@Antal 的回答是一个很好的开始,但 Q3 仍然开放:Alternative 提供了 Monoid 没有提供的什么?我觉得这个答案不能令人满意,因为它缺乏具体的例子,以及关于 Alternative 的更高善意如何将其与 Monoid 区分开来的具体讨论。

如果要将 applicative 的效果与 Monoid 的行为结合起来,为什么不只是:

liftA2 mappend

这对我来说更令人困惑,因为许多 Monoid 实例与 Alternative 实例完全相同。

这就是为什么我要寻找具体的例子来说明为什么 Alternative 是必要的,以及它与 Monoid 有何不同——或意味着不同的东西。

4

5 回答 5

92

首先,让我为每个问题提供简短的答案。然后,我会将每个答案扩展为更长的详细答案,但这些简短的答案有望帮助导航这些答案。

  1. 不,AlternativeMonoid没有不同的意思;适用于同时具有 of和 ofAlternative结构的类型。“挑选”和“组合”是同一个更广泛概念的两种不同直觉。ApplicativeMonoid

  2. Alternative包含empty以及<|>因为设计师认为这将是有用的,并且因为这会产生一个幺半群。在挑选方面,empty对应于做出不可能的选择。

  3. 我们两者都需要AlternativeMonoid因为前者比后者遵守(或应该)更多的法律;这些定律与类型构造函数的单曲面和应用结构有关。另外,Alternativecannot 依赖于内部类型,whileMonoid可以。

  4. MonadPlus略强于Alternative,因为它必须遵守更多的规律;除了应用结构之外,这些定律还将单曲面结构与一元结构联系起来。如果你有这两者的实例,它们应该是一致的。


不是Alternative意味着完全不同的东西Monoid吗?

并不真地!您感到困惑的部分原因是 HaskellMonoid类使用了一些非常糟糕(嗯,不够通用)的名称。这就是数学家定义幺​​半群的方式(非常明确):

定义。一个幺半群是一个集合M配备了一个可区分的元素εM和一个二元算子 · : M × MM,用并列表示,这样以下两个条件成立:

  1. ε是恒等式:对于所有mMm ε = ε m = m
  2. · 是关联的:对于所有m ₁, m ₂, m ₃ ∈ M , ( m ₁<em>m₂) m ₃ = m ₁( m ₂<em>m₃)。

就是这样。在 Haskell 中,ε 是拼写的mempty,而 · 是拼写的mappend(或者,现在是<>),而集合M是中的类型Minstance Monoid M where ...

查看这个定义,我们看到它没有提到“组合”(或“挑选”)。它说了关于 · 和关于ε的事情,但仅此而已。现在,将事物与这种结构结合起来确实很有效:ε对应于没有事物,而m ₁<em>m₂ 表示如果我将m ₁ 和m ₂ 的东西放在一起,我可以得到一个包含所有它们的新事物东西。但这里有另一种直觉:ε对应于根本没有选择,m ₁<em>m₂ 对应于m ₁ 和m ₂ 之间的选择。这就是“挑选”的直觉。请注意,两者都遵守幺半群定律:

  1. 一无所有和别无选择都是身份。
    • 如果我没有东西并将它与一些东西混合在一起,我最终会再次得到同样的东西。
    • 如果我在没有选择(不可能的事情)和其他选择之间做出选择,我必须选择其他(可能的)选择。
  2. 将收藏集中在一起并做出选择都是关联的。
    • 如果我有三个集合,我将前两个放在一起然后第三个,或者最后两个放在一起然后第一个都没关系。无论哪种方式,我最终都会得到相同的整体系列。
    • 如果我可以在三件事之间进行选择,那么我是否(a)首先在第一或第二和第三之间进行选择,然后,如果需要,在第一和第二之间进行选择,或者(b)首先在第一和第二之间进行选择并不重要和第二或第三,然后,如果我需要,在第二和第三之间。无论哪种方式,我都可以选择我想要的。

(注意:我在这里玩得又快又松;这就是为什么它是直觉。例如,重要的是要记住 · 不必是可交换的,上面掩盖了这一点:完全有可能m ₁<em>m₂ ≠ m ₂ <em>m₁.)

看哪:这两种事情(以及许多其他事情——乘以数字真的是“组合”还是“挑选”?)都遵循相同的规则。拥有直觉对于发展理解很重要,但决定实际情况的是规则和定义。

最好的部分是这两种直觉可以由同一个载体来解释!令M为包含空集的某个集合(不是所有集合的集合!),令ε为空集 ∅,令 · 为并集 ∪。很容易看出 ∅ 是 ∪ 的恒等式,并且 ∪ 是关联的,因此我们可以得出 ( M ,∅,∪) 是幺半群的结论。现在:

  1. 如果我们将集合视为事物的集合,那么 ∪ 对应于将它们聚集在一起以获得更多事物——“组合”直觉。
  2. 如果我们认为集合代表可能的动作,那么 ∪ 对应于增加可供选择的可能动作池——“选择”直觉。

这正是[]Haskell 中正在发生的事情:[a]是 a Monoidfor 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部件和作为两者的实例的部件之间是否存在关系?Applicativef虽然文档中没有任何内容,但我要表明立场并说的——或者至少,应该有。我认为这Alternative应该遵守一些与Applicative(除了幺半群定律之外)相关的定律;特别是,我认为这些法律类似于

  1. (的)右分配<*>  (f <|> g) <*> a = (f <*> a) <|> (g <*> a)
  2. 右吸收(对于<*>):  empty <*> a = empty
  3. 左分布(的fmap):  f <$> (a <|> b) = (f <$> a) <|> (f <$> b)
  4. 左吸收(对于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 ,·)是一个半群,并且以下两个条件成立:

  1. · 在 + 上是右分配的:对于所有r , s , tR , ( s + t ) r = sr + tr
  2. 0 是右吸收的 ·:对于所有rR,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 中检查,偶尔使用类型注释):

  1. 正确分配:
    • (ssf 1 <> ssf 1) <*> ssn 1 = (Sum 3, Sum 4)
    • (ssf 1 <*> ssn 1) <> (ssf 1 <*> ssn 1) = (Sum 4, Sum 4)
  2. 正确的吸收:
    • mempty <*> ssn 1 = (Sum 1, Sum 0)
    • mempty = (Sum 0, Sum 0)
  3. 左分布:
    • (<> Sum 1) <$> (ssn 1 <> ssn 1) = (Sum 2, Sum 3)
    • ((<> Sum 1) <$> ssn 1) <> ((<> Sum 1) <$> ssn 1) = (Sum 2, Sum 4)
  4. 左吸收:
    • (<> Sum 1) <$> mempty = (Sum 0, Sum 1)
    • mempty = (Sum 1, Sum 1)

接下来,考虑Maybe。就目前而言,Maybe'MonoidAlternative实例不同意。(虽然我在本节开头提到的 haskell-cafe 讨论建议改变这一点,但semigroups 包中有一个Option新类型会产生相同的效果。)因为基础包没有半群类,它只是提升了幺半群,所以我们得到(重新格式化基础包的源):MonoidMaybeNothing

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; 它确实遵守关于 的定律<*>,尽管几乎是偶然的——它来自Monoidfor 函数的唯一实例的行为,它(如上所述)将返回幺半群的函数提升到读者应用函子中。如果你解决它(这都是非常机械的),你会发现所有的右分配和右吸收<*>都适用于AlternativeMonoid实例,左吸收也适用于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)

现在,这个例子有一个警告。如果您只要求Alternatives 与 s 兼容<*>,而不是与s 兼容<$>,那么Maybe很好。上面提到的 Edward Kmett 的幻灯片没有提及<$>,但我认为要求有关它的法律似乎也是合理的;尽管如此,我找不到任何支持我的东西。

因此,我们可以得出结论,作为Alternativea 的要求比作为 aMonoid要求更高,因此它需要不同的类。最纯粹的例子是具有内部类型不可知Monoid实例的类型和Applicative彼此不兼容的实例;但是,基本包中没有任何此类类型,我想不出任何类型。(可能不存在,尽管我会感到惊讶。)然而,这些内部类型的诺斯替示例说明了为什么两个类型类必须不同。


MonadPlus类型类的意义何在?

MonadPlus, like Alternative, 是加强的Monoid,但相对于Monad而不是Applicative。根据 Edward Kmett 在他对“类型类,?之间的区别MonadPlusAlternativeMonoidMonadPlusAlternativeempty <*> aempty >>= f”问题的回答中,也例如,法律并不暗示这一点AndrewC提供了两个例子:Maybe和它的对偶。由于存在两套潜在的法律,MonadPlus这一事实使问题变得复杂。普遍认为MonadPlus应该与mplus和形成一个幺半群,mempty并且应该满足左零定律,mempty >>= f = mempty. 然而,一些MonadPlusses 满足左分布, mplus a b >>= f = mplus (a >>= f) (b >>= f); 和其他人满足左接mplus (return a) b = return a。(请注意,左零/分布MonadPlus类似于Alternative;的右分布/吸收比(<*>)更类似于。)左分布可能“更好”,因此任何满足左捕获的实例,例如,都是但不是第一种的。由于 left catch 依赖于排序,你可以想象一个 newtype 包装器,它的实例是偏而不是偏的:(=<<)(>>=)MonadPlusMaybeAlternativeMonadPlusMaybeAlternativea <|> Just b = Just b. 这既不满足左分布也不满足左捕获,但将是一个完全有效的Alternative.

但是,由于任何类型aMonadPlus应该使其实例与其实例重合(我相信这与它是s 的 sAlternative所要求的ap(<*>)相等的方式相同),您可以想象将类定义为MonadApplicativeMonadPlus

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 都不支持量化约束。

另外,请注意,拥有Alternativeas 的超类MonadPlus需要Applicative成为 的超类Monad,所以祝你好运。如果你遇到这个问题,总会有WrappedMonadnewtype,它以明显的方式将 anyMonad变成 an Applicative;有一个instance MonadPlus m => Alternative (WrappedMonad m) where ...正是你所期望的。

于 2012-10-26T06:03:23.973 回答
20
import Data.Monoid
import Control.Applicative

让我们通过一个示例来追溯 Monoid 和 Alternative 如何与Maybe函子和ZipList函子交互,但让我们从头开始,部分是为了让所有定义在我们的脑海中保持新鲜,部分是为了停止一直切换标签到一些hackage,但是主要是这样我就可以运行过去的 ghci来纠正我的错字!

(<>) :: Monoid a => a -> a -> a
(<>) = mappend -- I'll be using <> freely instead of `mappend`.

这是 Maybe 克隆:

data Perhaps a = Yes a | No  deriving (Eq, Show)

instance Functor Perhaps where
   fmap f (Yes a) = Yes (f a)
   fmap f No      = No

instance Applicative Perhaps where
   pure a = Yes a
   No    <*> _     = No
   _     <*> No    = No
   Yes f <*> Yes x = Yes (f x)
   

现在是 ZipList:

data Zip a = Zip [a]  deriving (Eq,Show)

instance Functor Zip where
   fmap f (Zip xs) = Zip (map f xs)

instance Applicative Zip where
   Zip fs <*> Zip xs = Zip (zipWith id fs xs)   -- zip them up, applying the fs to the xs
   pure a = Zip (repeat a)   -- infinite so that when you zip with something, lengths don't change

结构1:组合元素:Monoid

也许克隆

首先让我们看一下Perhaps String。有两种组合方式。首先串联

(<++>) :: Perhaps String -> Perhaps String -> Perhaps String
Yes xs <++> Yes ys = Yes (xs ++ ys)
Yes xs <++> No     = Yes xs
No     <++> Yes ys = Yes ys
No     <++> No     = No

连接本质上在 String 级别工作,而不是真正的 Maybe 级别,将No其视为Yes []. 它等于liftA2 (++)。这是明智且有用的,但也许我们可以从仅使用++到使用任何组合方式进行概括——然后是任何 Monoid!

(<++>) :: Monoid a => Perhaps a -> Perhaps a -> Perhaps a
Yes xs <++> Yes ys = Yes (xs `mappend` ys)
Yes xs <++> No     = Yes xs
No     <++> Yes ys = Yes ys
No     <++> No     = No

这个幺半群结构试图在这个层面上Perhaps尽可能多地工作。a注意Monoid a约束,告诉我们我们正在使用a关卡中的结构。这不是替代结构,它是派生(提升)的 Monoid 结构。

instance Monoid a => Monoid (Perhaps a) where
   mappend = (<++>)
   mempty = No

在这里,我使用了数据 a 的结构来为整个事物添加结构。如果我正在组合Sets,我将能够添加一个Ord a上下文。

ZipList 克隆

那么我们应该如何将元素与 zipList 结合起来呢?如果我们将它们组合起来,它们应该压缩到什么位置?

   Zip ["HELLO","MUM","HOW","ARE","YOU?"] 
<> Zip ["this", "is", "fun"]
=  Zip ["HELLO" ? "this",   "MUM" ? "is",   "HOW" ? "fun"]

mempty = ["","","","",..]   -- sensible zero element for zipping with ?

但是我们应该使用什么?。我说这里唯一明智的选择是++。实际上,对于列表,(<>) = (++)

   Zip [Just 1,  Nothing, Just 3, Just 4]
<> Zip [Just 40, Just 70, Nothing]
 =  Zip [Just 1 ? Just 40,    Nothing ? Just 70,    Just 3 ? Nothing]

mempty = [Nothing, Nothing, Nothing, .....]  -- sensible zero element

但是我们可以使用什么?我说我们是要组合元素,所以我们应该再次使用 Monoid 中的元素组合运算符:<>.

instance Monoid a => Monoid (Zip a) where
   Zip as `mappend` Zip bs = Zip (zipWith (<>) as bs) -- zipWith the internal mappend
   mempty = Zip (repeat mempty)  -- repeat the internal mempty

这是使用 zip 组合元素的唯一合理方式 - 所以它是唯一合理的 monoid 实例。

有趣的是,这不适用于上面的 Maybe 示例,因为 Haskell 不知道如何组合Ints - 它应该使用+or*吗?要获取数值数据的 Monoid 实例,您可以将它们包装起来SumProduct告诉它要使用哪个 monoid。

Zip [Just (Sum 1),   Nothing,       Just (Sum 3), Just (Sum 4)] <> 
Zip [Just (Sum 40),  Just (Sum 70), Nothing]
= Zip [Just (Sum 41),Just (Sum 70), Just (Sum 3)]

   Zip [Product 5,Product 10,Product 15] 
<> Zip [Product 3, Product 4]
 =  Zip [Product 15,Product 40]

关键

请注意, Monoid 中的类型有 kind*正是允许我们将Monoid a上下文放在这里的事实——我们也可以添加Eq aor Ord a。在 Monoid 中,原始元素很重要。Monoid 实例旨在让您操作和组合结构内的数据。

结构2:更高层次的选择:Alternative

选择运算符是相似的,但也不同。

也许克隆

(<||>) :: Perhaps String -> Perhaps String -> Perhaps String
Yes xs <||> Yes ys = Yes xs   -- if we can have both, choose the left one
Yes xs <||> No     = Yes xs
No     <||> Yes ys = Yes ys
No     <||> No     = No  

这里没有连接- 我们根本没有使用++- 这种组合纯粹在Perhaps级别上工作,所以让我们将类型签名更改为

(<||>) :: Perhaps a -> Perhaps a -> Perhaps a
Yes xs <||> Yes ys = Yes xs   -- if we can have both, choose the left one
Yes xs <||> No     = Yes xs
No     <||> Yes ys = Yes ys
No     <||> No     = No  

注意没有约束——我们没有使用a关卡的结构,只是使用关卡的结构Perhaps。这是一种替代结构。

instance Alternative Perhaps where
   (<|>) = (<||>)
   empty = No  

ZipList 克隆

我们应该如何在两个 ziplist 之间进行选择?

Zip [1,3,4] <|> Zip [10,20,30,40] = ????

在元素上使用会很诱人<|>,但我们不能,因为元素的类型对我们不可用。让我们从empty. 它不能使用元素,因为我们在定义 Alternative 时不知道元素的类型,所以它必须是Zip []. 我们需要它是 的左(最好是右)身份<|>,所以

Zip [] <|> Zip ys = Zip ys
Zip xs <|> Zip [] = Zip xs

有两个明智的选择Zip [1,3,4] <|> Zip [10,20,30,40]

  1. Zip [1,3,4]因为它是第一个 - 与 Maybe 一致
  2. Zip [10,20,30,40]因为它是最长的 - 与Zip []被丢弃一致

好吧,这很容易决定:因为pure x = Zip (repeat x),两个列表可能都是无限的,所以比较它们的长度可能永远不会终止,所以必须选择第一个。因此,唯一合理的 Alternative 实例是:

instance Alternative Zip where
   empty = Zip []
   Zip [] <|> x = x
   Zip xs <|> _ = Zip xs

这是我们可以定义的唯一明智的替代方案。请注意它与 Monoid 实例有多么不同,因为我们不能弄乱元素,我们甚至不能看它们。

关键

请注意,因为Alternative采用了一种构造函数,* -> *所以不可能添加Ord aorEq aMonoid a上下文。不允许替代项使用有关结构内数据的任何信息。不管你多么想对数据任何事情,你都不能对数据做任何事情,除非把它扔掉。

关键点:Alternative 和 Monoid 有什么区别?

不是很多——它们都是幺半群,但总结最后两节:

Monoid *实例使合并内部数据成为可能。Alternative (* -> *)实例使它不可能。Monoid 提供灵活性,Alternative 提供保证。种类*(* -> *)是这种差异的主要驱动因素。拥有它们可以让您同时使用这两种操作。

这是正确的事情,我们的两种口味都很合适。Monoid 实例Perhaps String表示将所有字符放在一起,Alternative 实例表示字符串之间的选择。

Maybe 的 Monoid 实例没有任何问题——它正在做它的工作,结合数据。
Maybe 的 Alternative 实例没有任何问题——它在做自己的工作,在事物之间进行选择。

Zip 的 Monoid 实例结合了它的元素。Zip 的 Alternative 实例被迫选择其中一个列表 - 第一个非空列表。

能够同时做到这两点很好。

Applicative 上下文有什么用?

选择和申请之间有一些互动。请参阅Antal SZ 在他的问题中或在他的回答中间陈述的法律。

从实际的角度来看,它很有用,因为 Alternative 是一些 Applicative Functors 用来选择的东西。该功能被用于 Applicatives,因此发明了一个通用接口类。Applicative Functor 非常适合表示产生值的计算(IO、解析器、输入 UI 元素......),其中一些必须处理失败 - 需要替代方案。

为什么 Alternative 有empty

为什么 Alternative 需要一个空的方法/成员?我可能是错的,但它似乎根本没有被使用......至少在我能找到的代码中。而且这似乎不符合课堂的主题——如果我有两件事,并且需要选择一个,我需要一个“空”做什么?

这就像问为什么加法需要一个 0 - 如果你想添加东西,那么拥有不添加任何东西的东西有什么意义?答案是 0 是一切都围绕它旋转的关键数字,就像 1 对乘法[]至关重要,对列表至关重要(并且y=e^x对微积分至关重要)。实际上,您可以使用这些无所事事的元素来开始构建:

sum = foldr (+) 0
concat = foldr (++) []
msum = foldr (`mappend`) mempty          -- any Monoid
whichEverWorksFirst = foldr (<|>) empty  -- any Alternative

我们不能用 Monad+Alternative 替换 MonadPlus 吗?

MonadPlus 类型类的意义何在?我不能通过将某些东西同时用作 Monad 和 Alternative 来解锁它的所有优点吗?为什么不直接放弃呢?(我确定我错了,但我没有任何反例)

你没看错,没有反例!

您的有趣问题让 Antal SZ、Petr Pudlák 和我深入研究了 MonadPlus 和 Applicative 之间的关系究竟是什么。在这里这里的答案 是,任何是 a MonadPlus(在左侧分布意义上 - 请点击链接了解详细信息)也是 a Alternative,但不是相反。

这意味着如果你创建一个 Monad 和 MonadPlus 的实例,它无论如何都满足 Applicative 和 Alternative 的条件。这意味着如果您遵循 MonadPlus 的规则(左 dist),您也可以将您的 Monad 设为 Applicative 并使用 Alternative。

但是,如果我们删除 MonadPlus 类,我们会删除一个用于记录规则的合理位置,并且您将无法指定某个东西的 Alternative 而不是 MonadPlus(从技术上讲,我们应该为 Maybe 这样做)。这些都是理论上的原因。实际原因是它会破坏现有代码。(这也是为什么 Applicative 和 Functor 都不是 Monad 的超类的原因。)

Alternative和Monoid不是一样的吗?Alternative和Monoid不是完全不同的吗?

'pedia 说“Alternative 类型类适用于也具有幺半群结构的 Applicative 函子。” 我不明白——Alternative 不是意味着与 Monoid 完全不同的东西吗?即,我将 Alternative 类型类的要点理解为在两件事之间进行选择,而我将 Monoids 理解为关于组合事物。

Monoid 和 Alternative 是以合理的方式从两个对象中获取一个对象的两种方法。Maths 不在乎你是在选择、组合、混合还是炸毁你的数据,这就是为什么 Alternative 被称为 Applicative 的 Monoid 的原因。你现在似乎对这个概念很熟悉,但你现在说

对于同时具有 Alternative 和 Monoid 实例的类型,这些实例应该是相同的

我不同意这一点,我认为我的 Maybe 和 ZipList 示例已仔细解释了它们为何不同。如果有的话,我认为它们相同的情况应该很少见。我只能想到一个例子,简单的列表,这是合适的。这是因为列表是具有 的幺半群的基本示例++,但在某些情况下,列表也被用作元素的不确定选择,因此<|>也应该是++

于 2012-11-01T10:03:20.163 回答
8

概括

  • 我们需要为一些应用函子定义(提供相同操作的实例) Monoid 实例,它们真正在应用函子级别组合,而不仅仅是提升较低级别的幺半群。下面的示例错误litvar = liftA2 mappend literal variable显示<|>通常不能定义为liftA2 mappend; <|>在这种情况下,通过组合解析器而不是它们的数据来工作。

  • 如果我们直接使用 Monoid,我们需要语言扩展来定义实例。Alternative是更高种类的,因此您可以在不需要语言扩展的情况下制作这些实例。

示例:解析器

假设我们正在解析一些声明,因此我们导入了我们需要的所有内容

import Text.Parsec
import Text.Parsec.String
import Control.Applicative ((<$>),(<*>),liftA2,empty)
import Data.Monoid
import Data.Char

并考虑我们将如何解析类型。我们选择简单:

data Type = Literal String | Variable String  deriving Show
examples = [Literal "Int",Variable "a"]

现在让我们为文字类型编写一个解析器:

literal :: Parser Type
literal = fmap Literal $ (:) <$> upper <*> many alphaNum

含义:解析一个upper大小写字符,然后是many alphaNumeric 字符,将结果与纯函数组合成一个字符串(:)。然后,应用纯函数Literal将这些Strings 变成Types。我们将以完全相同的方式解析变量类型,除了以lower大小写字母开头:

variable :: Parser Type
variable = fmap Variable $ (:) <$> lower <*> many alphaNum

太好了,parseTest literal "Bool" == Literal "Bool"正如我们所希望的那样。

问题 3a:如果要将 applicative 的效果与 Monoid 的行为结合起来,为什么不直接liftA2 mappend

编辑:哎呀-忘了实际使用<|>
现在让我们使用 Alternative 组合这两个解析器:

types :: Parser Type
types = literal <|> variable

这可以解析任何 Type:parseTest types "Int" == Literal "Bool"parseTest types "a" == Variable "a". 这结合了两个解析器,而不是两个。这就是它在 Applicative Functor 级别而不是数据级别上工作的意义。

但是,如果我们尝试:

litvar = liftA2 mappend literal variable

那将要求编译器在数据级别组合它们生成的两个值。我们得到

No instance for (Monoid Type)
  arising from a use of `mappend'
Possible fix: add an instance declaration for (Monoid Type)
In the first argument of `liftA2', namely `mappend'
In the expression: liftA2 mappend literal variable
In an equation for `litvar':
    litvar = liftA2 mappend literal variable

所以我们发现了第一件事;Alternative 类做了一些与 真正不同的事情liftA2 mappend,因为它组合了不同级别的对象——它组合了解析器,而不是解析的数据。如果你喜欢这样想,它是真正更高层次的结合,而不仅仅是提升。我不喜欢这样说,因为Parser Type有 kind *,但确实可以说我们正在组合Parsers,而不是Types。

(即使对于具有 Monoid 实例的类型,也不会liftA2 mappend为您提供与<|>.它失败了。)Parser StringliftA2 mappend<|>

问题 3b:Alternative<|> :: f a -> f a -> f a与 Monoid有何不同mappend :: b -> b -> b

首先,您正确地注意到它没有在 Monoid 实例上提供新功能。

然而,其次,直接使用 Monoid 存在一个问题:让我们尝试mappend在解析器上使用,同时显示它与以下结构相同Alternative

instance Monoid (Parser a) where
    mempty = empty
    mappend = (<|>)

哎呀!我们得到

Illegal instance declaration for `Monoid (Parser a)'
  (All instance types must be of the form (T t1 ... tn)
   where T is not a synonym.
   Use -XTypeSynonymInstances if you want to disable this.)
In the instance declaration for `Monoid (Parser a)'

因此,如果您有一个 applicative functor f,该Alternative实例显示它f a是一个幺半群,但您只能将其声明为Monoid带有语言扩展的 a。

一旦我们{-# LANGUAGE TypeSynonymInstances #-}在文件顶部添加,我们就可以定义

typeParser = literal `mappend` variable

令我们高兴的是,它起作用了:parseTest typeParser "Yes" == Literal "Yes"并且parseTest typeParser "a" == Literal "a".

即使您没有任何同义词(Parser并且String是同义词,所以它们已经出局了),您仍然需要{-# LANGUAGE FlexibleInstances #-}定义一个像这样的实例:

data MyMaybe a = MyJust a | MyNothing deriving Show
instance Monoid (MyMaybe Int) where
   mempty = MyNothing
   mappend MyNothing x = x
   mappend x MyNothing = x
   mappend (MyJust a) (MyJust b) = MyJust (a + b)

(Maybe 的幺半群实例通过提升底层幺半群来解决这个问题。)

使标准库不必要地依赖于语言扩展显然是不可取的。


所以你有它。Alternative 只是 Applicative Functors 的 Monoid(而且不仅仅是 Monoid 的提升)。它需要更高种类的类型f a -> f a -> f a,因此您可以在没有语言扩展的情况下定义一个。

为了完整起见,您的其他问题:

  1. 为什么 Alternative 需要一个空的方法/成员?
    因为拥有一个操作的身份有时很有用。例如,您可以anyA = foldr (<|>) empty在不使用繁琐的边缘情况的情况下进行定义。

  2. MonadPlus 类型类的意义何在?我不能通过将某些东西同时用作 Monad 和 Alternative 来解锁它的所有优点吗?不,我请您回到您链接到的问题

此外,即使 Applicative 是 Monad 的超类,你最终还是需要 MonadPlus 类,因为empty <*> m = empty严格遵守并不足以证明这一点empty >>= f = empty

....我想出了一个例子:也许。我详细解释了这个答案,并在 Antal 的问题中提供了证据。出于此答案的目的,值得注意的是,我能够使用 >>= 来制作违反替代法的 MonadPlus 实例。


Monoid 结构很有用。Alternative 是为 Applicative Functors 提供它的最佳方式。

于 2012-10-29T02:30:37.800 回答
4

我不会介绍 MonadPlus,因为对其法律存在分歧。


在尝试并未能找到任何有意义的示例之后,Applicative 的结构自然会导致与其 Monoid 实例不一致的 Alternative 实例*,我终于想出了这个:

Alternative 的定律比 Monoid 的更严格,因为结果不能依赖于内部类型。这将大量 Monoid 实例排除在 Alternatives 之外。 这些数据类型允许部分(意味着它们仅适用于某些内部类型) Monoid 实例,这些实例被该类型的额外“结构”禁止* -> *。例子:

  • Monoid 的标准 Maybe 实例假定内部类型是 Monoid => 而不是 Alternative

  • ZipLists、元组和函数都可以做成 Monoids,如果它们的内部类型是 Monoids => not Alternatives

  • 具有至少一个元素的序列 - 不能是替代品,因为没有empty

    data Seq a
        = End a
        | Cons a (Seq a)
      deriving (Show, Eq, Ord)
    

另一方面,某些数据类型不能成为 Alternatives,因为它们是*-kinded:

  • 单元 - ()
  • Ordering
  • 数字,布尔值

我推断的结论: 对于同时具有 Alternative 和 Monoid 实例的类型,这些实例应该是相同的。 另请参阅此答案


排除可能,我认为这不算数,因为它的标准实例不应该要求 Monoid 作为内部类型,在这种情况下,它将与 Alternative 相同

于 2012-10-31T22:44:02.333 回答
2

我将 Alternative 类型类的要点理解为在两件事之间进行选择,而我将 Monoids 理解为是关于组合事物。

如果您考虑一下,它们是相同的。

+结合事物(通常是数字),它的类型签名是(Int -> Int -> Int或其他)。

运算符在<|>选项之间进行选择,它的类型签名也是一样的:取两个匹配的东西并返回一个组合的东西。

于 2012-10-26T12:00:37.867 回答