# A State Monad with dynamically-typed state

Haskell’s
standard State monad types allow the programmer to define a computation
that works with some state in a way that looks and feels similar to using
mutable state in an imperative language. However these State monad types are
limited in that *the type of the state cannot change* during the computation.

Normally this is fine, but what if we really wanted to use the mechanics of a state monad to pass some state value that changed type, e.g. some mutually- recursive tree structure we would like to traverse?:

```
data EvenBranch = EBranch OddBranch Int OddBranch
data OddBranch = OBranch EvenBranch EvenBranch
| Nil
```

Well it turns out its not only possible, but relatively simple to use the existing MonadState types with something like a dynamically-typed state, thanks to a couple really fascinating standard Haskell libraries:

## Introducing `Typeable`

and `Dynamic`

The first piece of the puzzle is the
Data.Typeable library.
The library provides polymorphic functions for
extracting *type information* (in the form of a data type called a `TypeRep`

)
from any object in the `Typeable`

type class.

Try this out:

```
Prelude Data.Dynamic> :t typeOf
typeOf :: (Typeable a) => a -> TypeRep
Prelude Data.Dynamic> typeOf 1
Integer
Prelude Data.Dynamic> typeOf 1 == typeOf 'a'
False
Prelude Data.Dynamic> typeOf 1 == typeOf 2
True
```

The magic of bringing bits of the abstract type system into the world of data is known as “reification”.

Typeable also provides a method of “casting” any Typeable value as a fixed type, in the Maybe monad. Observe:

```
Prelude Data.Dynamic> cast 'a' :: Maybe Int
Nothing
Prelude Data.Dynamic> cast 'a' :: Maybe Char
Just 'a'
```

By using `cast`

the programmer is essentially saying *“Compiler, I take it
upon myself to deal with any runtime type errors in my code. Take the
afternoon off.”*

The other component is
Data.Dynamic, which uses Typeable (and in fact
exports the entire Typeable module) to create a new data type called
`Dynamic`

. Thanks goes to Luke Palmer for pointing out the existence of this
library to me.

This Dynamic type is like a magic bag for Typeable values:

```
Prelude Data.Dynamic> :t toDyn
toDyn :: (Typeable a) => a -> Dynamic
Prelude Data.Dynamic> :t fromDynamic
fromDynamic :: (Typeable a) => Dynamic -> Maybe a
Prelude Data.Dynamic> fromDynamic (toDyn 'c') :: Maybe Char
Just 'c'
```

So by encapsulating an arbitrary `Typeable`

value in a `Dynamic`

, it becomes a
monomorphic value that we can use in lists, functions, etc.

A final interesting thing to note is that the existence of Typeable and Dynamic do not in any way change haskell’s static typing. For example, if the compiler cannot infer the type of a value that we cast it will complain of the ambiguity:

```
Prelude Data.Dynamic> cast 'a' :: (Typeable a)=>Maybe a
Ambiguous type variable `a' in the constraint:
`Typeable a'
arising from an expression type signature at :1:0-32
Probable fix: add a type signature that fixes these type variable(s)
```

Furthermore the compiler will not allow you to do something fancy like define
a function that says *“if the value is an Int pass it to foo, if it is a
String, pass it to bar, else return Nothing”*.

## Defining the Dynamic State Monad

Okay, now let’s get to the fun part and define our new state monad with dynamic state.

```
module DynamicState
where
import Control.Monad.State
import Data.Dynamic
type DynamicState a = StateT Dynamic Maybe a
```

As you can see our new monad is simply the StateT
monad transformer,
where the state type is a Dynamic (meaning we’ll be able
to marshall in and out whatever state types we like), and the inner monad is
`Maybe`

for catching any type threading errors.

```
-- Dynamic 'get' and 'put' functions:
putD :: (Typeable a)=> a -> DynamicState ()
putD = put . toDyn
getD :: (Typeable a)=> DynamicState a
getD = get >>= lift . fromDynamic
```

Above we define our special getter and setter functions. You can see that they are both very simple: putD simply takes a Typeable state value, converts it to a Dynamic and pushes it; getD gets the Dynamic state, casts it into our requested type, and lifts this Maybe value back into the StateT transformer.

That’s about all there is to it, but a couple more functions are useful if we want to completely hide Dynamic from the user:

```
-- Compiler will complain if we ignore the returned final state since
-- its type is ambiguous:
runDState :: (Typeable s, Typeable s')=> DynamicState a -> s -> Maybe (a, s')
runDState c = (liftTypState =<<) . runStateT c . toDyn
where liftTypState (a,s) = fmap ((,)a) $ fromDynamic s
-- ...instead, use this if we want to discard the final state:
evalDState :: (Typeable s)=> DynamicState a -> s -> Maybe a
evalDState c = evalStateT c . toDyn
```

### Testing it Out

Let’s use the example we presented above (passing a mutually-recursive data type as state) to demonstrate our new state monad.

To begin with, we must make our EvenBranch/OddBranch type an instance of the Typeable class. This is really easy in GHC with the DeriveDataTypeable extension. Just add this to the top of the file:

```
{-# LANGUAGE DeriveDataTypeable #-}
```

…and add “`deriving Typeable`

” to the data declarations for those two types.

Now let’s see an example of a correct computation in the DynamicState monad (I’m sorry this is such a bad example, but I hope it demonstrates the point):

```
-- a non-sensical and contrived example:
traverseGood :: DynamicState String
traverseGood = do
-- we "get" a state value of type EvenBranch
(EBranch l i r) <- getD
-- ...and here we "put" a different type (OddBranch)!
if i == 2 then putD r
else putD l
(OBranch l' _) <- getD
-- ...and the state type changes back once more:
putD l'
(EBranch _ i' _) <- getD
if i' == 3 then return "found 3 in tree"
else return "3 not found"
```

Now we can define a little helper function to test our computation and a test EvenBranch tree we can pass as state:

```
tree = EBranch Nil 2 (OBranch (EBranch Nil 3 Nil) (EBranch Nil 4 Nil))
test :: DynamicState String -> Maybe String
test c = evalDState c tree
```

And testing it out with GHCi:

```
*DynamicState> test traverseGood
Just "found 3 in tree"
```

Cool! It seems like we got the threading of the state types correct and the algorithm did… what we wanted it to do.

Now let’s intentionally screw up the state, in a slight variation to the code above:

```
-- same as above but with a programmer error:
traverseBad :: DynamicState String
traverseBad = do
(EBranch l i r) <- getD
if i == 2 then putD r
else putD l
-- Oops! This is not the type of our state at this point!:
(EBranch l' _ _) <- getD
putD l'
(EBranch _ i' _) <- getD
if i' == 3 then return "found 3 in tree"
else return "3 not found"
```

And testing running this computation:

```
*DynamicState> test traverseBad
Nothing
```

This time a casting error was caught in our inner Maybe monad and running the computation simply returned Nothing.

## Philosophical Conclusion

The existence of Data.Dynamic allows for library designers to implement some pretty cool things that wouldn’t normally be possible in a statically-typed language. But I wonder to what extent its use is not simply “passing the buck” so to speak.

In other words to what extent can a haskell programmer really handle potential
type failure at runtime? If `Nothing`

s raised by cast et al. failing eventually
simply percolate up into an error message thrown in the user’s face, then
`Typeable`

seems not much more than a shim to work around haskell’s type system.