Hello all,<br><br>I just released two new packages on Hackage, stateful-mtl and pqueue-mtl.<br><br>Stateful-mtl provides an ST monad transformer, several useful operations on generic monad transformers, and a monad transformer intended to cleanly externally wrap operations on a mutable array (including resizing operations). It provides wrappers to generic MArray instances, an "array" based on an IntMap, and a specialized transformer that completely wraps what is essentially a pared-down STArray into a monadic interface that doesn't mention ST at all.<br>
<br>pqueue-mtl provides implementations of several structures supporting a generic 'single-in, single-out' paradigm (encapsulated in a typeclass named Queuelike), including stacks, queues, and several implementations of priority queues, including primarily a PQueue structure (in Data.Queue.PQueue) based on a pairing heap. In addition, the package provides monad transformers encapsulating single-threaded access to a Queuelike structure, and provides a fully encapsulated array-backed heap implementation (using the array transformers from stateful-mtl).<br>
<br>The primary motivation for all this was to improve elegance of graph algorithms. The following is an implementation of a shortest-path algorithm based on the fgl library that returns an IntMap mapping each node to its parent in a shortest-path tree:<br>
<br><span style="font-family: courier new,monospace;">type DijkstraM gr a b = IntMapT (Node, b) (PQueueT (Edge :-> b) (State (gr a b)))</span><br style="font-family: courier new,monospace;"><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">expand :: (Num b, Ord b, MonadQueue (Edge :-> b) m) => b -> Context a b -> m ()</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">expand d cxt = let x = node' cxt -- node being expanded</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> in queueInsertAll [(y, x) :-> (d + w) | (y, w) <- lsuc' cxt]</span><br style="font-family: courier new,monospace;"><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">dijkstraM :: (Graph gr, Num b, Ord b) => DijkstraM gr a b ()</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">dijkstraM = execMaybeT $ forever $ do</span> <span style="font-family: courier new,monospace;">-- this line repeats a monadic operation until a pattern match fails</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> False <- gets isEmpty</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> Just ((v, w) :-> d) <- queueExtract</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> statefully (match v) >>=? \ c -> writeAt v (w, d) >> expand d c -- performs an action if the match does not return Nothing</span><br style="font-family: courier new,monospace;">
<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">dijkstra :: (Graph gr, Num b, Ord b) => gr a b -> Node -> IntMap (Node, b)</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">dijkstra g v = evalState (runQueueTOn (execIntMapT_ dijkstraM) [(v, v) :-> 0]) g</span><br style="font-family: courier new,monospace;"><br>As an imperative programmer for many years, this is pretty much the most intuitive implementation of Dijkstra's algorithm that I've seen. Let me know what you think.<br>
<br clear="all">Louis Wasserman<br><a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a><br>