The module I put together already has everything I'd need to do it in terms of an IntMap with much less work than that -- the generic MonadArray type class has implementations both in terms of ST and in terms of an IntMap already. Only three changes in the Heap implementation would be needed: two changes from runArrayT_ 16 to evalIntMapT, and one change of ArrayT to IntMapT. (Here ArrayT is backed by an STT transformer.)<br>
<br>newtype HeapT e m a = HeapT {execHeapT :: ArrayT e (StateT Int m) a} deriving (Monad, MonadReader r, MonadST s, MonadWriter w, MonadFix, MonadIO)<br><br>-- | Runs an 'HeapT' transformer starting with an empty heap.<br>
runHeapT :: (Monad m, Ord e) => HeapT e m a -> m a<br>runHeapT m = evalStateT (runArrayT_ 16 (execHeapT m)) 0<br><br>But I'm still not entirely convinced that the original STT monad with all its illegal behavior, hidden from the user, couldn't be used internally by HeapT without exposing non-referential-transparency -- I'm still thinking on that problem. (Perhaps it'd be useful to ask, how would this purely functional implementation of HeapT behave when used as a drop-in replacement for the STT-backed HeapT?)<br>
<br>Originally I said that I was inferring that the problem with an ST transformer was that it allowed access to mutable references. If that's true, can a priority queue be used to simulate an STRef? If so, wouldn't that imply (rather elegantly, in fact) that an STT-backed heap transformer would violate referential transparency. (Would the single-threaded array transformer backing HeapT fail in that fashion as well?)<br>
<br clear="all">Louis Wasserman<br><a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a><br>
<br><br><div class="gmail_quote">On Sun, Feb 15, 2009 at 6:15 PM, Ryan Ingram <span dir="ltr"><<a href="mailto:ryani.spam@gmail.com">ryani.spam@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
You can roll your own pure STT monad, at the cost of performance:<br>
<br>
-- Do not export any of these constructors, just the types STT and STTRef.<br>
data W = forall a. W !a<br>
data Heap s = Heap !Int !(IntMap W)<br>
newtype STT s m a = STT (StateT (Heap s) m a) deriving (Monad,<br>
MonadTrans, MonadIO, insert other stuff here, but not MonadState)<br>
newtype STTRef s a = Ref Int<br>
<br>
liftState :: (MonadState s m) => (s -> (a,s)) -> m a<br>
liftState f = do<br>
(a, s') <- liftM f get<br>
put s'<br>
return a<br>
<br>
newSTTRef :: forall s m a. a -> STT s m a<br>
newSTTRef a = STT $ liftState go where<br>
go (Heap sz m) = (Ref sz, Heap (sz+1) (insert sz (W a) m)<br>
<br>
readSTTRef :: forall s m a. STTRef s a -> STT s m a<br>
readSTTRef (Ref n) = STT $ liftM go get where<br>
go (Heap _ m) = case lookup n m of<br>
Just (~(W a)) -> unsafeCoerce a<br>
_ -> error "impossible: map lookup failed."<br>
<br>
writeSTTRef :: forall s m a. STTRef s a -> a -> STT s m ()<br>
writeSTTRef (Ref n) a = STT $ modify go where<br>
go (Heap sz m) = Heap sz (insert n (W a) m)<br>
<br>
-- forall s. here makes unsafeCoerce in readSTTRef safe. Otherwise<br>
references could escape and break unsafeCoerce.<br>
runSTT :: (forall s. STT s m a) -> m a<br>
runSTT (STT m) = evalStateT m (Heap 0 empty)<br>
<br>
instance (MonadState s m) => MonadState s (STT st m) where<br>
get = lift get<br>
put = lift . put<br>
modify = lift . modify<br>
<br>
Unfortunately, you lose garbage collection on referenced data since<br>
it's all stored in an IntMap. Is there a way to solve this problem,<br>
perhaps using some form of weak reference? Ideally you'd like to be<br>
able to find that all references to a particular Ref have been GC'd so<br>
that you can reuse that Ref index. Otherwise eventually the IntMap<br>
will fill up if you keep allocating references and throwing them away.<br>
<br>
-- ryan<br>
<br>
2009/2/15 Louis Wasserman <<a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a>>:<br>
<div><div></div><div class="Wj3C7c">> Well, it makes me sad, I guess. pqueue-mtl provides an array-backed heap<br>
> monad transformer that is supposed to keep its own ST thread, if only for<br>
> the sake of retaining a purely functional interface without any externally<br>
> visible forall'd types, which is perfectly fine in most cases, but I'd have<br>
> to think about whether or not it'd remain referentially transparent if the<br>
> ST thread were only visible to a very tightly encapsulated set of commands<br>
> (i.e. priority queue operations).<br>
><br>
> Louis Wasserman<br>
> <a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a><br>
><br>
><br>
> On Sun, Feb 15, 2009 at 5:33 PM, Henning Thielemann<br>
> <<a href="mailto:lemming@henning-thielemann.de">lemming@henning-thielemann.de</a>> wrote:<br>
>><br>
>> On Sun, 15 Feb 2009, Louis Wasserman wrote:<br>
>><br>
>>> I follow. The primary issue, I'm sort of wildly inferring, is that use<br>
>>> of STT -- despite being<br>
>>> pretty much a State monad on the inside -- allows access to things like<br>
>>> mutable references?<br>
>><br>
>> I assume that ST must always be the most inner monad, like IO. Is this a<br>
>> problem in an application?<br>
><br>
</div></div>> _______________________________________________<br>
> Haskell-Cafe mailing list<br>
> <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
> <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
><br>
><br>
</blockquote></div><br>