list - Unsequence Monad function within Haskell

Question

I'm having some real trouble designing the counterfunction of Haskell's sequence function, which Hoogle tells me doesn't yet exist. This is how it behaves:

ghci> sequence [Just 7, Just 8, Just 9]
Just [7,8,9]
ghci> sequence [getLine, getLine, getLine]
hey
there
stack exchange
["hey","there","stack exchange"] :: IO [String]

My problem is making a function like this:

unsequence :: (Monad m) => m [a] -> [m a]

So that it behaves like this:

ghci> unsequence (Just [7, 8, 9])
[Just 7, Just 8, Just 9]
ghci> sequence getLine
hey
['h','e','y'] :: [IO Char] --(This would actually cause an error, but hey-ho.)

I don't actually know if that's possible, because I'd be escaping the monad at some point, but I've made a start, though I don't know how to set a breakpoint for this recursive function:

unsequence m = (m >>= return . head) : unsequence (m >>= return . tail)

I realise that I need a breakpoint when the m here is equal to return [], but not all monads have Eq instances, so how can I do this? Is this even possible? If so, why and why not? Please tell me that.

Answer 1

You can't have an unsequence :: (Monad m) => m [a] -> [m a]. The problem lies with lists: you can't be sure how may elements you are going to get with a list, and that complicates any reasonable definition of unsequence.

Interestingly, if you were absolutely, 100% sure that the list inside the monad is infinite, you could write something like:

unsequenceInfinite :: (Monad m) => m [a] -> [m a]
unsequenceInfinite x = fmap head x : unsequenceInfinite (fmap tail x)

And it would work!

Also imagine that we have a Pair functor lying around. We can write unsequencePair as

unsequencePair :: (Monad m) => m (Pair a) -> Pair (m a)
unsequencePair x = Pair (fmap firstPairElement x) (fmap secondPairElement x)

In general, it turns out you can only define unsequence for functors with the property that you can always "zip" together two values without losing information. Infinite lists (in Haskell, one possible type for them is Cofree Identity) are an example. The Pair functor is another. But not conventional lists, or functors like Maybe or Either.

In the distributive package, there is a typeclass called Distributive that encapsulates this property. Your unsequence is called distribute there.