[Haskell-cafe] ANNOUNCE: pqueue-mtl, stateful-mtl
Ryan Ingram
ryani.spam at gmail.com
Sun Feb 15 19:15:43 EST 2009
You can roll your own pure STT monad, at the cost of performance:
-- Do not export any of these constructors, just the types STT and STTRef.
data W = forall a. W !a
data Heap s = Heap !Int !(IntMap W)
newtype STT s m a = STT (StateT (Heap s) m a) deriving (Monad,
MonadTrans, MonadIO, insert other stuff here, but not MonadState)
newtype STTRef s a = Ref Int
liftState :: (MonadState s m) => (s -> (a,s)) -> m a
liftState f = do
(a, s') <- liftM f get
put s'
return a
newSTTRef :: forall s m a. a -> STT s m a
newSTTRef a = STT $ liftState go where
go (Heap sz m) = (Ref sz, Heap (sz+1) (insert sz (W a) m)
readSTTRef :: forall s m a. STTRef s a -> STT s m a
readSTTRef (Ref n) = STT $ liftM go get where
go (Heap _ m) = case lookup n m of
Just (~(W a)) -> unsafeCoerce a
_ -> error "impossible: map lookup failed."
writeSTTRef :: forall s m a. STTRef s a -> a -> STT s m ()
writeSTTRef (Ref n) a = STT $ modify go where
go (Heap sz m) = Heap sz (insert n (W a) m)
-- forall s. here makes unsafeCoerce in readSTTRef safe. Otherwise
references could escape and break unsafeCoerce.
runSTT :: (forall s. STT s m a) -> m a
runSTT (STT m) = evalStateT m (Heap 0 empty)
instance (MonadState s m) => MonadState s (STT st m) where
get = lift get
put = lift . put
modify = lift . modify
Unfortunately, you lose garbage collection on referenced data since
it's all stored in an IntMap. Is there a way to solve this problem,
perhaps using some form of weak reference? Ideally you'd like to be
able to find that all references to a particular Ref have been GC'd so
that you can reuse that Ref index. Otherwise eventually the IntMap
will fill up if you keep allocating references and throwing them away.
-- ryan
2009/2/15 Louis Wasserman <wasserman.louis at gmail.com>:
> Well, it makes me sad, I guess. pqueue-mtl provides an array-backed heap
> monad transformer that is supposed to keep its own ST thread, if only for
> the sake of retaining a purely functional interface without any externally
> visible forall'd types, which is perfectly fine in most cases, but I'd have
> to think about whether or not it'd remain referentially transparent if the
> ST thread were only visible to a very tightly encapsulated set of commands
> (i.e. priority queue operations).
>
> Louis Wasserman
> wasserman.louis at gmail.com
>
>
> On Sun, Feb 15, 2009 at 5:33 PM, Henning Thielemann
> <lemming at henning-thielemann.de> wrote:
>>
>> On Sun, 15 Feb 2009, Louis Wasserman wrote:
>>
>>> I follow. The primary issue, I'm sort of wildly inferring, is that use
>>> of STT -- despite being
>>> pretty much a State monad on the inside -- allows access to things like
>>> mutable references?
>>
>> I assume that ST must always be the most inner monad, like IO. Is this a
>> problem in an application?
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
More information about the Haskell-Cafe
mailing list