Friday, April 9, 2010

Lazy IO with Haskell Monads

Haskell's treatment of imperative programming and side effects is possibly the most derided feature of the language. As someone who's written desktop apps, I'm certainly aware of the inflexibility that Haskell's sandboxing imposes. However, monads happen to mesh very nicely with Haskell's purity and laziness, and what they take away, they give back in other ways.

Suppose for example, you are designing an evil robot that goes out and steals wheels from people's cars. The robot can steal up to 4 wheels from a car, but because it tries to avoid being detected by witnesses (organic or otherwise), it may abort the job prematurely. You need it to fetch 20 wheels a night. No more, no less. Fewer, and you may not be able to pay the bills. More, and the police might start catching on.

For this simple example, you have a function that returns a monadic value:

stealWheelz :: Coordinates -> IO [Wheel]

Then you have some other pre-calculated list of random locations that you want the robot to steal from.

locations :: [Coordinates]

Now here's the funky part. You can define a function takeM, as such:

takeM :: (Monad m) => Int -> [m [a]] -> m [a]
takeM = takeM' []

takeM' :: (Monad m) => [a] -> Int -> [m [a]] -> m [a]
takeM' acc 0 xs = return acc
takeM' acc n [] = return acc
takeM' acc n (x:xs) =
do rs <- x
let rs' = take n rs
n' = n - length rs'
takeM' (acc ++ rs') n' xs

and then your list of tires stolen can simply be:

takeM 20 (map stealWheelz locations)

With this code, the robot will only steal as many tires is as necessary, even if the list of coordinates is of infinite length. Because Haskell is lazy, and IO routines (and all imperative programming that are modelled as monads) are treated as lazy values, you can pass around tasks, with all their arguments bound--even in a strict monad like IO--, and not have to deal with a lot of the usual glue that goes into determining how many results to return.

Btw, that means you can actually pass around the value:

let stealSomeWheelz = map stealWheelz locations

and take results from that list of actions only as you need them. This sort of thing is doable, but *much* less elegant in languages that do not treat actions as if they were values. When you design a language to operate via side effects, then you have to deal with those side effects immediately, as you arise. That means you can't easily reason about it at a higher level, even when you're trying to do simple things like "take the first n results".

As an example, I can apply a filter function to those results, as such:

-- Police commissioner is in town tonight with his Escalade
let stealSomeWheelz = map stealWheelz locations
filter noCaddyWheelzTonight <$> stealSomeWheelz

I discovered this trick when I needed to sanitize the first n queries for a particular area of interest, given a statically-ranked listed of sources. In a more general setting, removing the glue from imperative programming means that I can focus more on what I'm doing, rather than what I'm programming. That's a good thing.

I'd love to see more gems like this. I'm sure someone else has discovered this already, it's in a library somewhere, and I'm just yakking the obvious. I have a feeling that the functional community (and the rest of the world by proxy) is only beginning to discover the value of treating imperative routines as if they were monadic values. Indeed, at the time of this writing, there's a video on HN concerning monads in Clojure.

1 comment:

Unknown said...

takeM = sequence . take