Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Unsequence Monad function within Haskell

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.

like image 869
AJF Avatar asked Dec 07 '14 13:12

AJF


People also ask

How do you make a monad in Haskell?

To create a monad, it is not enough just to declare a Haskell instance of the Monad class with the correct type signatures. To be a proper monad, the return and >>= functions must work together according to three laws: (return x) >>= f ==== f x.

What is a monad in Haskell?

What is a Monad? A monad is an algebraic structure in category theory, and in Haskell it is used to describe computations as sequences of steps, and to handle side effects such as state and IO. Monads are abstract, and they have many useful concrete instances. Monads provide a way to structure a program.

Is list a monad Haskell?

Lists are a fundamental part of Haskell, and we've used them extensively before getting to this chapter. The novel insight is that the list type is a monad too! As monads, lists are used to model nondeterministic computations which may return an arbitrary number of results.

What is a monadic function?

A monadic function is a function with a single argument, written to its right. It is one of three possible function valences; the other two are dyadic and niladic. The term prefix function is used outside of APL to describe APL's monadic function syntax.


2 Answers

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.

like image 121
danidiaz Avatar answered Oct 22 '22 20:10

danidiaz


It is indeed not possible to create an unsequence function using monads alone. The reason is:

  1. You can safely and easily create a monadic structure from a value using return.
  2. However, it is not safe to remove a value from a monadic structure. For example you can't remove an element from an empty list (i.e. a function of the type [a] -> a is not safe).
  3. Hence we have a special function (i.e. >>=) which safely removes a value from a monadic structure (if one exists), processes it and returns another safe monadic structure.

Hence it is safe to create a monadic structure from a value. However it is not safe to remove a value from a monadic structure.

Suppose we had a function extract :: Monad m => m a -> a which could “safely” remove a value from a monadic structure. We could then implement unsequence as follows:

unsequence :: Monad m => m [a] -> [m a]
unsequence = map return . extract

However, there's no safe way to extract a value from a monadic structure. Hence unsequence [] and unsequence Nothing will return undefined.

You can however create an unsequence function for structures that are both monadic and comonadic. A Comonad is defined as follows:

class Functor w => Comonad w where
    extract   :: w a -> a
    duplicate :: w a -> w (w a)
    extend    :: (w a -> b) -> w a -> w b

    duplicate = extend id
    extend f = fmap f . duplicate

A comonadic structure is the opposite of a monadic structure. In particular:

  1. You can safely extract a value from a comonadic structure.
  2. However you can't safely create a new comonadic structure from a value, which is why the duplicate function safely creates a new comonadic structure from a value.

Remember that the definition of unsequence required both return and extract? You can't safely create a new comonadic structure from a value (i.e. comonadic structures don't have return). Hence the unsequence function is defined as follows:

unsequence :: (Comonad m, Monad m) => m [a] -> [m a]
unsequence = map return . extract

Interestingly sequence works on simply monadic structures. So via intuition you might assume that unsequence works on simply comonadic structures. However it not so because you need to first extract the list from the comonadic structure and then put each element of the list into a monadic structure.

The general version of the unsequence function converts a comonadic list structure to a list of monadic structures:

unsequence :: (Comonad w, Monad m) => w [a] -> [m a]
unsequence = map return . extract

On the other hand the sequence function works on simply monadic structures because you are just folding the list of monadic structures into a monadic list structure by chaining all the monads:

import Control.Monad (liftM2)

sequence :: Monad m => [m a] -> m [a]
sequence = foldr (liftM2 (:)) (return [])

Hope that helps.

like image 45
Aadit M Shah Avatar answered Oct 22 '22 20:10

Aadit M Shah