折叠flatMap/bind在一系列函数上(又名Name That Combinator!)

Question

在编写简单的RPN计算器的过程中,我有以下类型的别名:

type Stack = List[Double]
type Operation = Stack => Option[Stack]

...我写了一个好奇的Scala代码:

val newStack = operations.foldLeft(Option(stack)) { _ flatMap _ }

这将获取stack值的初始值并应用operations该堆栈的列表.每个操作都可能失败(即产生一个Option[Stack]),所以我对它们进行排序flatMap.对我来说有些不同寻常的事情(在我看来)是我折叠了一系列monadic函数,而不是折叠数据列表.

我想知道是否有一个标准函数可以捕获这种"折叠绑定"行为.当我试图玩"Name That Combinator"游戏时,Hoogle通常是我的朋友,所以我在Haskell尝试了相同的心理锻炼:

foldl (>>=) (Just stack) operations

这里的类型是:

foldl :: (a -> b -> a) -> a -> [b] -> a
(>>=) :: Monad m => m a -> (a -> m b) -> m b

所以我的神秘foldl (>>=)组合器的类型,在制作类型foldl和(>>=)排队之后,应该是:

mysteryCombinator :: Monad m => m a -> [a -> m a] -> m a

......这也是我们所期待的.我的问题是在Hoogle中搜索具有该类型的函数不会产生任何结果.我尝试了一些我认为可能合理的其他排列:( a -> [a -> m a] -> m a即以非monadic值开始),[a -> m a] -> m a -> m a(即翻转参数),但也没有运气.所以我的问题是,有人知道我的神秘"折叠式"组合器的标准名称吗？

Answer 1

a -> m a只是一个Kleisli箭头,参数和结果类型都是一个.Control.Monad.(> =>)组成两个Kleisli箭头:

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

想想flip (.),但对于Kleisli箭头而不是函数.

所以我们可以将这个组合器分成两部分,组成和"应用程序":

composeParts :: (Monad m) => [a -> m a] -> a -> m a
composeParts = foldr (>=>) return

mysteryCombinator :: (Monad m) => m a -> [a -> m a] -> m a
mysteryCombinator m fs = m >>= composeParts fs

现在,(>=>)和flip (.)在并非只是类似更深的层次上有关; 功能箭头(->)和包装Kleisli箭头的数据类型Kleisli都是Control.Category.Category的实例.因此,如果我们要导入该模块,我们实际上可以重写composeParts为:

composeParts :: (Category cat) => [cat a a] -> cat a a
composeParts = foldr (>>>) id

(>>>)(在Control.Category中定义)只是一种更好的写作方式flip (.).

所以,我所知道的并没有标准名称,但它只是编写一系列函数的概括.Endo a标准库中有一个类型包装,a -> a并且有一个Monoid实例,其中memptyis id和mappendis (.); 我们可以将其概括为任何类别:

newtype Endo cat a = Endo { appEndo :: cat a a }

instance (Category cat) => Monoid (Endo cat a) where
  mempty = Endo id
  mappend (Endo f) (Endo g) = Endo (f . g)

然后我们可以实现composeParts:

composeParts = appEndo . mconcat . map Endo . reverse

这只是mconcat . reverse一些包装.但是,我们可以避免reverse,因为实例使用(.)而不是(>>>)通过使用Dual aMonoid,它只是将一个monoid转换为一个翻转的mappend:

composeParts :: (Category cat) => [cat a a] -> cat a a
composeParts = appEndo . getDual . mconcat . map (Dual . Endo)

这表明composeParts在某种意义上它是一个"明确定义的模式":)