[Haskell-cafe] ANNOUNCE: pqueue-mtl, stateful-mtl

[Louis Wasserman]

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 at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090215/4d15b3a0/attachment.htm