Subject: ANNOUNCE: pqueue-mtl, stateful-mtl Newsgroups: gmane.comp.lang.haskell.cafe Date: Sunday 15th February 2009 20:26:16 UTC (over 8 years ago) 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 [email protected] |
|||