“Haskell Doesn’t Have Loops”

Among the first thing any prospective Haskeller learns is that “Haskell doesn’t have loops.” You know what I say to that?

Challenge Accepted

Challenge Accepted.

While it’s true that loops are not a primitive control structure in Haskell like they are in imperative languages, that doesn’t mean we can’t add them. But what should a loop look like? In C, a while loop looks like this:

while (some_predicate() != TRUE) { do_stuff(); }

It’s basically the same in any C-like language; first, you type the type of loop (while, in this case), then you type some predicate that evaluates to a boolean value, then on the next line, an arbitrary block of code.

I feel that it would be in poor taste to just define a function while that takes another function that represents the block of code to execute. It feels out of line with the spirit of the problem. Luckily for us, Haskell’s do notation has a very “arbitrary block of code” feel to it. But that requires us to use a monad…

Which brings us to the root of the issue: what exactly do we *do* in loops? Basically, while the predicate is false, we mutate some state, then test the predicate again. If the predicate is still false, we mutate some more state until it evaluates true. The key word there is state.

Take a look at my sample loop above. The loop calls two functions: some_predicate, and do_stuff(). Neither function takes any arguments. If this were Haskell, then we’d have a problem, because the loop would never exit. If a function always returns the same result given the same input, then a function with no input will always only return one thing. some_predicate would always either return True (resulting the the loop not being entered), or False, resulting in an infinite loop. However, in C this loop probably works fine. This is because C has state.

To this end, my Haskell loop must operate on a State monad. Now, with this out of the way, let’s jump to the implementation!

The Implementation

So, how would we implement a loop in Haskell? I think a good source of inspiration here is the Monad typeclass. Monads have a very “language-feature” feeling to them, but they are not primitives. Monads are a typeclass, some functions, and some data types. Similarly, I’ve created a Loop typeclass:

class Loop a where exec :: a -> a

The Loop typeclass is very simple. It defines one function, exec that takes a loop, and returns another loop of the same type. Different types of loops behave differently, so it’s up to the implementor to determine how the loop should function. For this example, I’ve implemented the while loop. Here is my While type:

data While a = While {whilePred :: (a -> Bool), whileState :: a, whileBody :: State a ()}

My While type has three fields. The whileState field is a state value for use by the loop’s state monad. The whileBody field is the State monad itself. Finally the whilePred field is a predicate function that is used to determine if the loop should terminate.

Next, we have an implementation for class Loop:

instance Loop (While a) where exec w = let predicate = (whilePred w) (whileState w) s' = execState (whileBody w) (whileState w) w' = While {whileState = s', whilePred = (whilePred w), whileBody = (whileBody w)} in case (predicate) of True -> w False -> exec w'

It’s a little verbose, but it’s not too bad when you break it down. The meat of the function is in the case statement: we test the predicate, by calling whilePred on whileState. If the predicate returns True, we return the current While object. If it evaluates False, we iterate once by calling execState using whileState as the initial state, and whileBody as the State monad. When that’s done, we construct a new While object with the old State monad, old predicate function, and new state, and then recursively call exec. This continues until the predicate evaluates True. Like any good while loop, this could potentially go on forever.

So, where does that leave us? We have a while loop type, and a function to “run” the loop. So, as it stands, we have to build the While, then call exec on the While, then finally call whileState on the While to get the result. Doesn’t really feel like a C-like while loop, does it? Well, we’re not done yet. Let’s define one last function:

while :: a -> (a -> Bool) -> (State a ()) -> a while s p b = whileState $ exec (While {whileState = s, whilePred = p, whileBody = b})

This function is where the magic happens. This function approximates the while statement from C. By calling this function, we can perform a “while loop” that looks like so:

while initialState predicateFunction $ do oldState <- get newState <- mutate oldState put newState

The while function will return the final mutation of initialState. Here’s an example main function:

main = do res <- return $ while [] (\a -> (length a) == 10) $ do old <- get new <- return $ old ++ [(length old)] put new sequence_ $ map (putStrLn . show) res

In this example, we perform a while. Our initial state is an empty list. Our predicate tests that the length of the list is equal to 10. Then we enter our State block where we append the length of the list to the end of the list. Finally, after the loop exits we map (putStrLn . show) over the resulting list to print each element of the list to the console. The following will be displayed:

0 1 2 3 4 5 6 7 8 9

Ladies and Gentlemen, it walks like a duck, and quacks like a duck. Therefore, it must be a duck.

Trackbacks / Pingbacks

  1. Again, This Time In Reverse! | Doing My Programming... - September 5, 2014

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: