12

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

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

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

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

这需要初始stack值并将列表应用于operations该堆栈。每个操作都可能失败（即产生一个Option[Stack]），所以我用flatMap. 对此（在我看来）有点不寻常的是，我正在折叠一个单子函数列表，而不是折叠一个数据列表。

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

4

2 回答 2

15

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 箭头的数据类型都是Control.Category.CategoryKleisli的实例。因此，如果我们要导入该模块，我们实际上可以重写为：composeParts

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

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

所以，我知道没有标准名称，但它只是组成函数列表的概括。Endo a标准库中有一个类型，它包含a -> a一个Monoid实例，其中memptyisid和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一些包装。但是，我们可以通过使用Monoid来避免reverse，因为实例使用(.)而不是，它只是将一个 monoid 转换为一个带有翻转的：(>>>)Dual amappend

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

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

于 2012-01-03T18:36:27.620 回答
2

以非单子值开头的是 (modulo flip)

Prelude> :t foldr (Control.Monad.>=>) return
foldr (Control.Monad.>=>) return
    :: Monad m => [c -> m c] -> c -> m c

（或foldl）

（是的，我知道这不能回答问题，但注释中的代码布局并不令人满意。）

于 2012-01-03T18:32:40.380 回答