计算构造(Monads,Arrows等)

Question

我对如何在Haskell中建模计算感兴趣.一些资源将monad描述为"可组合计算",将箭头描述为"计算的抽象视图".我从未见过用这种方式描述的幺半群,仿函数或应用函子.他们似乎缺乏必要的结构.

我发现这个想法很有趣,并想知道是否有其他类似的结构.如果是这样,我可以使用哪些资源来熟悉它们？Hackage上是否有任何可能派上用场的软件包？

注意:这个问题类似于 Monads vs. Arrows和/sf/ask/167700081/,但我正在寻找超越funtors的构造,applicative仿函数,单子和箭头.

编辑:我承认应用仿函数应该被视为"计算结构",但我真的在寻找一些我还没有遇到过的东西.这包括应用函子,monad和箭头.

Answer 1

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引起的Applicative(普遍量化得到正确的种),除了Category超,我相信适当的组合Category和Applicative足够重构你的Arrow.

因此,这些结构是紧密相连的.

警告:未来的评论.Functor/ Applicative/ Monad思维方式与Category/ 思维方式之间的一个中心差异在于Arrow,虽然Functor它的同类是对象层面的泛化(Haskell中的类型),但Category/ Arrow是对态射(Haskell中的函数)概念的泛化.我的观点是,在广义态射的层面上思考涉及比在广义对象层次上思考更高层次的抽象.有时这是好事,有时则不是.另一方面,尽管事实上Arrows有一个明确的基础,并且数学中没有人认为Applicative有趣,但我的理解Applicative通常比人们理解得更好Arrow.

基本上你可以想到"Category <Arrow <ArrowApply"和"Functor <Applicative <Monad"这样的"Category~Functor","Arrow~Applied"和"ArrowApply~Monad".

下面更具体: 对于模型计算的其他结构:人们通常可以在分类结构中反转"箭头"的方向(这里只是意味着态射),以获得"双重"或"共同构建".因此,如果将monad定义为

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

(好吧,我知道这是不是哈斯克尔是如何定义的东西,但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是细胞自动机的基本结构.对于completness,我要指出的是,爱德华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

事实证明,所有Monads都是"可扩展的"

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

虽然Comonads都是"可加入的"

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

所以这些结构非常接近.

Answer 2

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

使用GHC 7.4.1中最近的约束类型扩展monad,现在可以有更好的受限monad设计.还有人在看参数化的monad,当然我还包括Oleg的链接.

Answer 3

在库中,这些结构产生不同类型的计算.

例如,Applicatives可用于实现静态效果.我的意思是效果,正面定义.例如,在实现状态机时,拒绝或接受输入状态.它们不能用于根据输入操纵其内部结构.

类型说明了一切:

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

很容易理解,f的结构不能取决于a的输入.因为a在类型级别上无法达到f.

Monads可用于动态效果.这也可以从类型签名中推断出来:

 >>= :: 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可以根据输入值创建新结构.然后我们用连接来折叠结构,因此我们能够以依赖于输入的方式在monadic计算中操纵结构:

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

使用join可以更轻松地实现许多monad:

(>>=) = join . fmap 

monads可以实现这一点:

addCounter :: Int -> m Int () 

但不是应用程序,但应用程序(和任何monad)可以做的事情,如:

addOne :: m Int ()

箭头可以更好地控制输入和输出类型,但对我来说,它们确实与应用程序类似.也许我错了.