repeat and sequence

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
res <- bar t

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