What is the name of this monad-like functional programming pattern?

20
votes

I have occasionally encountered a pattern in code which resembles a monad but does not keep a consistent type across >>=.

Here is the simplest example I could come up with:

(First some type-level booleans:

data TyT = TyT
data TyF = TyF

class TyOr a b c | a b -> c

instance TyOr TyF TyF TyF
-- rest similarly

)

Now here is our "monad" type constructor:

data Marked p a = Marked a
    deriving (Show)

For a given p, Marked p is a * -> * which acts very much like m in a monad, but different, as occurs next, when we define "bind":

(>>%) :: (TyOr p q r) => Marked p a -> (a -> Marked q b) -> Marked r b
(Marked x) >>% f = Marked y where Marked y = f x

What's different here is that the result of >>% has a different type constructor than the arguments. Other than that it's basically a monad.

We could use it like this:

a :: Marked TyF Int
a = Marked 5

f :: Int -> Marked TyT Int
f x = Marked (x + 1)

ghci> a >>% f
Marked 6

ghci> :t a >>% f
a >>% f :: Marked TyT Int

(This was inspired by outis's observation that Python's "with" can't be a monad because it changes the type, but I've seen it in other (simpler) ways too).

1
design-patternshaskellfunctional-programmingmonads
The type signature of (>>%) looks closer to flip (<*>) :: Applicative f => f a -> (f a -> f b) -> f b than (>>=) :: Monad m => m a -> (a -> m b) -> m b, so I'd say this is more applicative-like than monad-like. – hammar
You're right. I actually want to fix that to be more monad-like though, even though I'm not really "using" monads. I'll edit it. Though I would have more or less the same question about Applicatives. – Owen
Google for "Indexed Monad", "Monadish", or "Monadic Region". – Apocalisp

1 Answers

10
votes

Well, it's closely related to monads in some sense, just incompatible with the Monad type class. In particular, we can note the following parallels:

  • Monoids have an associative operation with identity defined on values of a consistent type: mappend :: a -> a -> a and mempty :: a.

  • Monads have an associative operation with identity defined on type constructors, e.g.: join :: m (m a) -> m a and return :: a -> m a.

  • Functions--really, arrows in a category--have an associative operation and identity, but the associative operation is indexed by the objects of the category, which here means "types": (.) :: arr b c -> arr a b -> arr a c and id :: arr a a.

...so what would a monad whose join is indexed by types be? Hm.

A few references you might find interesting, exploring related concepts:

post scriptum -- You said this in a comment on the question:

You're right. I actually want to fix that to be more monad-like though, even though I'm not really "using" monads. I'll edit it. Though I would have more or less the same question about Applicatives.

Actually, limiting things to Applicative changes matters significantly! The difference between a -> Marked p b and Marked p (a -> b) is that, in the former, the properties of the Marked p structure can depend on the a parameter; whereas in the latter, the marking is independent of the function's arguments. The independence means that the two can treated separately, which simplifies matters considerably; noting that any value of type a is isomorphic to a function of type () -> a, you can probably turn it into some sort of two-tiered version of Arrow in a straightforward manner.

On the other hand, involving Monad implies some degree of interleaving between the functions and the marking context, which complicates matters for reasons similar to those discussed in the answers to this question.