process + pipes = process-streaming

There are a number of good libraries for launching external processes already in Hackage. Basic libraries like process, and libraries that build on top of it like shelly and process-conduit (there is also module System.IO.Streams.Process from io-streams).

An official pipes-process package hasn't come out yet. After working recently with Ruby's Open3 package, and becoming inspired by this thread in the Haskell Pipes Google group, I decided to cobble together my own experiment. process-streaming is the result (git repo here).

I wanted to scratch a number of itches:

• To my knowledge, neither shelly nor process-conduit provide concurrent streaming access to both the stdout and the stderr of a process, which is sometimes necessary. (shelly does provide direct access to the handles, but you have to orchestrate the concurrency by yourself.)
• shelly and process-conduit use exceptions for signaling errors. This makes for simpler signatures. I wanted to test if a purely Either-based approach to errors could work without making the signatures excessively complicated.
• Combining stdout with stderr is a frequent use case with some subtleties in the implementation. You have to be careful not to mangle lines, and also ensure that both streams are drained continuously (because otherwise you can get yourself into a blocking scenario).
• Besides using plain Consumers, it should be easy to consume stdout and stderr using folds from Pipes.Prelude (and pipes-text and pipes-bytestring and pipes-group) and also parsers from the pipes-parse package. And it would be nice if two parsers could be run in parallel over the same Producer.

The haddock documentation for the System.Process.Streaming module is here. A tutorial with some examples can be found here.

If nothing else, this experiment has served me to understand the pipes ecosystem a little better. I really like the pipes-text approach for handling decoding leftovers (putting them in the return values of pipes) and the FreeT-based approach for parsing lines without never having to keep a whole line in memory at any time.

Compiled Heist insight, with no Snap in sight

A few weeks ago, I wrote a tutorial on compiled Heist at School of Haskell, but for some reason I forgot to post the link. Here it is.

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.

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.

Evaluating probabilistic cellular automata is comonadic, too! (part II)

Part I is here. The complete code is here.

We have defined our CA datatype and a local update rule for it. Since our CA is probabilistic, the update rule has a monadic effect in the Rand monad.

To perform a "global update" of the CA, we pass the current CA state and the local update rule to the extend function of Comonad:

extend localRule ca :: EnvT Probs U (Rand StdGen Bool)

The returning type is almost, but not quite, what we need. We now have a CA in which each cell is a monadic random effect. What we would like is to have the whole CA inside the Rand monad, so that a single call to runRand or evalRand gives us a value of EnvT Probs U Bool. We need a way to aggregate the monadic effects of each singular cell into a global monadic effect for the whole CA.

This is similar to the problem of transforming a list of IO actions into an IO action that returns a list. List is an instance of Traversable, so we can use the sequence function on it. Likewise, we must make our type U an instance of Traversable.

The easiest way is to have the instance derived for you automatically. Just use the DeriveTraversable extension and add Traversable to the deriving clause when declaring the U datatype.

But it doesn´t work. More precisely, it works only for one half of the universe! I wanted to print the CA's new state, 8 cells around the center (the showca function is defined in the gist):

    putStrLn . showca 8 
             . lower 
             . flip evalRand (mkStdGen 7) 
             . sequence 
             $ extend localRule ca

This printed only the left side of the universe. When it tried to print the first cell to the right, the whole computation just hanged. Why?

sequence is defined in terms of traverse. The default definition provided by the compiler first traverses the left side of the universe, then the center cell and the right side last. The StdGen generator is threaded throughout. But each side is infinite; when traversing the left side, we can get the updated generator to use on the right side only after an infinite number of steps. Laziness doesn't help here, because there is a data dependency.

This stumped me for a while, but finally I came up with an alternate version of traverse which doesn't suffer this problem:

    instance Traversable U where
        traverse f (U lstream focus rstream) = 
            let pairs =  liftA unzip 
                       . sequenceA . fmap (traversepair f) 
                       $ zip lstream rstream 
                traversepair f (a,b) = (,) <$> f a <*> f b
                rebuild c (u,v) = U u c v
            in rebuild <$> f focus <*> pairs

The trick is to zip the two streams together before traversing them, and unzip them afterwards inside the monad. This way, accessing the value in the first cell to the right doesn't require an infinite number of steps.

That solved, there is still one problem left. When we use evalRand to obtain the new state of the CA, we don't get an updated generator alongside it. And we can't use runRand to get it because the CA is potentially infinite. As we lazily consume the returned CA state, the generator we supplied is still used "under the hood" for generating new values. If we feed the updated generator returned by runRand to the following iteration, the whole computation would hang, again.

Fortunately, the MonadRandom class provides a getSplit operation which "bifurcates" a generator. At each iteration, we split the generator, throwing one half into the black hole of evalRand, and keeping the other half for the next iteration. We now know enough to define a function that, given a generator and an initial state of the CA, produces a lazy stream of all the succesive states of the automaton:

evolve :: EnvT Probs U Bool -> Rand StdGen (EnvT Probs U Bool)
evolve ca = sequence $ extend localRule ca

history :: StdGen -> EnvT Probs U Bool -> Stream (EnvT Probs U Bool)
history seed initialca =     
   let unfoldf (ca,seed) = 
           let (seed',seed'') = runRand getSplit seed 
               nextca = evalRand (evolve ca) seed'
           in  (nextca,(nextca,seed''))
   in unfold unfoldf (initialca,seed)

That's all folks! Happy New Year.

Edit: I wasn't sure of the correctness of my Traversable instance, so I posted a question on Stack Overflow.

Evaluating probabilistic cellular automata is comonadic, too! (part I)

I'm trying to develop my intuition for comonads and comonad transformers in Haskell. This article in A Neighborhood of Infinity helped me grasp the basic concepts, so I decided to continue in the same vein, and explore how to handle simple probabilistic cellular atomata like the ones described in this link.

Let's start by adapting sigfpe's datatype to make it use the standard Comonad typeclass from the comonad package:

    data U x = U (Stream x) x (Stream x) deriving (Functor,Foldable)

    right (U a b (c:>cs)) = U (b:>a) c cs
    left  (U (a:>as) b c) = U as a (b:>c)

    instance Comonad U where
       extract (U _ b _) = b
       duplicate a = U (tail $ iterate left a) a (tail $ iterate right a)

I have used the Stream datatype (from the streams package) instead of lists, to actually enforce that the universe is infinite in both directions.

Now, to allow probabilistic "evolution" of the CA, we need two things:

• Some way of storing and accessing the probability parameters. Think of them as the "basic constants" of the CA's universe.
• Some way of generating random values that plays well with the Comonad instance. Remember that randomness is a kind of monadic effect.

The first one is easy, we'll just use the EnvT comonad transfomer. This transformer attaches "environment values" to comonadic values. The environment can be later extracted from the transformed comonadic value using the ask function.

Let's add probabilities to our U datatype. We pass a vanilla U value to the EnvT constructor, along with a probabilities tuple:

    type Probs = (Float,Float,Float,Float)

    ca :: EnvT Probs U Bool
    ca = EnvT (0.0,0.6,0.7,0.0) $ U (repeat False) True (repeat False)

    probs :: Probs
    probs = ask ca
 
Easy as a pie! Notice the following: with monads, there is a uniform interface to "put things in" (return) but the interfaces to "get things out" are specialized (runReaderT, runWriterT) or don't even exist (like with IO). With comonads, there is a uniform interface to "get things out" (aptly named extract) but the interface to "put things in" depends on the comonad (the EnvT constructor in this case).

Let's now define a probabilistic local update rule which calculates the next state of a cell from the state of its neighbours. We are using the MonadRandom package:

    localRule :: EnvT Probs U Bool -> Rand StdGen Bool
    localRule ca =
        let (tt,tf,ft,ff) = ask ca
            black prob = (<prob) <$> getRandomR (0,1)
        in case lower ca of
            U (True:>_) _ (True:>_) -> black tt
            U (True:>_) _ (False:>_) -> black tf
            U (False:>_) _ (True:>_) -> black ft
            U (False:>_) _ (False:>_) -> black ff

We already know what ask does. But what does lower do? lower is the dual of lift. lift adds new effects to a base monadic value; lower strips one layer of a transformed comonadic value and returns the comonadic value underneath. Here we use it to access the base U value and pattern match against it.

We are almost there. Having defined localRule, we can use it together with extend to perform a "global update" that transforms an EnvT Probs U Bool into an EnvT Probs U (Rand StdGen Bool). But now we've hit a bit of a block. What we really want to get is a Rand StdGen (EnvT Probs U Bool) which we could then "run" using evalRand and obtain the next state of the CA. How to do this is explained in the next post.

A gist with the Haskell code can be found here.

Part II of this post is here.