计算结构（单子、箭头等）

Question

我对Haskell中的计算模型非常感兴趣。一些资源将monads描述为“可组合计算”，将arrows描述为“计算的抽象视图”。我从未见过monoids、functors或applicative functors以这种方式描述。它们似乎缺乏必要的结构。

我觉得这个想法很有趣，想知道是否有其他类似的构造物。如果有的话，有哪些资源可以让我熟悉它们？Hackage上有没有任何有用的软件包？

注意：这个问题与Monads vs. Arrows和https://stackoverflow.com/questions/2395715/resources-for-learning-monads-functors-monoids-arrows-etc类似，但我正在寻找超出functors、applicative functors、monads和arrows之外的构造物。

编辑：我承认applicative functors应该被认为是“计算构造物”，但我真的在寻找我还没有遇到过的东西。这包括applicative functors、monads和arrows。

- Doug Moore

---

Monad vs. Arrows页面链接到一篇论文，该论文还比较了Applicative Functors（又称为Idioms）。 - Sjoerd Visscher

应用函子绝对是擅长可组合计算的！事实上，它们比单子更好地进行组合（两个应用函子的组合仍为应用函子，而单子则不然）。 - ehird

Answer 1

箭头通过范畴进行广义化，因此通过Category类型类完成。

 class Category f where
     (.) :: f a b -> f b c -> f a c
     id :: f a a

Arrow 类型类定义具有超类 Category。在 Haskell 中，范畴（category）概括了函数（可以组合它们但无法应用它们），因此它们绝对是一种“计算模型”。Arrow 提供了一个带有附加结构的 Category 以处理元组，因此，虽然 Category 反映了关于 Haskell 函数空间的某些内容，但 Arrow 将其扩展到有关乘积类型的内容。

每个 Monad 都会产生一种称为“Kleisli 范畴”的东西，这种构造将为您提供 ArrowApply 实例。您可以从任何 ArrowApply 构建一个 Monad，以便完全回到原来的行为，因此在某种深层意义上，Monad 和 ArrowApply 是相同的事物。

 newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

 instance Monad m => Category (Kleisli m) where
     id = Kleisli return
     (Kleisli f) . (Kleisli g) = Kleisli (\b -> g b >>= f)

 instance Monad m => Arrow (Kleisli m) where
     arr f = Kleisli (return . f)
     first (Kleisli f) = Kleisli (\ ~(b,d) -> f b >>= \c -> return (c,d))
     second (Kleisli f) = Kleisli (\ ~(d,b) -> f b >>= \c -> return (d,c))

实际上，每个箭头（Arrow）除了 Category 超类之外，都会引出一个 Applicative（通常是普遍量化以获得正确的种类），我相信适当的 Category 和 Applicative 的组合足以重构你的 Arrow。

因此，这些结构是深度相关的。

警告：以下是犹豫不决的评论。 Functor / Applicative / Monad 思考方式和 Category / Arrow 思考方式之间的一个主要区别是，在 对象级别 （Haskell 中的类型）上，Functor 及其类似物是泛化，而 Category / Arrow 是 态射 概念的泛化（在 Haskell 中是函数）。 我认为，在广义 态射 的层面进行思考涉及比在广义 对象 的层面思考更高层次的抽象。 有时候这是一件好事，但有时候则不是。 另一方面，尽管 Arrow 具有范畴基础，而且数学界中没有人认为 Applicative 是有趣的，但我了解到，通常比 Arrow 更容易理解 Applicative。

基本上可以将“Category < Arrow < ArrowApply”和“Functor < Applicative < Monad”视为“Category ~ Functor”，“Arrow ~ Applicative”和“ArrowApply ~ Monad”。

更具体如下： 至于用于模拟计算的其他结构：人们可以经常颠倒范畴构造中的“箭头”（这里只是指态射），以获得“对偶”或“共构造”。 因此，如果一个单子（monad）被定义为

class Functor m => Monad m where
   return :: a -> m a
   join :: m (m a) -> m a

（好的，我知道这并不是Haskell如何定义事物的方式，但ma >> = f = join $ fmap f ma和join x = x >>= id，因此它同样可以）那么共函子是

class Functor m => Comonad m where
   extract :: m a -> a -- this is co-return
   duplicate :: m a -> m (m a) -- this is co-join

原来这种东西也很常见。事实证明，Comonad是元胞自动机的基本底层结构。为了完备起见，我应该指出Edward Kmett的Control.Comonad将duplicate放在“可扩展函子”类中，在函子和Comonad之间，因为您还可以定义

   extend :: (m a -> b) -> m a -> m b -- Looks familiar? this is just the dual of >>=
   extend f = fmap f . duplicate
   --this is enough
   duplicate = extend id

事实证明，所有的Monad也都是“可扩展”的。

   monadDuplicate :: Monad m => m a -> m (m a)
   monadDuplicate = return

所有的 Comonads 都是“可合并的”

   comonadJoin :: Comonad m => m (m a) -> m a
   comonadJoin = extract

所以这些结构非常靠近彼此。

- Philip JF

---

很好，范畴和共函子是我接下来要讲的两个主题。谢谢。 - Doug Moore

啊，我喜欢你元胞自动机的例子。Edward Kmett在Haskell中有一个非常酷的帖子，讲述如何将每个共函子转化为单子，但反之不成立。链接。这是非常高级的东西，但如果你花时间去理解它，就能明白两者之间的联系。 - Edgar Klerks

@EdgarKlerks，我认为那篇文章最有趣的后果之一是Store共同子类可能相当基本：因为镜头只是“存储共同子代数”（又名Lens a b = a -> Store b a），而State是通过取存储共同子代数的末端得到的。在镜头和状态之间，你拥有了类似于命令式编程的东西。不过，我仍然感觉离理解其重要性还有很长的路要走。 - Philip JF

Answer 2

所有的Monad都是Arrows（Monad与ArrowApply同构）。以不同的方式，所有的Monad都是Applicative的实例，其中<*>是Control.Monad.ap，*>是>>。Applicative比较弱，因为它不能保证>>=操作。因此，Applicative捕获不检查先前结果和基于值分支的计算。回顾一下，许多monadic代码实际上是applicative的，通过干净的重写可以实现这一点。

通过 GHC 7.4.1 中最新的 Constraint kinds，可以更好地设计 受限制的 monads。同时也有人研究 参数化的 monads，当然我也包括了 Oleg 的一些内容。

- Chris Kuklewicz

---

是的，单子（monads）大致上是箭头（arrows）的专业化，并且是适用性的一般化。是否有单子的一般化不是箭头的？也许有某些将箭头泛化的东西？ - Doug Moore

Answer 3

在图书馆中，这些结构引发了不同类型的计算。
例如，Applicatives可以用于实现静态效果。我指的是预先定义的效果。例如，在实现状态机时，拒绝或接受输入状态。它们不能用于按照其输入来操作其内部结构。
类型说明一切：

 <*> :: f (a -> b) -> f a -> f b

很容易理解，f的结构不能依赖于a的输入。因为在类型层面上，a无法访问f。

单子可以用于动态效果。这也可以从类型签名推理出来：

 >>= :: m a -> (a -> m b) -> m b

你能看到这个吗？因为a和m处于同一“级别”。从数学上讲，这是一个两阶段的过程。Bind是两个函数组合的结果：fmap和join。首先，我们使用fmap和monadic action一起创建一个嵌入在旧结构中的新结构：

fmap :: (a -> b) -> m a -> m b
f :: (a -> m b)
m :: m a
fmap f :: m a -> m (m b)
fmap f m :: m (m b)

Fmap可以基于输入值创建一个新的结构。然后我们使用join将结构合并，这样我们就能够在单子计算中以一种依赖于输入的方式操纵结构：

join :: m (m a) -> m a
join (fmap f m) :: m b

很多单子使用join更容易实现：

(>>=) = join . fmap 

使用单子是可以实现的：

addCounter :: Int -> m Int () 

但不是使用应用程序，而是应用程序（和任何单子）可以执行以下操作：

addOne :: m Int ()

箭头可以更好地控制输入和输出类型，但对我来说，它们与应用程序非常相似。也许我对此有误解。

- Edgar Klerks