Dynamic types in Haskell

Working on a Haskell project recently (GitHub link), I found myself in a tricky situation. I have these types (in pseudo-Haskell):

data A = A
data B = B
data C = C
data Value a = VA A | VB B | VC C
data Structure = ...
data Substructure = ...
computeOrLookup :: Structure -> (Substructure -> a) -> Map Label Value -> a

I have a data structure, and a function that computes an 'a' from a sub-part of that structure. I also have a Map containing values that can be of type A, B, or C.  The 'computeOrLookup' function finds the solution in the Map, or invokes the supplied function otherwise. The return type ('a') of 'computeOrLookup' is determined by the function we pass in (and the type parameter 'a' must be one of A, B, or C).  The problem is to safely extract and return a value of type 'a' from the Map.  There's no obvious way to do it.

If I were a smarter programmer, I would probably find a way to refactor my code to avoid this situation. But, I'm not, so I found myself reaching for dynamic types.  One advantage of a strong static type system (such as Haskell's) is that it is easy to embed dynamic types.  And indeed, GHC comes with an excellent library for dynamic types.

Dynamic types

These APIs have changed as of base-4.10.  I'm going to review the old API first (since base-4.10 isn't on stackage lts at the time of writing), then I will comment briefly on the revised API. The Data.Dynamic module offers the following definitions:

import Data.Dynamic
data Dynamic
toDyn :: Typeable a => a -> Dynamic
fromDyn :: Typeable a -> Dynamic -> a -> a
fromDynamic :: Typeable a -> Dynamic -> Maybe a

The Dynamic type wraps up an arbitrary value with a run-time representation of its type. Since Dynamic values carry around type information at run-time, and Data.Dynamic doesn't do any implicit casting, we don't lose strong-typing. The difference is that now we have to deal with type errors at run-time rather than compile time.

The Typeable constraint guarantees that GHC can construct a run-time type representation when required. GHC creates these Typeable instances as required; the programmer doesn't have to explicitly derive the Typeable class. Furthermore, GHC will not allow the programmer to write a custom Typeable instance (as it would allow the programmer to subvert the type system).  See the GHC manual for more details.

The Dynamic API could hardly be simpler. toDyn turns an ordinary value into a Dynamic value, fromDynamic casts a Dynamic value back to a statically typed value (returning Nothing if the types don't match), and fromDyn also casts a Dynamic value but it returns the supplied default value if there is a type mismatch.  GHC doesn't do any implicit type conversions, so fromDynamic will only return a Just value when the type parameter 'a' matches what was put into the Dynamic value.

The Dynamic API also has some functions for dynamic function application (which allows the programmer to write dynamically typed code without casting back to static types).

dynApply :: Dynamic -> Dynamic -> Dynamic
dynApp :: Dynamic -> Dynamic -> Dynamic

dynApply applies the function inside the first Dynamic value to the second Dynamic value, for example:

flip fromDyn "type error!" <$> toDyn (++ " dynamic!") `dynApply` toDyn "it's"

dynApp does the same thing but it throws an exception if there's a type mismatch.  Being a partial function, I think dynApp is best avoided.

There's one more function in the Data.Dynamic module:

dynTypeRef :: Dynamic -> TypeRep

TypeRep is the type of run-time type representations. TypeReps are regular Haskell values so we can store them in data structures etc. TypeRep is defined in Data.Typeable, and it has Eq, Ord, and Show instances. We can get the TypeRep of any Haskell value with typeOf. This allows the programmer to dynamically dispatch on types, for example:

sameType :: Dynamic -> a -> Bool
sameType dynamic v = dynTypeRef dynamic == typeOf v

What if I want to get the TypeRep of some type 'a', but I don't have a value of that type available? I found myself in exactly this situation when implementing the function in the introduction to this blog post. If the value in the Map is of the wrong type, I'd like to report an error to the user that includes the expected type, but I don't have a value of the expected type, only a function that returns a value of that type (and maybe I don't have the required data to call that function).

Firstly, we must enable the ScopedTypeVariables extension. Then, we could try something like this:

{-# LANGUAGE ScopedTypeVariables #-}
import Data.Dynamic
g :: forall a. Typeable a => (String -> a) -> String
g _ = show$ typeOf (undefined :: a)

The qualifier 'forall a.' declares a scoped type variable 'a'. This means that every 'a' inside the function will be the same 'a' (I'm not quite sure why this isn't the default behaviour).  Using (undefined :: a) works, but I don't like having that undefined value in there. A careless mistake could lead to an undefined value being evaluated  (which throws an exception that can only be caught in IO).

For these situations, Data.Typeable provides the Proxy type:

data Proxy t = Proxy

And now I can rewrite my trivial example without undefined:

g :: forall a. Typeable a => (String -> a) -> String
g _ = show$ typeRep (Proxy :: Proxy a)

This time I use the typeRep function, which gets the TypeRep of the first type parameter. Otherwise we'd be getting the TypeRep of 'Proxy a' instead of the TypeRep of 'a' itself.

There's plenty more to explore in Data.Typeable, including type-safe casting, and functions that apply and unapply type constructors at run-time. I don't have a use case for those functions yet, but it's nice to know they're there in case I should ever need them.

API changes in base-4.10

In base-4.10, the Dynamic type exposes it's constructor for pattern matching:

Dynamic :: forall a. TypeRep a -> a -> Dynamic

Notice that this TypeRep has a type parameter.  The old style TypeRep without a type parameter is still available in Data.Typeable, whereas the new version can be found in Data.Reflection.