repeat and sequence
- Magnus Therning
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
:
= x : foo 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
:
= return []
bar [] :t) = do
bar (hhead <- h
<- bar t
res 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:
= do
qux l n <- n
v 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:
= foldM (\ l n -> n >>= (\ v -> return $ v : l)) [] bar2
Unfortunately this definition has a small bug, the resulting list is reversed. Lifting reverse
into the monad takes care of that though:
= liftM reverse $ foldM (\ l n -> n >>= (\ v -> return $ v : l)) [] l1 bar2 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.