6

现在有几次,我发现自己在定义:

(<?>) :: [a] -> [a] -> [a]
[] <?> ys = ys
xs <?> _  = xs

当然,这是一个关联操作,空列表[]既是左标识又是右标识。它的功能类似于 Python 的or.

在我看来,这会做得很好(<|>),比(++)会更好。选择第一个非空列表感觉更像是我对命名类型类的期望,Alternative而不是连接列表。诚然,它并不适合MonadPlus,但我认为这是为救赎付出的小代价。我们已经拥有(++)(<>)在标准库中;我们是否需要另一个同义词,或者一个新功能(据我所知)会更有帮助?

起初我认为这可能是一个很好的Alternative例子ZipList,但是在这个答案之后对相关问题的讨论让我信服了。除了向后兼容和保持MonadPlus明智之外,对于当前实例而不是这个新实例还有什么论据?

4

1 回答 1

4

给你的问题一个直接的答案是很棘手的。孤立地考虑,您提出的实例没有根本性的错误。尽管如此,仍然可以说很多东西来支持现有Alternative的列表实例。


诚然,它并不适合MonadPlus,但我认为这是为救赎付出的小代价。

沿着这条路线走的一个问题是,Alternative它意味着要捕捉与它相同的一般概念MonadPlus,但在Applicative而不是Monad. 引用Edward Kmett 的相关回答

实际上,AlternativeApplicative什么MonadPlus是什么Monad

从这个角度来看,不匹配的AlternativeMonadPlus实例是令人困惑和误导的,就像ApplicativeMonad实例的类似情况一样。

(对这个论点的一个可能的反驳是想知道为什么我们仍然需要关心MonadPlus,因为它表达了相同的概念并提供了与 基本相同的方法Alternative。但应该注意的是,MonadPlus法律比法律更强大Alternative,因为它的方法与Monad那些方法的相关交互不能用 来表达Alternative。既然如此,MonadPlus仍然有它自己的意义,并且类的假设改革的一个可以想象的结果是将它保留为一个仅限法律的类,例如Antal Spector-Zabusky 在此答案的最后一部分中所讨论的。)

鉴于这些考虑,在接下来的内容中,我将假设MonadPlus. 这使得编写此答案的其余部分变得更加容易,就像MonadPlusHaskell 中一般概念的原始表达一样,因此在追踪Alternative.


在我看来,这会做得很好(<|>),比(++)会更好。选择第一个非空列表感觉更像是我对命名类型类的期望,Alternative而不是连接列表。

但是,追溯 和 的根源可以MonadPlus看出Alternative,连接列表实例不仅是成熟的,而且甚至是范式的。例如,引用 Hutton 和 Meijer 的经典论文,Haskell (1998)中的 Monadic 解析,p. 4:

也就是说,如果类型构造函数m是类的成员,并且它还配备了指定类型的值,那么它就是MonadZero类的成员。以类似的方式,该类通过添加指定类型的操作来构建在该类之上。MonadzeroMonadPlusMonadZero(++)

(请注意,作者确实使用(++)了他们的名字mplus。)

这里捕获的概念mplus是非确定性选择:如果计算uv每个都有一些可能的结果,则 的可能结果u `mplus` v将是 和 的所有可能u结果v。最基本的实现是通过MonadPlusfor 列表,尽管这个想法扩展到涵盖其他非确定性单子,例如 Hutton 和 Meijer 的Parser

newtype Parser a = Parser (String -> [(a,String)])

换一种说法,我们可以将非确定性选择描述为包容性析取,而您提出的操作是(左偏)排他性选择的一种形式。(值得注意的是,Hutton 和 Meijer 还(+++)为他们定义了一个确定性选择运算符,Parser它与您的运算符非常相似,只是它只选择第一个成功计算的第一个结果。)

进一步的相关观察:来自没有mtl类对应物的变压器的 monad 变压器之一是. 之所以如此,是因为概括功能的类正是. 引用Gabriella Gonzalez 的评论ListTListTMonadPlus

MonadPlus基本上是“list monad”类型的类。例如:cons a as = return a `mplus` asnil = mzero

请注意,变压器的损坏ListT不是问题。通常,ListT-done-right 的各种形式都配备了连接MonadPlus实例(示例:)。


之所以如此,是因为我们可能希望将Alternative []MonadPlus []实例保持原样。尽管如此,如果它没有认识到,正如 Will Ness 提醒我们的那样,存在多种合理的选择概念,并且您的运营商体现了其中之一,那么这个答案将是缺乏的。

的“官方”法律(即文档中实际提到的法律)AlternativeMonadPlus没有指定单一的选择概念。既然如此,我们最终会在同一/伞下得到非确定性(例如mplus @[])和确定性(例如)选择实例。此外,如果有人选择无视我上面的论点并替换为您的运营商,那么“官方”法律中的任何内容都不会阻止他们。多年来,有一些关于通过将其划分为具有额外法律的类别来进行改革的讨论,以区分不同的选择概念。不过,这种改革实际上发生的可能性似乎并不高(大量流失而实际收益相对较小)。mplus @MaybeAlternativeMonadPlusmplus @[]MonadPlus

为了进行对比,考虑近乎半透明的解释是很有趣的,这是对假设的阶级等级改革的重新想象之一MonadPlus,并且Alternative可能会被调用。有关它的完整说明,请参阅 Rivas、Jaskelioff 和 Schrijvers,A Unified View of Monadic and Applicative Non-determinism (2018)。对于我们目前的目的,只需注意解释通过向幺半群定律添加“左零”和“左分布”定律来调整类以适应非确定性选择Alternative......

empty <*> x = empty
(f <|> g) <*> x = (f <*> x) <|> (g <*> x)

...以及对于MonadPlus

mzero >>= k = mzero
(m1 `mplus` m2) >>= k = (m1 >>= k) `mplus` (m2 >>= k)

(这些MonadPlus法律比其Alternative对应的法律严格。)

特别是,您的选择运算符遵循所谓的Alternative左分布定律,但不是那个MonadPlus。在这方面,它类似于mplus @MaybeMonadPlus左分布使得很难(可能不可能,尽管我现在手头没有证据)放弃任何结果mplus,因为我们无法判断,在法律的右手边,如果不检查是否会m1 >>= k失败和m2 >>= k的结果。为了用有形的东西来结束这个答案,这里是对这一点的一个演示:m1m2

-- Your operator.
(<?>) :: [a] -> [a] -> [a]
[] <?> ys = ys
xs <?> _  = xs

filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = xs >>= \x -> if p x then [x] else []
-- If MonadPlus left distribution holds, then:
-- filter' p (xs `mplus` ys) = filter' p xs `mplus` filter' p ys
GHCi> filter' even ([1,3,5] <|> [0,2,4])
[0,2,4]
GHCi> filter' even [1,3,5] <|> filter' even [0,2,4]
[0,2,4]
GHCi> filter' even ([1,3,5] <?> [0,2,4])
[]
GHCi> filter' even [1,3,5] <?> filter' even [0,2,4]
[0,2,4]
于 2020-05-23T02:30:20.563 回答