For loops in Haskell
Functional programmers often seem to complain that for loops are better off done with maps, and that, in any case, they're just degenerate cases of the same thing, as all imperative constructs can be created in a fully functional way...
That being the claim, I thought it might be a fun exercise to try to implement for loops in Haskell.
First of all, I tried to work out the type, and guessed at:
> for :: a -> (a->Bool) -> (a->a) -> (a-> IO ()) -> IO ()
Where a usage might be something like:
> for 1 (<10) (+1) (\x -> putStr $ show x)
First of all, I tried the “straightforward” recursive version, and got as far as compiling:
> for i p pp f =
> do if p i
> then
> (f i)
> -- but now what?
> else
> return ()
The do‘s and the return are of course there pretty much at random, by adding, removing, and moving things till I could get it to compile. But it does work, partially, certainly it gets through a single iteration! I tried various options to recurse, and thought that something like this should work.
> for (pp i) p pp f
But it doesn't, and ghc‘s error messages are typically cryptic. Half an hour later I was about to give up, and then remembered the iterate function. After which the following higher order version sort of wrote itself.
We construct the list of iterators:
> iterate pp i
But of course we only need to take them while the predicate is true
> takeWhile p
And we need to sequence the actions
> mapM_ f
(OK, I remembered that someone had pointed mapM_ at me and found it in an earlier blog entry...)
Leading to the following definition:
> for i p pp f = mapM_ f $
> takeWhile p $
> iterate pp i
OK, so this version of a for loop doesn't have a last keyword to break out of the loop early, but otherwise it does pretty much what you'd expect. I don't know whether the earlier thunks (iterated values of i that have already been used) will be kept by ghc even after they have already been used or not, but that's an implementation / optimization detail.
I'm not sure why the recursive version seems harder to write: I guess because I don't understand what the do-notation is doing. (Generally speaking, programming tasks tend to be easier when you actually know what the code is doing rather than just trusting the voodoo.)
As a final note, this is the type that ghc infers from this definition (more general than the one I'd started with).
> for :: (Monad m) => a -> (a -> Bool) -> (a -> a) -> (a -> m b) -> m ()
Comments
Also, may we use this as an exercise in the wikibook?
Oh, I haven't got around to setting a CC license, but yes, in general this blog would be Attribution-ShareAlike, does that work for the wikibook?
If you put a do after the then. You can write it like this to get rid of the cryptic error messages:
for i p pp f =
do if p i
then do
(f i)
for (pp i) p pp f
else
return ()
flip mapM_ [1..10] $ \x -
flip mapM_ [1..10] $ \x -> putStrLn $ show x
for i p pp f =
if p i
then
(f i) >> for (pp i) p pp f
else
return ()
Another approach is to realise that for loops can be expressed using while loops. So you take the 'until' function and make that monadic:
untilM :: Monad m => (a -> m Bool) -> (a -> m a) ->a -> m a
untilM p f x = do
b <- p x
if b then return x
else do { x' <- f x; untilM p x' f }
(Note that it's (a -> m Bool) rather than (a -> Bool) - you have to do this to follow the M-suffix naming convention correctly, and besides, it lets us make side-effecting tests if we need to. If you want a pure test, just use 'return' to take it into the monad.) Then you naturally get a 'while' loop like so:
whileM :: Monad m => (a -> m Bool) -> (a -> m a) -> a -> m a
whileM p f x = forM (liftM not . p) f x
Your 'for' function is then:
for i p pp f = whileM (return . p) (\n -> do {f x; return (pp x)}) i >> return ()
Which has the advantage from a performance point of view of not creating and then destroying a list.
The suggestion about whileM, and the datastructure creation and destruction is interesting, and is something I don't yet understand deeply enough to reason about! Thanks for the pointer.