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.
## No comments:

## Post a Comment