Hello all,
I just released two new packages on Hackage, stateful-mtl and pqueue-mtl.
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.
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).
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:
type DijkstraM gr a b = IntMapT (Node, b) (PQueueT (Edge :-> b) (State (gr a b)))
expand :: (Num b, Ord b, MonadQueue (Edge :-> b) m) => b -> Context a b -> m ()
expand d cxt = let x = node' cxt -- node being expanded
in queueInsertAll [(y, x) :-> (d + w) | (y, w) <- lsuc' cxt]
dijkstraM :: (Graph gr, Num b, Ord b) => DijkstraM gr a b ()
dijkstraM = execMaybeT $ forever $ do -- this line repeats a monadic operation until a pattern match fails
False <- gets isEmpty
Just ((v, w) :-> d) <- queueExtract
statefully (match v) >>=? \ c -> writeAt v (w, d) >> expand d c -- performs an action if the match does not return Nothing
dijkstra :: (Graph gr, Num b, Ord b) => gr a b -> Node -> IntMap (Node, b)
dijkstra g v = evalState (runQueueTOn (execIntMapT_ dijkstraM) [(v, v) :-> 0]) g
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.
Louis Wasserman
wasserman.louis@gmail.com