Sunday, December 30, 2012

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 (runReaderTrunWriterT) 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.