列表的另一种选择
An alternative Alternative for lists
几次之后，我发现自己在定义：
(<?>) :: [a] -> [a] -> [a]
[] <?> ys = ys
xs <?> _ = xs
当然这是一个结合运算，空表[]既是左恒等式又是右恒等式。它的功能类似于 Python 的 or。
在我看来，这会是一个不错的 (<|>)，比 (++) 更好。选择第一个非空列表感觉更像是我对名为 Alternative 的类型类的期望，而不是连接列表。不可否认，它也不适合 MonadPlus，但我认为这是为拯救付出的小代价。我们在标准库中已经有了 (++) 和 (<>)；我们需要另一个同义词，还是一个新函数（据我所知）会更有帮助？
起初我认为这可能是 ZipList 的一个很好的 Alternative 实例，但 this answer 之后关于相关问题的讨论让我相信并非如此。除了向后兼容性和保持 MonadPlus 合理之外，当前实例而不是这个新实例还有哪些参数？
很难直接回答您的问题。孤立地考虑，您提出的实例从根本上没有错。尽管如此，还是有很多东西可以支持现有的 Alternative 列表实例。
Admittedly, it doesn't fit MonadPlus as well, but I think that a small price to pay for salvation.
沿着这条路走下去的一个问题是 Alternative 是为了捕捉与 MonadPlus 相同的一般概念，但是根据 Applicative 而不是 Monad.引用 a relevant answer by Edward Kmett:
Effectively, Alternative is to Applicative what MonadPlus is to Monad.
从这个角度来看，不匹配的 Alternative 和 MonadPlus 实例令人困惑和误导，就像 Applicative 和 Monad 实例的类似情况一样.
（这个论点的一个可能的反驳是想知道为什么我们需要关心 MonadPlus，因为它表达了相同的概念并提供了与 Alternative 基本相同的方法。它不过，应该注意的是，MonadPlus 法则比 Alternative 法则更强，因为它的方法与 Monad 法则的相关交互不能用 [=15] 来表达=]。既然如此，MonadPlus 仍然具有其自身的意义，并且 classes 的假设改革的一个可想象的结果是将其保留为仅法律 class，例如在 this answer by Antal Spector-Zabusky 的最后一节中讨论的那样。）
鉴于这些考虑，在下文中我将假设 MonadPlus 的持续相关性。这使得这个答案的其余部分更容易写，因为 MonadPlus 是 Haskell 中一般概念的原始表达，因此在追溯列表的起源时非常有必要参考它Alternative.
的实例
It seems to me that this would make a nice (<|>), better than (++) would. Choosing the first nonempty list feels more like what I would expect from a typeclass named Alternative than concatenating lists.
然而，追溯 MonadPlus 和 Alternative 的根源表明，连接列表实例不仅已经确立，而且甚至是范例。例如，引用 Hutton 和 Meijer 的 classic 论文，Monadic parsing in Haskell (1998)，p。 4:
That is, a type constructor m is a member of the class MonadZero if it is a member of the class Monad, and if it is also equipped with a value zero of the specified type. In a similar way, the class MonadPlus builds upon the class MonadZero by adding a (++) operation of the specified type.
（请注意，作者确实使用 (++) 作为 mplus 的名称。）
这里 mplus 的概念是非确定性选择：如果计算 u 和 v 每个都有一些可能的结果，那么 u `mplus` v 的可能结果将是 u 和 v 的所有可能结果。最基本的实现是通过列表的 MonadPlus，尽管这个想法扩展到涵盖其他非确定性单子，例如 Hutton 和 Meijer 的 Parser:
newtype Parser a = Parser (String -> [(a,String)])
换一种说法，我们可以将非确定性选择描述为包容性析取，而您提出的操作是一种（左偏）排他性选择。 （值得注意的是，Hutton 和 Meijer 还为他们的 Parser 定义了一个确定性选择运算符 (+++)，这很像您的运算符，只是它只选择第一次成功计算的第一个结果。）
进一步的相关观察：来自 transformers that doesn't have a mtl class counterpart is ListT. That is so because the class which generalises the ListT functionality is precisely MonadPlus. Quoting a Gabriella Gonzalez comment:
的 monad 转换器之一
MonadPlus is basically the "list monad" type class. For example: cons a as = return a `mplus` as and nil = mzero.
请注意，变形金刚' ListT 的损坏不是问题。一般来说，ListT-done-right 的各种表述都配备了一个串联的 MonadPlus 实例（示例：one, two, three）。
至此，我们可能希望保持 Alternative [] 和 MonadPlus [] 实例不变。尽管如此，如果它没有认识到 有多种合理的选择概念，并且您的运营商体现了其中之一，那么这个答案将是缺乏的。
Alternative 和 MonadPlus 的“官方”法律（即文档中实际提及的法律）并未指定单一的选择概念。既然如此，我们最终会在同一 Alternative/MonadPlus 保护伞下得到非确定性（例如 mplus @[]）和确定性（例如 mplus @Maybe）选择实例。此外，如果有人选择无视我上面的论点并将 mplus @[] 替换为您的运算符，那么“官方”法律中的任何内容都不会阻止他们。多年来，一直有一些关于 reforming MonadPlus 的讨论，通过将其拆分为带有额外法则的 classes，以区分不同的选择概念。不过，这种改革实际发生的可能性似乎并不高（大量流失却带来相对较少的实际利益）。
为了对比起见，考虑一下 near-semiring 解释很有趣，这是对 MonadPlus 和 Alternative 的重新构想之一，可能会在假设 class 层级改革。有关它的完整说明，请参阅 Rivas、Jaskelioff 和 Schrijvers，A Unified View of Monadic and Applicative Non-determinism (2018)。就我们当前的目的而言，只要注意到解释通过向幺半群法则添加 Alternative 的“左零”和“左分布”法则，将 classes 裁剪为非确定性选择就足够了。 .
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 和 m2 的结果，m1 >>= k 或 m2 >>= k 是否会失败。为了用有形的东西来结束这个答案，这里是这一点的示范：
-- 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]
几次之后，我发现自己在定义：
(<?>) :: [a] -> [a] -> [a]
[] <?> ys = ys
xs <?> _ = xs
当然这是一个结合运算，空表[]既是左恒等式又是右恒等式。它的功能类似于 Python 的 or。
在我看来，这会是一个不错的 (<|>)，比 (++) 更好。选择第一个非空列表感觉更像是我对名为 Alternative 的类型类的期望，而不是连接列表。不可否认，它也不适合 MonadPlus，但我认为这是为拯救付出的小代价。我们在标准库中已经有了 (++) 和 (<>)；我们需要另一个同义词，还是一个新函数（据我所知）会更有帮助？
起初我认为这可能是 ZipList 的一个很好的 Alternative 实例，但 this answer 之后关于相关问题的讨论让我相信并非如此。除了向后兼容性和保持 MonadPlus 合理之外，当前实例而不是这个新实例还有哪些参数？
很难直接回答您的问题。孤立地考虑，您提出的实例从根本上没有错。尽管如此，还是有很多东西可以支持现有的 Alternative 列表实例。
Admittedly, it doesn't fit
MonadPlusas well, but I think that a small price to pay for salvation.
沿着这条路走下去的一个问题是 Alternative 是为了捕捉与 MonadPlus 相同的一般概念，但是根据 Applicative 而不是 Monad.引用 a relevant answer by Edward Kmett:
Effectively,
Alternativeis toApplicativewhatMonadPlusis toMonad.
从这个角度来看，不匹配的 Alternative 和 MonadPlus 实例令人困惑和误导，就像 Applicative 和 Monad 实例的类似情况一样.
（这个论点的一个可能的反驳是想知道为什么我们需要关心 MonadPlus，因为它表达了相同的概念并提供了与 Alternative 基本相同的方法。它不过，应该注意的是，MonadPlus 法则比 Alternative 法则更强，因为它的方法与 Monad 法则的相关交互不能用 [=15] 来表达=]。既然如此，MonadPlus 仍然具有其自身的意义，并且 classes 的假设改革的一个可想象的结果是将其保留为仅法律 class，例如在 this answer by Antal Spector-Zabusky 的最后一节中讨论的那样。）
鉴于这些考虑，在下文中我将假设 MonadPlus 的持续相关性。这使得这个答案的其余部分更容易写，因为 MonadPlus 是 Haskell 中一般概念的原始表达，因此在追溯列表的起源时非常有必要参考它Alternative.
然而，It seems to me that this would make a nice
(<|>), better than(++)would. Choosing the first nonempty list feels more like what I would expect from a typeclass namedAlternativethan concatenating lists.
追溯 MonadPlus 和 Alternative 的根源表明，连接列表实例不仅已经确立，而且甚至是范例。例如，引用 Hutton 和 Meijer 的 classic 论文，Monadic parsing in Haskell (1998)，p。 4:
That is, a type constructor
mis a member of the classMonadZeroif it is a member of the classMonad, and if it is also equipped with a valuezeroof the specified type. In a similar way, the classMonadPlusbuilds upon the classMonadZeroby adding a(++)operation of the specified type.
（请注意，作者确实使用 (++) 作为 mplus 的名称。）
这里 mplus 的概念是非确定性选择：如果计算 u 和 v 每个都有一些可能的结果，那么 u `mplus` v 的可能结果将是 u 和 v 的所有可能结果。最基本的实现是通过列表的 MonadPlus，尽管这个想法扩展到涵盖其他非确定性单子，例如 Hutton 和 Meijer 的 Parser:
newtype Parser a = Parser (String -> [(a,String)])
换一种说法，我们可以将非确定性选择描述为包容性析取，而您提出的操作是一种（左偏）排他性选择。 （值得注意的是，Hutton 和 Meijer 还为他们的 Parser 定义了一个确定性选择运算符 (+++)，这很像您的运算符，只是它只选择第一次成功计算的第一个结果。）
进一步的相关观察：来自 transformers that doesn't have a mtl class counterpart is ListT. That is so because the class which generalises the ListT functionality is precisely MonadPlus. Quoting a Gabriella Gonzalez comment:
MonadPlusis basically the "list monad" type class. For example:cons a as = return a `mplus` asandnil = mzero.
请注意，变形金刚' ListT 的损坏不是问题。一般来说，ListT-done-right 的各种表述都配备了一个串联的 MonadPlus 实例（示例：one, two, three）。
至此，我们可能希望保持 Alternative [] 和 MonadPlus [] 实例不变。尽管如此，如果它没有认识到
Alternative 和 MonadPlus 的“官方”法律（即文档中实际提及的法律）并未指定单一的选择概念。既然如此，我们最终会在同一 Alternative/MonadPlus 保护伞下得到非确定性（例如 mplus @[]）和确定性（例如 mplus @Maybe）选择实例。此外，如果有人选择无视我上面的论点并将 mplus @[] 替换为您的运算符，那么“官方”法律中的任何内容都不会阻止他们。多年来，一直有一些关于 reforming MonadPlus 的讨论，通过将其拆分为带有额外法则的 classes，以区分不同的选择概念。不过，这种改革实际发生的可能性似乎并不高（大量流失却带来相对较少的实际利益）。
为了对比起见，考虑一下 near-semiring 解释很有趣，这是对 MonadPlus 和 Alternative 的重新构想之一，可能会在假设 class 层级改革。有关它的完整说明，请参阅 Rivas、Jaskelioff 和 Schrijvers，A Unified View of Monadic and Applicative Non-determinism (2018)。就我们当前的目的而言，只要注意到解释通过向幺半群法则添加 Alternative 的“左零”和“左分布”法则，将 classes 裁剪为非确定性选择就足够了。 .
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 和 m2 的结果，m1 >>= k 或 m2 >>= k 是否会失败。为了用有形的东西来结束这个答案，这里是这一点的示范：
-- 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]