Folding flatMap/bind over a list of functions (a.k.a. Name That Combinator!)

Question

In the process of writing a simple RPN calculator, I have the following type aliases:

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

... and I have written a curious-looking line of Scala code:

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

This takes an initial stack of values and applies a list of operations to that stack. Each operation may fail (i.e. yields an Option[Stack]) so I sequence them with flatMap. The thing that's somewhat unusual about this (in my mind) is that I'm folding over a list of monadic functions, rather than folding over a list of data.

I want to know if there's a standard function that captures this "fold-bind" behavior. When I'm trying to play the "Name That Combinator" game, Hoogle is usually my friend, so I tried the same mental exercise in Haskell:

foldl (>>=) (Just stack) operations

The types here are:

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

So the type of my mystery foldl (>>=) combinator, after making the types of foldl and (>>=) line up, should be:

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

... which is again what we'd expect. My problem is that searching Hoogle for a function with that type yields no results. I tried a couple other permutations that I thought might be reasonable: a -> [a -> m a] -> m a (i.e. starting with a non-monadic value), [a -> m a] -> m a -> m a (i.e. with arguments flipped), but no luck there either. So my question is, does anybody know a standard name for my mystery "fold-bind" combinator?

Answer 1

a -> m a is just a Kleisli arrow with the argument and result types both being a. Control.Monad.(>=>) composes two Kleisli arrows:

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

Think flip (.), but for Kleisli arrows instead of functions.

So we can split this combinator into two parts, the composition and the "application":

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

Now, (>=>) and flip (.) are related in a deeper sense than just being analogous; both the function arrow, (->), and the data type wrapping a Kleisli arrow, Kleisli, are instances of Control.Category.Category. So if we were to import that module, we could in fact rewrite composeParts as:

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

(>>>) (defined in Control.Category) is just a nicer way of writing as flip (.).

---

So, there's no standard name that I know of, but it's just a generalisation of composing a list of functions. There's an Endo a type in the standard library that wraps a -> a and has a Monoid instance where mempty is id and mappend is (.); we can generalise this to any Category:

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)

We can then implement composeParts as:

composeParts = appEndo . mconcat . map Endo . reverse

which is just mconcat . reverse with some wrapping. However, we can avoid the reverse, which is there because the instance uses (.) rather than (>>>), by using the Dual a Monoid, which just transforms a monoid into one with a flipped mappend:

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

This demonstrates that composeParts is a "well-defined pattern" in some sense :)

Answer 2

The one starting with a non-monadic value is (modulo flip)

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

(or foldl)

(Yes, I know this doesn't answer the question, but the code layout in comments isn't satisfactory.)