Skip to content

sequence

Here's a list function that has no pure counterpart in the way that mapM, filterM, zipWithM, and foldM do:

sequence :: Monad m => [m a] -> m [a]

As the name suggests, it captures the idea of sequencing a list of actions in a monad. Another way to describe it is as follows: We're given a list of values of type a, each decorated using the monad m. We want to collect these values of type a in a list and combine their decorations into a single decoration, which we use to decorate the whole list. Here are three simple examples:

First, let's play with the Maybe monad again. We can use sequence to convert a list of Maybes into Maybe a list:

GHCi
>>> sequence [Just 1, Just 2, Just 3]
Just [1,2,3]
>>> sequence [Just 1, Just 2, Nothing, Just 3]
Nothing

If all values in the list are Just something, then the result is Just the list of all these somethings. If there is at least one Nothing in the list, then the result is Nothing. This agrees nicely with our understanding of Maybe as a monad. A list of type [Maybe a] is a list of computations that are each expected to produce a value of type a, but they may also fail, producing Nothing. We want to construct a list containing the results of all these computations, but producing this list fails if producing even one of its elements fails.

So our earlier implementation of the listDiv function,

safeDiv :: Double -> Double -> Maybe Double
safeDiv _ 0 = Nothing
safeDiv p q = Just $ p / q

listDiv :: [(Double, Double)] -> Maybe [Double]
listDiv = mapM (uncurry safeDiv)

could also have been expressed as

listDiv :: [(Double, Double)] -> Maybe [Double]
listDiv = sequence . map (uncurry safeDiv)

Instead of directly applying uncurry safeDiv to each pair in the list, we first transform this list into a sequence of function applications that may or may not succeed, using plain old map, and then we execute all these function applications using sequence, checking whether each of them succeeds.

GHCi
>>> :{
  | safeDiv :: Double -> Double -> Maybe Double
  | safeDiv _ 0 = Nothing
  | safeDiv p q = Just $ p / q
  |
  | listDiv :: [(Double, Double)] -> Maybe [Double]
  | listDiv = sequence . map (uncurry safeDiv)
  | :}
>>> listDiv [(3,4),(1,2),(0,3)]
Just [0.75,0.5,0.0]
>>> listDiv [(3,4),(1,2),(3,0),(0,3)]
Nothing

In general, we have that

mapM     f xs    = sequence $ map     f xs
zipWithM f xs ys = sequence $ zipWith f xs ys

for any monad. It doesn't matter whether we map our effectful function f over the elements in xs directly or whether we first transform xs into a list of function applications using the pure map function, and then we execute these function applications in order using sequence.

The second example involves the IO monad discussed in the next section. We can collect a sequence of IO actions in a list and then execute them:

GHCi
>>> sequence [putStrLn "Hello", putStrLn "world!"]
Hello
world!
[(),()]

This output needs some explanation. The first two lines of output are the effects of running the two actions in the list:

GHCi
>>> putStrLn "Hello"
Hello
>>> putStrLn "world!"
world!

Each of these actions returns () because putStrLn has the type

putStrLn :: String -> IO ()

Thus, sequence [putStrLn "Hello", putStrLn "world!"] has the type [()], and GHCi dutifully reports the list of the two return values of these two function calls [(), ()]. Why don't we see two lines of output when running just putStrLn "Hello" then? Like this:

GHCi
>>> putStrLn "Hello"
Hello
()

That's because GHCi knows that () is the same as void in C. It provides no information. Thus, whenever we evaluate an action of type IO () in GHCi, GHCi does not print the output. GHCi cannot simply ignore the return value when the result is a list of ()s, because [(), ()] and [(), (), ()] are different lists. We may care about which list our function application produces. In the next subsection, we will discuss mapM_, foldM_, zipWithM_, and sequence_. They all behave exactly as their counterparts without underscores, but they all have the return type m (), where m is our monad. The idea is that we want to sequence some actions only for their effects; we don't care about the return values. Thus,

GHCi
>>> sequence_ [putStrLn "Hello", putStrLn "world!"]
Hello
world!

As a final example, let's once again look at generating the list [1..n] using the State monad. We will use the following action:

count :: State Int Int
count = do
    val <- get
    put $ val + 1
    return val

count returns the current value of the counter that is our state but before doing so, we increment this counter, so the next call to count returns the next number. To generate the list [1..n], we can sequence n applications of count:1

GHCi
>>> :{
  | count = do
  |     val <- get
  |     put $ val + 1
  |     return val
  | :}
>>> evalState (sequence $ replicate 10 count) 1
[1,2,3,4,5,6,7,8,9,10]

The implementation of sequence is fairly straightforward. It's rather similar to the implementation of mapM:2

sequence :: Monad m => [m a] -> m [a]
sequence []     = return []
sequence (f:fs) = do
    x  <- f
    xs <- sequence fs
    return $ x : xs

Instead of applying the same action to a bunch of list elements, the list elements themselves are the actions to be performed.

  1. We can make this simpler using the monadic equivalent of replicate, called replicateM:

    GHCi
    >>> evalState (replicateM 10 count) 1
[1,2,3,4,5,6,7,8,9,10]

    Just as we have

    mapM     f xs    = sequence $ map     f xs
zipWithM f xs ys = sequence $ zipWith f xs ys

    we have

    replicateM n f = sequence $ replicate n f
     ↩

  2. We can once again exploit that every monad is an applicative function to obtain the more concise implementation

    sequence :: Monad m => [m a] -> m [a]
sequence []     = return []
sequence (f:fs) = (:) <$> f <*> sequence fs
     ↩