CODEWITHSUNDEEP
haskellmonads
Tachy
Tachy

Reputation: 1021

Questions on Haskell's sequence function

I've been going through UPenn's CS194 and currently on Lecture 7, Monads. I thought I was getting an okay handle on Monads until I saw the implementation of the sequence function and started poking around.

sequence :: Monad m => [m a] -> m [a]
sequence [] = return []
sequence (ma:mas) = do
  a  <- ma
  as <- sequence mas
  return (a:as)

This seems intuitive at first glance, but as I delved into it, I came up against a bunch of questions:

  1. The type of return [] is : return [] :: Monad m => m [t] . Earlier in the same lesson, the Monad instance for [] defines return as: return x = [x]. How did this lead to the type signature m [t] for return []?

  2. a <- ma . What is type of a here, assuming I called sequence with [Just 5, Just 9] ? By the Monad instance definition of Maybe: 

    Just x  >>= k = k x

    I would think x, or a in the case of sequence would be a Num. But it must really be a Monad of Num. How did x become a monad of Num here when Just x from the instance definition of Maybe seems to be pulling x out of Just?

Upvotes: 4

Views: 4887

Answers (1)

Sebastian Redl
Sebastian Redl

Reputation: 72044

The type of return [] is Monad m => m [t] - here, the [] is an instance of [t], i.e. a list of some arbitrary type (the type is arbitrary since it's the empty list, so there are no instances of the type anyway). If you substitute the list monad, the type of return is t -> [t], and return [] yields [[]]. The confusing thing is that both the monad and the contained value are lists.

The type of return in general is Monad m => t -> m t. If you specialize for lists, you get t -> [t], so the list type takes the place of m. The special syntax for lists makes this a bit more confusing; if you use the maybe monad instead, specialized return has the type t -> Maybe t, so you can see clearly how the m was replaced by Maybe. In the maybe monad, the type of return [] is Maybe [t]: the monad now wraps some list.

The type of return [] is Monad m => m [t], a list wrapped by the monad. If you use the list monad, you substitute the m with the list constructor and get [[t]], which is the right type.

As for the second question, why do you think that a must be a monad?

Edit after clarification in comment

In the example call sequence [Just 5, Just 9] you gave, the monad is maybe, not list; that list is an ordinary list as required by the type of sequence. Remember that it takes a [m a] as input. As you supply a Num a => [Maybe a] as input, that makes the monad Maybe, and the result type is Num a => Maybe [a]. sequence turns a list of optional values into an optional list. This means that in the first case of sequence, the return [] applies to Maybe's return and means Just []. This makes sense, as calling sequence [] in the maybe monad should return Just [].

Now, in the do-block of the second case, we have a bunch of variables, and it helps to figure out the type of each. I'll do that for the concrete case of Maybe and Int for the numbers; getting the generic types comes down to simply replacing Maybe with m and Int with a in all these cases, and adding constraints.

The entire input has type [Maybe Int]. The second case pattern-matches this with (ma:mas), picking the first element off the list. So ma has the type of the list's element, Maybe Int, whereas mas is the remainder of the list and thus has type [Maybe Int].

In the do-block, ma is unwrapped with the arrow notation, and the result is a, whose type is therefore that of ma with the monad stripped, i.e. Int.

Then, sequence is called recursively with the rest of the input, mas, which has type [Maybe Int]. Substituting into the type of sequence shows that the result type is Maybe [Int]. This value is again unwrapped, so the target as has type [Int].

In the last line, a (type Int) is prepended to as (type [Int]), yielding a longer list ([Int]). The result is given to return, which wraps it in a Just (Maybe [Int]) to match the result type of sequence.

By the way, if you want to track the types through do-blocks in detail, you should first desugar them to normal composition with lambdas.

Upvotes: 4

Related Questions