Having adopted the purely functional point of view on programming, I don’t like mutable variables very much.
But there is something strange about them that goes far beyond their mutability: somehow, they seem to wreak havoc to the type system. For instance, their spooky “action over a distance” allows you to decompose a function type
a -> IO b into two separate entities
decompose :: (a -> IO b) -> IO (a -> IO (), IO b) decompose f = do ref <- newIORef Nothing let argument = writeIORef ref . Just result = f . fromJust =<< readIORef ref return $ (argument, result)
that “magically” communicate with each other. Interestingly, each part carries only half the type information of the original function.
Another, more drastic example is that polymorphic mutable variables can destroy type safety. This is what forced ML to adopt the value restriction and this is also why
IORef can be used to implement
unsafeCoerce :: a -> b in Haskell.
Of course, sometimes you want to stretch the type system a bit and that’s where mutable variables are quite handy, even when their mutability is not useful.
In particular, while implementing my reactive-banana library, I have found the need for a type-safe, persistent storage. Like
IORef, I want to be able to store values of any type in it, but unlike
IORef, I want the storage space to behave like a persistent, first-class data structure, as appropriate for a purely functional language.
I will call this data structure a vault, because it is analogous to a bank vault, where you can access different bank boxes with different keys. In other words, a
Vault is an abstract data type with the following signature
data Key a data Vault newKey :: IO (Key a) empty :: Vault lookup :: Key a -> Vault -> Maybe a insert :: Key a -> a -> Vault -> Vault delete :: Key a -> Vault -> Vault
The idea is that keys obtained with the
newKey functions correspond to “secure deposit boxes” in the vault. You can insert or remove items of any type by using different keys.
Implementing a vault in Haskell is straightforward with some form of dynamic typing, like the
import Data.Map as Map import Data.Unique import Data.Dynamic data Vault = Map.Map Unique Dynamic data Key a = Unique newKey = newUnique empty = Map.empty lookup key vault = Map.lookup key vault >>= fromDynamic insert key x vault = Map.insert key (toDyn x) vault delete key vault = Map.delete key vault
Unfortunately, we now have to include the
Typable constraint in the type signatures, for instance
insert :: Typable a => Key a -> a -> Vault -> Vault
But this is really bad for my library because the constraint would creep into the publicly visible API and for example prohibit me from providing a
Functor instance. Some other solution is needed.
That’s where the strange properties of mutable variables come in very handy.
The idea is to use a finite map as storage, but we don’t store the values themselves, we store actions of type
IO (). This way, all items in the store have the same type.
type Vault = Map Unique Item type Item = IO ()
Of course, these IO actions must somehow contain the values. In particular, the idea is that executing an action will write the corresponding value to a temporary mutable variable. Furthermore, it is the
Key who keeps track of the mutable variable
data Key a = Key Unique (Item' a) type Item' a = IORef (Maybe a)
In other words, storing a value works like this
insert :: Key a -> a -> Vault -> Vault insert (Key k ref) x = Map.insert k (writeIORef ref $ Just x)
while reading a value works like this
lookup :: Key a -> Vault -> IO (Maybe a) lookup (Key k ref) vault = case Map.lookup k vault of Nothing -> return Nothing Just item -> do item -- write into IORef mx <- readIORef ref -- read the value writeIORef ref Nothing -- clear IORef return mx
We have to make a small concession here: the type of
lookup is no longer pure. That said, it is safe to wrap this in
unsafePerformIO because the function itself actually is pure. After all, we don’t want to mutate anything, we just want to play a trick on the type system.
To create a new key, we simply allocate both a new unique identifier and the temporary mutable variable.
newKey :: IO (Key a) newKey = do k <- newUnique ref <- newIORef Nothing return $ Key k ref
Voilà, that’s my implementation of a vault, i.e. a persistent store for values of arbitrary types. I have implemented a variant in my reactive-banana library and used it for great, purely functional good.