[Haskell-cafe] MonadMemory class

[Ryan Ingram]

On 3/27/08, Ariel J. Birnbaum <valgarv at gmx.net> wrote:
> class (Monad m) => MonadMemory m r | m -> r where
>    new :: a -> m (r a)
>    read :: r a -> m a
>    write :: r a -> a -> m ()
>
> What kind of axioms should an instance of this class satisfy?

Here's some thoughts:
(~=) means "equivalent excluding allocation effects".
(==) means "equivalent"

1) Unreferenced allocations do nothing:
(new a >> m) ~= m

2) Read+Write laws:
(read r >>= write r) == return ()
(new x >>= read) ~= return x
(write r x >>= read) == (write r x >> return x)

3) References are independent:
If m does not refer to r, then:
(read r >>= (\x -> m >> return x)) == m >> read r
(write r x >> m) == m >>= (\v -> write r x >> return v)

> 2. How would a "pure" instance of this class look like (obvious
> unsafePerformIO-based solutions aside)? Is it even possible in pure Haskell?

Yes, it is possible with unsafeCoerce.  It's possible without
unsafeCoerce if you add a Typeable constraint or pass a GADT type
representation to new.

To be truly safe you need higher-rank types and use the same trick
that ST does.  But there's not much point; you may as well use ST.

At that point, it's actually a pretty simple state monad:

data HeapItem = forall a. HeapItem a
newtype Ref s a = Ref Integer
newtype RefM s = RefM (State (Integer, Map Integer HeapItem))
-- use unsafeCoerce to extract elements in read.

Handling garbage collection is tricky, though.

  -- ryan