17

我对如何在 Haskell 中建模计算变得相当感兴趣。一些资源将 monad 描述为“可组合计算”，将箭头描述为“计算的抽象视图”。我从未见过以这种方式描述的幺半群、函子或应用函子。他们似乎缺乏必要的结构。

我觉得这个想法很有趣，想知道是否还有其他结构可以做类似的事情。如果是这样，我可以使用哪些资源来熟悉它们？Hackage 上是否有任何可能派上用场的软件包？

注意：这个问题类似于 Monads vs. Arrows和https://stackoverflow.com/questions/2395715/resources-for-learning-monads-functors-monoids-arrows-etc，但我正在寻找超越 funtors 的构造，适用函子、单子和箭头。

编辑：我承认应用函子应该被认为是“计算构造”，但我真的在寻找我还没有遇到过的东西。这包括应用函子、单子和箭头。

4

3 回答 3

25

Arrows由类别概括，因此由类型类概括Category。 

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

Arrow类型类定义Category作为超类。类别（在haskell 意义上）概括了函数（您可以组合它们但不能应用它们），因此绝对是“计算模型”。 为处理元组Arrow提供了额外的结构。Category因此，虽然Category反映了有关 Haskell 函数空间的某些内容，但Arrow将其扩展到有关产品类型的某些内容。

每一个Monad都会产生一个叫做“Kleisli 类别”的东西，这个结构给你提供了ArrowApply. 你可以建立一个完整的循环不会改变你的行为Monad的任何东西ArrowApply，所以从某种意义上说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都会产生一个（普遍量化以得到正确的种类） ，我相信适当的组合和足以重建你的. ApplicativeCategoryCategoryApplicativeArrow

因此，这些结构是紧密相连的。

警告：前面有空洞的评论。Functor/ Applicative/Monad思维方式和Category/思维方式之间的一个主要区别Arrow是，虽然Functor及其同类是对象级别的概括（Haskell 中的类型），Category/是态射Arrow概念的泛化（Haskell 中的函数）。我的信念是，在广义态射层面上的思考比在广义对象层面上的思考涉及更高层次的抽象。有时这是一件好事，有时则不是。另一方面，尽管有分类基础，但数学界没有人认为ArrowsApplicative很有趣，我的理解Applicative通常比Arrow.

基本上你可以想到“Category < Arrow < ArrowApply”和“Functor < Applicative < Monad”，例如“Category ~ Functor”、“Arrow ~ Applicative”和“ArrowApply ~ 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可能是这样）然后comonad 是

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的s也是“可扩展的”

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

虽然所有人Comonads都是“可加入的”

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

所以这些结构非常接近。

于 2012-03-09T23:43:03.183 回答
9

所有的 Monad 都是箭头（Monad 与 ArrowApply 同构）。以不同的方式，所有 Monad 都是Applicative的实例，其中<*>isControl.Monad.ap和*>is >>。Applicative 较弱，因为它不保证>>=操作。因此，Applicative 捕获不检查先前结果和分支值的计算。回想起来，许多一元代码实际上是适用的，并且通过干净的重写会发生这种情况。

扩展 monad，在 GHC 7.4.1 中使用最近的 Constraint 类型，现在可以为受限制的 monad提供更好的设计。还有一些人在看参数化的 monad，当然我也包含了Oleg的链接。

于 2012-03-09T17:07:06.440 回答
5

在库中，这些结构会产生不同类型的计算。

例如，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 动作来创建一个嵌入旧结构的新结构：

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

许多 monad 使用 join 更容易实现：

(>>=) = join . fmap

这对于单子是可能的：

addCounter :: Int -> m Int ()

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

addOne :: m Int ()

箭头可以更好地控制输入和输出类型，但对我来说，它们真的与应用程序相似。也许我错了。

于 2012-03-10T14:43:51.890 回答