On 3/27/08, Ariel J. Birnbaum
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