Monadic pairs and Kleisli arrows

While working on my data-object library, I needed to apply some monadic functions to a tuple, and get back a monaidc tuple. In code:

f :: Monad m => (a -> m b) -> (c -> m d) -> (a, c) -> m (b, d)

The most obvious thing to do is just long-hand it with do notation:

test1 :: Monad m => (a -> m b) -> (c -> m d) -> (a, c) -> m (b, d)
test1 f g (a, c) = do
    b <- f a
    d <- g c
    return (b, d)

But who wants to write that? I got a recommendation instead to try out liftM2. After playing with it a bit, I came out with:

test2 :: Monad m => (a -> m b) -> (c -> m d) -> (a, c) -> m (b, d)
test2 f g (a, c) = uncurry (liftM2 (,)) $ (f *** g) (a, c)

Which is definitely more respectable (though arguably more line noise). After staring at that for a little bit, I realized that there was nothing particularly monadic about this, and could instead be expressed Applicatively:

test3 :: Applicative f => (a -> f b) -> (c -> f d) -> (a, c) -> f (b, d)
test3 f g (a, c) = uncurry (liftA2 (,)) $ (f *** g) (a, c)

Then of course comes the eta-reduction, so you get:

test4 :: Applicative f => (a -> f b) -> (c -> f d) -> (a, c) -> f (b, d)
test4 f g = uncurry (liftA2 (,)) . (f *** g)

Kleisli

I’m sure you noticed the use of *** in test2, test3 and test4. That’s not too surprising; often times we want to use Data.Arrow functions when operating on tuples. As I was staring at the documentation for Data.Arrow, I decided to see what could be done with Kleisli. I came up with:

test5 :: Monad m => (a -> m b) -> (c -> m d) -> (a, c) -> m (b, d)
test5 f g = runKleisli $ Kleisli f *** Kleisli g

This, in my opinion, is much more readable than the above. For those who don’t know, Kleisli allows turning any monadic function into an arrow. Another advantage of this is I can now do things like:

test6 :: Monad m => (a -> m b) -> (a, c) -> m (b, c)
test6 f = runKleisli $ first $ Kleisli f

The downside of test5 versus test4 is that it only works Monadically, not Applicatively. And in case you were wondering, you can’t define a KleisliA type value which will work on all Applicatives. This boils down to where the real extra power of Monads versus Applicatives lies.

All Arrows must be Categorys. One of the functions of a Category is (.), or essentially function composition. The definition for Kleisli monads goes, after unwrapping:

f . g = \b -> g b >>= f

There is no equivalent to this in Applicatives. So sadly, if I want to make my tuple lifting functions work on applicatives, I’m stuck with liftA2.

Advertisements

9 Responses to “Monadic pairs and Kleisli arrows”

  1. steffen Says:

    i find this one in applicative style very clear (but without arrows…):

    test :: (Applicative f) => (a ->f b) -> (c->f d) -> (a, c) -> f (b, d)
    test f g = liftA2 (,) f . fst g . snd

  2. steffen Says:

    yay, ur blog did eat the applicative combinators…
    another try:

    test f g = liftA2 (,) <$> f . fst <*> g . snd

  3. JR Says:

    Is there a generic (automatic) way to create “sound/natural” functions given type signature?
    It would be great if only a type signature would be required and a haskell system (libraries/compiler?) could produce the needed function.

  4. admin Says:

    @JR

    I’m not aware of anything like that. My usual approach is trial and error. I think that Theorems for Free might be related to what you’re discussing, but I haven’t read it: http://portal.acm.org/citation.cfm?id=99404

  5. Daniel Yokomizo Says:

    @JR: Djinn

  6. Andrea Vezzosi Says:

    @steffen

    that’s quite nice, it’s using the fact that the composition of applicative functors gives another applicative functor.
    In this case you’re composing ((a,b) ->) with f, using the names from test4.
    Not having higher order unification in the typeclass resolution we can’t just add that instance and we’ve to use a newtype like in teh TypeCompose package.

    Otherwise we could simply write:

    test f g = liftA2 (,) (f . fst) (g . snd)

  7. Andrea Vezzosi Says:

    in fact, there is something we could call KliesliA, i.e. a canonical way to make arrows out of applicatives[1], and mixing that with my previous post you get this[2].

    Note that defining test we’re interpreting ((a,b) ->) as a functor, while in the Kliesli formulation the focus is on (->) as representation of morphisms.

    [1] http://homepages.inf.ed.ac.uk/wadler/topics/links.html#arrows-and-idioms
    [2] http://hpaste.org/fastcgi/hpaste.fcgi/view?id=10992#a10992

  8. Andrea Vezzosi Says:

    I honestly didn’t play with that type much so i don’t know how useful it is in practice, but if you want to package that up please go ahead 🙂
    As for existing packages It might fit into category-extras or applicative-extras, and maybe it’d need a different name since it doesn’t really relate to kleisli categories afaik.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: