我可以通过应用仿函数的组合来建立一个短路失败的成功列表吗？

Question

用户'singpolyma' 在reddit上询问是否存在一些基本结构:

data FailList a e = Done | Next a (FailList a e) | Fail e

建议使用免费的monad,但我想知道是否可以通过applicative functors更一般地建模.在使用Applicatives的抽象中,Bazerman向我们展示了两个应用函子的总和也是一个应用函子,左/右偏向,只要我们在偏差的方向上有一个自然的变换.这听起来像是我们需要的!因此,我开始提出建议,但很快就遇到了问题.谁能看到这些问题的解决方案？:

---

首先,我们从两个仿函数之和的定义开始.我从这里开始是因为我们想要建模和类型 - 成功或成功以及失败.

data Sum f g a = InL (f a) | InR (g a)

我们想要使用的两个仿函数是:

data Success a = Success [a]
data Failure e a = Failure e [a]

Success直截了当 - 基本上就是这样Const [a].但是,Failure e我不太确定.它不是一个应用程序的函子,因为pure没有任何定义.但是,它是Apply的一个实例:

instance Functor Success where
  fmap f (Success a) = Success a

instance Functor (Failure e) where
  fmap f (Failure e a) = Failure e a

instance Apply (Failure e) where
  (Failure e a) <.> (Failure _ b) = Failure e a

instance Apply Success where
  (Success a) <.> (Success b) = Success (a <> b)

instance Applicative Success where
  pure = const (Success [])
  a <*> b = a <.> b

接下来,我们可以定义这些仿函数的总和,从右到左进行自然变换(左偏差):

instance (Apply f, Apply g, Applicative g, Natural g f) => Applicative (Sum f g) where
  pure x = InR $ pure x
  (InL f) <*> (InL x) = InL (f <*> x)
  (InR g) <*> (InR y) = InR (g <*> y)
  (InL f) <*> (InR x) = InL (f <.> eta x)
  (InR g) <*> (InL x) = InL (eta g <.> x)

而我们现在唯一需要做的就是定义我们的自然转型,这就是崩溃的地方.

instance Natural Success (Failure e) where
  eta (Success a) = Failure ???? a

无法创建Failure似乎是一个问题.此外,即使是hacky并且使用⊥也不是一种选择,因为这将在你拥有的情况下进行评估InR (Success ...) <*> InL (Failure ...).

我觉得我错过了什么,但我不知道它是什么.

可以这样做吗？

Answer 1

我很确定“正确”的答案是创建e一个幺半群，就像你不喜欢 reddit 讨论中的想法一样。

考虑Failure "oops" [(*1),(*2),(*3)] <*> Failure "doh" [1,2,3]结果是否应该将“oops”或“doh”作为失败？通过将e一个幺我们捕获的事实，有没有规范的选择，让消费者选择他们的毒药（可能是First，Last，[]等）

请注意，此解决方案与(Maybe e, [a])表示非常相似，无法正确处理流/潜在无限数据，因为它对结束列表是否失败很严格。

根据后续帖子（http://comonad.com/reader/2013/algebras-of-applicatives/），不同的编码将使用应用程序的固定点。

然后，您获取此处显示的列表表示 ( FixF (ProductF Embed (Sum (Const ()))) a) 并通过将您的错误幺半群粘贴在单位位置来更改它，以获得以下内容：

Monid mon => FixF (ProductF Embed (Sum (Const mon))) a

请注意，您可以使用 aMaybe而不是 monoid 来获得精确的a FailList，但就像FailList您那样，除非您编写一个指定组合错误的正确方法，否则不要免费获得应用实例。

另请注意，使用固定点方法，如果我们有等价物Success [(*1),(*2),(*3)] <*> Failure "doh" [1,2,3,4,5]then 我们会返回Success带有三个元素的 a（即我们在失败时确实不严格），而在您建议的方法中，我们会返回Failure带有三个元素的 a 以及来自五个元素的错误元素失败列表。这就是流与严格之间的权衡。

最后，也是最直接的一点，我们可以type FailList e = Product (Const (First e)) ZipList使用标准的应用机制并获得非常接近原始数据类型的东西。