haskell - 我可以通过应用仿函数的组合对短路失败的成功列表进行建模吗？

用户 'singpolyma' asked on reddit 如果底层有一些通用结构:

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

有人建议使用免费的 monad，但我想知道是否可以通过 applicative functors 更普遍地建模。在 Abstracting with 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 ...) 的情况下，这将被评估。

我觉得我错过了一些东西，但我不知道它是什么。

这能做到吗？

最佳答案

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

考虑 Failure "oops" [(*1),(*2),(*3)] <*> Failure "doh" [1,2,3] 结果是否应该将“oops”或“doh”作为失败？通过使 e 成为幺半群，我们捕捉到没有规范选择的事实，并让消费者选择他们的毒药(无论是 First 、 Last 、 0x2513412 )。

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

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

然后你采用那里显示的列表表示( (Maybe e, [a]) )并通过将你的错误幺半群粘贴在单位位置来改变它，以获得以下内容:
FixF (ProductF Embed (Sum (Const ()))) a
请注意，您可以使用 Monid mon => FixF (ProductF Embed (Sum (Const mon))) a 而不是幺半群来获得 Maybe ，但就像使用 FailList 一样，除非您以正确的方式组合一个错误，否则您将无法免费获得应用实例。

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

最后，也是最直接的，我们可以使用 Success 来使用标准的应用机制并获得非常接近原始数据类型的东西。

关于haskell - 我可以通过应用仿函数的组合对短路失败的成功列表进行建模吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15460794/