Saturday, November 30, 2013

Monday, November 18, 2013

My solution to the Twitter waterflow problem

The Twitter waterflow problem originated in this post. After becoming aware of the existence of functional solutions in this other post, I decided to roll my own in Haskell before looking at them.

It turned out to be more tricky than I had expected. The first version of the algorithm was hideously ugly and verbose, and I couldn't make it to work. I tried a new approach and came up with the following:

I haven't tested it extensively but I think it works.

I "compress" consecutive columns of equal height, so instead of working with a list of heights, I work with a list of (height,width) pairs. The initial list with uncompressed columns is created in the (zip l (repeat 1)) expression.

I traverse the list from left to right, carrying an accumulator parameter for the volume, and also an axiliary list of the "high" columns visited so far. These columns can potentially enclose water if another sufficiently high column is encountered on the other side of a "valley".

The algorithm ensures that the columns in the auxiliary list (a stack, really) are strictly increasing in height, and have all been "compressed".

Lines 3-4 purge columns that go "uphill" from the left border, since these columns can't possibly contain a valley. Once we find the first "peak", we put it into the auxiliary list.

Line 7 compresses "valley floors".

Line 8 identifies "valleys" whose floors have already been compressed. We find how much water that portion of the valley will hold by multiplying the width of the floor with the height of the lowest wall. We add the volume to the accumulator and then fill that portion of the valley with concrete (so to speak) to avoid double-counting that volume in future iterations.

Friday, May 31, 2013

Haskell equivalents of some Clojure forms

While trying to learn Clojure, I keep confusing doall, dorun, and doseq. What are their differences, and when to use each one?

The functional language I know best is Haskell, so I will find what Haskell functions correspond to the Clojure ones, using Hoogle.

doall. 


The documentation says:
When lazy sequences are produced via functions that have side effects, any effects other than those needed to produce the first element in the seq do not occur until the seq is consumed. doall can be used to force any effects. Walks through the successive nexts of the seq, retains the head and returns it, thus causing the entire seq to reside in memory at one time.  
Ok, we have a list where each element is produced through a side effect. Using doall we perform all these effects "up front" and get the whole list as a result.

In Haskell, values which are obtained through side effects are "tagged" with the IO monad, to distinguish them from pure values. A value of type IO a could be understood as "a description of a program that, when run, produces a value of type a".

We want a function with a type like this:
[IO a] -> IO [a] 
[] is the type constructor for lists. -> means a function from some type to another. For simplicity, in this post we only deal with lists whose elements are all of the same type.

We put the signature in Hoogle, we find the following
sequence :: Monad m => [m a] -> m [a] 
Evaluate each action in the sequence from left to right, and collect the results.
The type is more general but, when m is IO, this is the function we are looking for.

dorun. 


The documentation says:
When lazy sequences are produced via functions that have side effects, any effects other than those needed to produce the first element in the seq do not occur until the seq is consumed. dorun can be used to force any effects. Walks through the successive nexts of the seq, does not retain the head and returns nil.
In Haskell, functions which are executed only for side effects return values of type (). There is only one such value, also named (). It's roughly similar to void in C and Java.

Let's then search for the signature
[IO a] -> IO ()
We find
sequence_ :: Monad m => [m a] -> m () 
Evaluate each action in the sequence from left to right, and ignore the results.
The trailing underscore is a notational convention. It means that this is a function that behaves like the one without the underscore, but ignores the return value.

doseq. 


The documentation says:
Repeatedly executes body (presumably for side-effects) with bindings and filtering as provided by "for". Does not retain the head of the sequence. Returns nil.
Ok, it seems that now the values in the input list are "pure", but we want to apply an effectful function to each one of them. And we do not care about the return value.

So we must search Hoogle for something like
[a] -> (a -> IO b) -> IO () 
We find
forM_ :: Monad m => [a] -> (a -> m b) -> m ()
So that's it. doall is sequence, dorun is sequence_, doseq is forM_. I won't confuse them anymore!

A good introduction to Haskell IO can be found here.