列表的替代方案

Question

现在有几次，我发现自己定义了：

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

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

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

我起初认为这可能是一个很好的Alternative例子，但在相关问题的答案ZipList之后的讨论让我相信了事实并非如此。除了向后兼容性和保持明智之外，当前实例而不是这个新实例还有什么理由呢？MonadPlus

Answer 1

直接回答你的问题是很棘手的。孤立地考虑，您提出的实例没有什么根本性的错误。尽管如此，还是有很多事情可以用来支持现有的Alternative列表实例。

诚然，它不太合适MonadPlus，但我认为为救赎付出的代价很小。

沿着这条路线走下去的一个问题是，它的Alternative目的是捕获相同的一般概念MonadPlus，但是是在术语方面Applicative而不是在术语方面Monad。引用Edward Kmett的相关回答：

实际上，Alternative就是为了Applicative什么。MonadPlusMonad

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

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

考虑到这些因素，在下文中我将假设MonadPlus. 这使得编写这个答案的其余部分变得更加容易，就像MonadPlusHaskell 中一般概念的原始表达一样，因此在追踪 的列表实例的起源时非常有必要引用它Alternative。

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

MonadPlus然而，追踪和 的根源Alternative表明，串联列表实例不仅是完善的，而且甚至是范例性的。例如，引用 Hutton 和 Meijer 的经典论文，Monadic parsing in Haskell (1998)，p. 11。4：

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

（请注意，作者确实使用(++)来作为他们的名字mplus。）

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

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

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

进一步相关的观察：Transformer中没有mtl类对应项的 monad 转换器之一是ListT。之所以如此，是因为概括功能的类ListT正是MonadPlus. 引用加布里埃拉·冈萨雷斯的评论：

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

请注意，变压器的损坏ListT不是问题。一般来说，ListT-done-right 的各种表述都配有连接MonadPlus实例（示例：一、二、三）。

Alternative []我们可能希望将和MonadPlus []实例保留原样的原因就这么多。尽管如此，如果它没有认识到这一点，正如威尔·尼斯提醒我们的那样，存在多种合理的选择概念，并且您的操作员体现了其中之一，那么这个答案就会缺乏。

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

为了进行对比，考虑近半半解释是很有趣的，这是对假设的阶级等级制度改革的重新想象之一，MonadPlus并且Alternative可能会在假设的阶级等级制度改革中被引用。有关它的完整描述，请参阅 Rivas、Jaskelioff 和 Schrijvers 的《一元论和应用非决定论的统一观点》 (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 @Maybe。MonadPlus左分布使得很难（可能不可能，尽管我现在手头没有证据）将任何结果丢弃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]