It seems to happen all the time to me. I ask a question on haskell-cafe and a get an answer involving at least one function I’ve never heard of before. This time around it was sequence (or rather sequence_) and repeat.

I took a look at Hoogle of course but found it as sparse as always so I decided to play a little.

First repeat:

> :t repeat
repeat :: a -> [a]
> repeat 4
[4,4,4,4,4,4,4,4,4,4,4,4,4,...

The list repeats until I interrupt it by pressing Ctrl-C. Let’s limit the list to 5 items.

> take 5 $ repeat 2
[2,2,2,2,2,]

Simple enough. Can I do “IO stuff” and stuff it in the list?

> take 5 $ repeat getChar
-- error because there's no instance of Show (IO Char)

Ah, that’s another one of those pesky little things when using GHC interactively. I’m guessing that there’s a reason for the response mail using sequence_…

> :t sequence_
sequence_ :: (Monad m) => [m a] -> m ()
> :t sequence
sequence_ :: (Monad m) => [m a] -> m [a]

Combining them seems like a good idea

> sequence . (take 5 ) . repeat $ getChar
abcde"abcde"

Brilliant. However, to make sure I really understand what’s happening I wanted to write the functions myself. First my repeat:

foo x = x : foo x

Making infinite lists in Haskell is quite simple :-) Replacing repeat by foo in the code snippets above shows that foo indeed exhibits the same behaviour as repeat.

It proved a little more difficult to get the behaviour of sequence. I usually find it easiest to try for a recursive function first. I find that using higer-order functions is a lot easier if I first have grasped a recursive solution. Here’s my recursive version of sequence:

bar [] = return []
bar (h:t) = do
    head <- h
    res <- bar t
    return $ head : res

The termination case is simple. The recursive step is straight forward as well, simply pull out the values from the IO monad in order (that is important since monad’s do impose ordering) and at the end put together the list and return it in the monad.

Looking at that recursive definition it’s not unreasonable to suspect it’s possible to use foldM to define another variant of sequence. Given foldM’s type ((Monad m) => (a -> b -> m a) -> a -> [b] -> m a) it’s obvios that in this case a is a list (e.g. [Char]) and b is a monad (e.g. IO Char). This means that the first argument should be of type (Monad m) => [t] -> m t -> m [t] and something like qux here seems to fit the bill:

qux l n = do
    v <- n
    return $ v : l

It’s basically an abridged version of bar from above. It could also be written as a one-line lambda expression like this \ l n -> n >>= (\ v -> return $ v : l). The termination case remains unchanged so a sequence implemented using foldM ought to look like this:

bar2 = foldM (\ l n -> n >>= (\ v -> return $ v : l)) []

Unfortunately this definition has a small bug, the resulting list is reversed. Lifting reverse into the monad takes care of that though:

bar2 l1 = liftM reverse $ foldM (\ l n -> n >>= (\ v -> return $ v : l)) [] l1

It seems both bar and bar2 mimick the behaviour of sequence. Even to the level that they are “un-lazy”:

> (take 5) . sequence . repeat $ getChar
abcdefg... (ad infinitum)

I’ll leave adding laziness to people who are smarter than me.