Disciple-style Regions in Haskell, Part 1

I've admired ddc for quite a while, in particular its region system. Unfortunately, it also has many annoyances, and one big one is complexity. To rectify this, I've created a system implementing regions in Haskell.

The Essence of Regions

At first we might adopt a definition of regions based on their use in memory management: they are areas where you can allocate memory and work with it, as show by the class below.

-- WRONG!
class (Monad (Environment r)) => Region r where
    data Ref r :: * -> *
    type Environment r :: * -> *

    newRef :: a -> Environment r (Ref r a)
    readRef :: Ref r a -> Environment r a
    writeRef :: a -> Ref r a -> Environment r ()

There are a couple of instances of this - consider ST, or IO, or STM. Unfortunately, this is not what we want. We need to support, for example, immutable regions. Not only that, but in rare cases we might want a write only region (as a random example, a password store). You might have regions that you can't create data in. In the end, we have reduced the idea of a region to something very small: a place with data.

data family Ref r :: * -> *

Note that this also allows us to do away with the monad. Of course, mutation and reading and creation are common, so we should have some classes:

class (Monad m) => Writable r m where
    writeRef :: a -> Ref r a -> m ()

class (Monad m) => Readable r m where
    readRef :: Ref r a -> m a

class (Monad m) => Creatable r m where
    newRef :: a -> m (Ref r a)

Following the previous idea of not needing a fixed monad, we do not restrict a reference to have a single monad assosciated with it.

Some Examples

data Mut s
newtype instance Ref (Mut s) a = MutRef (STRef s a)

instance Writable (Mut s) (ST s) where
    writeRef val (MutRef ref) = writeSTRef val ref

instance Readable (Mut s) (ST s) where
    readRef (MutRef ref) = readSTRef ref

instance Creatable (Mut s) (ST s) where
    createRef val = fmap MutRef $ newSTRef val

data Immut
newtype instance Ref Immut a = ImmutRef a

instance (Monad m) => Readable Immut m where
    readRef (ImmutRef val) = return val

instance (Monad m) => Creatable Immut m where
    createRef val = return (ImmutRef val)

data Atomic
newtype instance Ref Atomic a = AtomicRef (TVar a)

instance Writable Atomic STM where
    writeRef val (AtomicRef ref) = writeTVar val ref

instance Readable Atomic STM where
    readRef (AtomicRef ref) = readTVar ref

instance Creatable Atomic STM where
    createRef val = fmap AtomicRef $ newTVar val

instance Writable Atomic IO where
    writeRef val (AtomicRef ref) = writeTVarIO val ref

instance Readable Atomic IO where
    readRef (AtomicRef ref) = readTVarIO ref

instance Creatable Atomic IO where
    createRef val = fmap AtomicRef $ newTVarIO val

To support things like pointers or specialized references, we probably want to add the ability to restrict the types that can be put in a Ref, but this is beyond the scope of this post.

Building Complex Data Structures

As an example, I will build a cyclic doubly linked list with this framework. Actually constructing the representation and basic operations of a complex data structure is pretty easy:

data DList r a = DList (Ref r (DList r a)) a (Ref r (DList r a))

head :: (Monad m) => DList r a -> m a
head (DList _ x _) = return x

tail :: (Readable r m, Writable r m) => DList r a -> m (DList r a)
tail (DList lRef _ rRef) = do
    l@(DList ll xl rl) <- readRef lRef
    r@(DList lr xr rr) <- readRef rRef
    writeRef lr l
    writeRef rl r
    return r

singleton :: (Creatable r m, MonadFix m) => a -> m (DList r a)
singleton x = do rec
    l <- createRef result
    r <- createRef result
    let result = DList l x r
    return result

-- And so on...

However, how do we switch between representations? With arrays, we usually have the freeze and thaw methods. Here, we have a possibly infinite collection of regions to switch between - how can we do it? I'll post my answer in part 2, since this post is getting a bit long.