scala - 在函数列表上折叠 flatMap/bind(也就是命名组合器!)

Question

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

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

...我写了一段看起来很奇怪的 Scala 代码:

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

这需要一个初始 stack值并应用 operations 的列表到那个堆栈。每个操作都可能失败(即产生 Option[Stack] )所以我用 flatMap 对它们进行排序.对此(在我看来)有点不寻常的是，我正在折叠一个单子(monad)函数列表，而不是折叠一个数据列表。

我想知道是否有一个标准函数可以捕获这种“折叠绑定(bind)”行为。当我尝试玩“Name That Combinator”游戏时，Hoogle 通常是我的 friend ，所以我在 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 (即从非单子(monad)值开始)， [a -> m a] -> m a -> m a (即参数翻转)，但也没有运气。所以我的问题是，有人知道我神秘的“折叠绑定(bind)”组合器的标准名称吗？

Answer 1

a -> m a只是一个 Kleisli 箭头，参数和结果类型都是 a。 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 mempty 的实例是 id和 mappend是 (.) ;我们可以将其推广到任何类别:

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 a Monoid，它只是将一个幺半群转换为一个翻转的 mappend :

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

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