13

Given two monads, Monad m and Monad n, I would like to transform m (n a) into n (m a). But there seems to be no generic way because both (>>=) and return deals with only one monad type, and although (>>=) allows extracting content from a monad, you must pack them back to the same monad type so it can be a result value.

However, if we set m to a fixed type, the job becomes easy. Take Maybe as an example:

reorder :: (Monad n) => Maybe (n a) -> n (Maybe a) reorder Nothing = return Nothing reorder (Just x) = do x' <- x return $ Just x'

Or a list:

reorder :: (Monad n) => [n a] -> n [a] reorder [] = return [] reorder (x:xs) = do x' <- x xs' <- reorder xs return (x':xs')

Not hard to see, we've got a pattern here. To be more obvious, write it in a Applicative way, and it's no more than applying the data constructor to each element:

reorder (Just x) = Just <$> x reorder (x:xs) = (:) <$> x <*> (reorder xs)

My question is: does a haskell typeclass already exist to describe such operations, or do I have to invent the wheel myself?

I had a brief search in the GHC documentation, and found nothing useful for this topic.

Improve this question

4 Answers 4

Reset to default
14

Data.Traversable provides what you are looking for:

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

GHC even provides support for automatically deriving instances:

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-} import Data.Foldable import Data.Traversable data List a = Nil | Cons a (List a) deriving(Functor, Foldable, Traversable)
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

This, of course, only works when your outer type constructor is a Traversable (not all Monads are). The bonus is that the inner one only has to be Applicative.
5

A quick search on hoogle for (Monad m, Monad n) => m (n a) -> n (m a) showed me that there are several functions that (roughly) comply with the signature you're looking for:

  1. Data.Traversable.sequence :: (Traversable t, Monad m) => t (m a) -> m (t a);
  2. Data.Traversable.sequenceA :: Applicative f => t (f a) -> f (t a);
  3. Contro.Monad.sequence :: Monad m => [m a] -> m [a] (also exported by Prelude).

Both [a] and Maybe a are instances of traversable, so your reorder functions are just applications of Data.Traversable.sequence. One could write, in example:

ghci> (Data.Traversable.sequence $ Just (return 1)) :: IO (Maybe Int) Just 1 it :: Maybe Int ghci> (Data.Traversable.sequence $ Just ([1])) :: [Maybe Int] [Just 1] it :: [Maybe Int] ghci> (Data.Traversable.sequence $ [Just 1]) :: Maybe [Int] Just [1] it :: Maybe [Int]

Please note however that the specific class declaration is class (Functor t, Foldable t) => Traversable t, and if you look also at the types of the other two functions, it does not seems like what you're looking for could possibly be done in a generic way for all monads m and n without restrictions/preconditions.

Improve this answer

Comments

4

It can't be done in general: a good example of a monad that can't do this is the reader (or function) monad. That would require the following function to be definable:

impossible :: (r -> IO a) -> IO (r -> a)

It's not straightforward to prove that a function cannot be implemented. But intuitively, the problem is that whatever IO has to be done in the value returned has to be done before we know what the r parameter is. So impossible readFile would have to yield a pure function FilePath -> String before it knew which files to open. Clearly, at least, impossible can't do what you'd want it to.

Improve this answer

Comments

1

Not all Monads can commute in that way. Edward Kmett's distributive package provides a typeclass Distributive for type constructors that is similar to what you desire (simplified):

class Functor g => Distributive g where distribute :: Functor f => f (g a) -> g (f a) collect :: Functor f => (a -> g b) -> f a -> g (f b)

Default definitions are provided for distribute and collect, written in terms of each other. I found this package by searching hayoo for the desired type signature.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.