Hi!
Some time ago, i needed to write down graphs in Haskell. I wanted to be able
to write them down without to much noise, to make them easily maintainable. I
came up with a way to define graphs using monads and the do notation. I thought
this might be interesting to someone, so i wrote a small script to illustrate
the idea. Here's an example:
example :: Graph String
example = buildGraph $ do
a <- mkNode "A" []
b <- mkNode "B" [a]
mkNode "C" [a, b]
In this graph there are three nodes identified by ["A", "B", "C"] and three
edges ([("A", "B"), ("A", "C"), ("B", "C")]). Think of the variables a and b
as outputs of the nodes "A" and "B". Note that each node identifier needs to be
mentioned only once. Also the definition of edges (references to other nodes
via the outputs) can be checked at compile time.
The attachment is a little script that defines a Graph-type (nothing
elaborate), the "buildGraph" function and an example graph that is a little
more complex than the above. The main function of the script prints the
example graph to stdout to be read by dot (or similar).
By the way, it is possible to define cyclic graphs using mdo (RecursiveDo).
I haven't come across something similar, so i thought, i'd share it. What do
you think?
Sönke
{-# language RecursiveDo #-}
import Data.Map ((!), fromList)
import Control.Monad.State
import qualified Text.Dot as Dot
-- * Graph definition
-- | type of Graphs.
data Graph node
= Graph {
nodes :: [node],
edges :: [(node, node)]
}
deriving Show
-- | The empty Graph.
emptyGraph :: Graph a
emptyGraph = Graph [] []
-- | Converts a Graph into dot format
toDot :: (Ord s, Show s) => Graph s -> String
toDot (Graph nodes edges) = Dot.showDot $ do
ids <- mapM (\ l -> Dot.node [("label", show l)]) nodes
let idMap = fromList $ zip nodes ids
mapM_ (\ (a, b) -> (idMap ! a) Dot..->. (idMap ! b)) edges
-- * GraphMonad
-- | Allows to write directed Graphs in form of monadic statements.
type GraphMonad n a = State (Graph n) a
data Output n = Output n
-- | Builds the Graph given a graph creation command.
buildGraph :: GraphMonad n () -> Graph n
buildGraph cmd = snd $ runState cmd emptyGraph
-- | Constructs a node. $inputs$ are all nodes which should be
-- connected (via edges) to this new node.
mkNode :: n -> [Output n] -> GraphMonad n (Output n)
mkNode node inputs =
State $ \ (Graph nodes edges) ->
let newEdges = map (\ (Output input) -> (input, node)) inputs
in (Output node, Graph (node : nodes) (edges ++ newEdges))
-- * example graph
-- | This is just an example graph.
example :: Graph String
example = buildGraph $ mdo
mkNode "unconnected" []
a <- mkNode "A" []
b <- mkNode "B" [a]
mkNode "C" [a, b]
subgraph a b
c1 <- mkNode "cyclic" [c1, c2]
c2 <- mkNode "cyclic2" [c1]
return ()
-- | example for encapsulating subgraphs.
-- This doesn't show in the resulting graph.
subgraph :: Output String -> Output String -> GraphMonad String ()
subgraph a b = do
x <- mkNode "x" [a]
mkNode "y" [x, b]
return ()
-- | Print out the example graph in dot format to stdout
main = putStrLn $ toDot example
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
