<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <!--Rendered using the Haskell Html Library v0.2--> <HTML ><HEAD ><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8" ><TITLE >Data.Graph.Inductive.Query.Monad</TITLE ><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css" ><SCRIPT SRC="haddock-util.js" TYPE="text/javascript" ></SCRIPT ><SCRIPT TYPE="text/javascript" >window.onload = function () {setSynopsis("mini_Data-Graph-Inductive-Query-Monad.html")};</SCRIPT ></HEAD ><BODY ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="topbar" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD ><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" " ></TD ><TD CLASS="title" >fgl-5.4.2.3: Martin Erwig's Functional Graph Library</TD ><TD CLASS="topbut" ><A HREF="index.html" >Contents</A ></TD ><TD CLASS="topbut" ><A HREF="doc-index.html" >Index</A ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="modulebar" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD ><FONT SIZE="6" >Data.Graph.Inductive.Query.Monad</FONT ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="section4" ><B >Contents</B ></TD ></TR ><TR ><TD ><DL ><DT ><A HREF="#1" >Additional Graph Utilities </A ></DT ><DT ><A HREF="#2" >Graph Transformer Monad </A ></DT ><DT ><A HREF="#3" >Graph Computations Based on Graph Monads </A ></DT ><DD ><DL ><DT ><A HREF="#4" >Monadic Graph Accessing Functions </A ></DT ><DT ><A HREF="#5" >Derived Graph Recursion Operators </A ></DT ></DL ></DD ><DT ><A HREF="#6" >Examples: Graph Algorithms as Instances of Recursion Operators </A ></DT ><DD ><DL ><DT ><A HREF="#7" >Instances of graphRec </A ></DT ></DL ></DD ><DT ><A HREF="#8" >Example: Monadic DFS Algorithm(s) </A ></DT ></DL ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" >Description</TD ></TR ><TR ><TD CLASS="doc" >Monadic Graph Algorithms </TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" >Synopsis</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="decl" ><A HREF="#v%3AmapFst" >mapFst</A > :: (a -> b) -> (a, c) -> (b, c)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AmapSnd" >mapSnd</A > :: (a -> b) -> (c, a) -> (c, b)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3A%3E%3C" >(><)</A > :: (a -> b) -> (c -> d) -> (a, c) -> (b, d)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AorP" >orP</A > :: (a -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> (b -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> (a, b) -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A ></TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A HREF="#t%3AGT" >GT</A > m g a = <A HREF="#v%3AMGT" >MGT</A > (m g -> m (a, g))</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Aapply" >apply</A > :: <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m g a -> m g -> m (a, g)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Aapply%27" >apply'</A > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m g a -> g -> m (a, g)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AapplyWith" >applyWith</A > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => (a -> b) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m g a -> m g -> m (b, g)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AapplyWith%27" >applyWith'</A > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => (a -> b) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m g a -> g -> m (b, g)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3ArunGT" >runGT</A > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m g a -> m g -> m a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AcondMGT%27" >condMGT'</A > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => (s -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3ArecMGT%27" >recMGT'</A > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => (s -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a -> (a -> b -> b) -> b -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s b</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AcondMGT" >condMGT</A > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => (m s -> m <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3ArecMGT" >recMGT</A > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => (m s -> m <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a -> (a -> b -> b) -> b -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s b</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgetNode" >getNode</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A ></TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgetContext" >getContext</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) (<A HREF="Data-Graph-Inductive-Graph.html#t%3AContext" >Context</A > a b)</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgetNodes%27" >getNodes'</A > :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3AGraph" >Graph</A > gr, <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr) => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgetNodes" >getNodes</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AsucGT" >sucGT</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A > -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) (<A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Maybe.html#t%3AMaybe" >Maybe</A > [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >])</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AsucM" >sucM</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A > -> m (gr a b) -> m (<A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Maybe.html#t%3AMaybe" >Maybe</A > [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >])</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgraphRec" >graphRec</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) c -> (c -> d -> d) -> d -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) d</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgraphRec%27" >graphRec'</A > :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3AGraph" >Graph</A > gr, <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr) => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) c -> (c -> d -> d) -> d -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) d</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgraphUFold" >graphUFold</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => (<A HREF="Data-Graph-Inductive-Graph.html#t%3AContext" >Context</A > a b -> c -> c) -> c -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) c</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgraphNodesM0" >graphNodesM0</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgraphNodesM" >graphNodesM</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgraphNodes" >graphNodes</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => m (gr a b) -> m [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgraphFilterM" >graphFilterM</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => (<A HREF="Data-Graph-Inductive-Graph.html#t%3AContext" >Context</A > a b -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="Data-Graph-Inductive-Graph.html#t%3AContext" >Context</A > a b]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgraphFilter" >graphFilter</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => (<A HREF="Data-Graph-Inductive-Graph.html#t%3AContext" >Context</A > a b -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> m (gr a b) -> m [<A HREF="Data-Graph-Inductive-Graph.html#t%3AContext" >Context</A > a b]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AdfsGT" >dfsGT</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >] -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AdfsM" >dfsM</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >] -> m (gr a b) -> m [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AdfsM%27" >dfsM'</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => m (gr a b) -> m [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AdffM" >dffM</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >] -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="/usr/share/doc/ghc/html/libraries/containers-0.3.0.0/Data-Tree.html#t%3ATree" >Tree</A > <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgraphDff" >graphDff</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >] -> m (gr a b) -> m [<A HREF="/usr/share/doc/ghc/html/libraries/containers-0.3.0.0/Data-Tree.html#t%3ATree" >Tree</A > <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgraphDff%27" >graphDff'</A > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => m (gr a b) -> m [<A HREF="/usr/share/doc/ghc/html/libraries/containers-0.3.0.0/Data-Tree.html#t%3ATree" >Tree</A > <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" ><A NAME="1" ><A NAME="1" >Additional Graph Utilities </A ></A ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:mapFst" ><A NAME="v%3AmapFst" ></A ></A ><B >mapFst</B > :: (a -> b) -> (a, c) -> (b, c)</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:mapSnd" ><A NAME="v%3AmapSnd" ></A ></A ><B >mapSnd</B > :: (a -> b) -> (c, a) -> (c, b)</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:><" ><A NAME="v%3A%3E%3C" ></A ></A ><B >(><)</B > :: (a -> b) -> (c -> d) -> (a, c) -> (b, d)</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:orP" ><A NAME="v%3AorP" ></A ></A ><B >orP</B > :: (a -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> (b -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> (a, b) -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" ><A NAME="2" ><A NAME="2" >Graph Transformer Monad </A ></A ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A NAME="t:GT" ><A NAME="t%3AGT" ></A ></A ><B >GT</B > m g a </TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="section4" >Constructors</TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:MGT" ><A NAME="v%3AMGT" ></A ></A ><B >MGT</B > (m g -> m (a, g))</TD ><TD CLASS="rdoc" ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="section4" ><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:GT')" ALT="show/hide" > Instances</TD ></TR ><TR ><TD CLASS="body" ><DIV ID="i:GT" STYLE="display:block;" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="decl" ><A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > (<A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m g)</TD ></TR ></TABLE ></DIV ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:apply" ><A NAME="v%3Aapply" ></A ></A ><B >apply</B > :: <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m g a -> m g -> m (a, g)</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:apply'" ><A NAME="v%3Aapply%27" ></A ></A ><B >apply'</B > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m g a -> g -> m (a, g)</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:applyWith" ><A NAME="v%3AapplyWith" ></A ></A ><B >applyWith</B > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => (a -> b) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m g a -> m g -> m (b, g)</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:applyWith'" ><A NAME="v%3AapplyWith%27" ></A ></A ><B >applyWith'</B > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => (a -> b) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m g a -> g -> m (b, g)</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:runGT" ><A NAME="v%3ArunGT" ></A ></A ><B >runGT</B > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m g a -> m g -> m a</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:condMGT'" ><A NAME="v%3AcondMGT%27" ></A ></A ><B >condMGT'</B > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => (s -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:recMGT'" ><A NAME="v%3ArecMGT%27" ></A ></A ><B >recMGT'</B > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => (s -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a -> (a -> b -> b) -> b -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s b</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:condMGT" ><A NAME="v%3AcondMGT" ></A ></A ><B >condMGT</B > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => (m s -> m <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:recMGT" ><A NAME="v%3ArecMGT" ></A ></A ><B >recMGT</B > :: <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad.html#t%3AMonad" >Monad</A > m => (m s -> m <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s a -> (a -> b -> b) -> b -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m s b</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" ><A NAME="3" ><A NAME="3" >Graph Computations Based on Graph Monads </A ></A ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section2" ><A NAME="4" ><A NAME="4" >Monadic Graph Accessing Functions </A ></A ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:getNode" ><A NAME="v%3AgetNode" ></A ></A ><B >getNode</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:getContext" ><A NAME="v%3AgetContext" ></A ></A ><B >getContext</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) (<A HREF="Data-Graph-Inductive-Graph.html#t%3AContext" >Context</A > a b)</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:getNodes'" ><A NAME="v%3AgetNodes%27" ></A ></A ><B >getNodes'</B > :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3AGraph" >Graph</A > gr, <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr) => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:getNodes" ><A NAME="v%3AgetNodes" ></A ></A ><B >getNodes</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:sucGT" ><A NAME="v%3AsucGT" ></A ></A ><B >sucGT</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A > -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) (<A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Maybe.html#t%3AMaybe" >Maybe</A > [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >])</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:sucM" ><A NAME="v%3AsucM" ></A ></A ><B >sucM</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A > -> m (gr a b) -> m (<A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Maybe.html#t%3AMaybe" >Maybe</A > [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >])</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section2" ><A NAME="5" ><A NAME="5" >Derived Graph Recursion Operators </A ></A ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:graphRec" ><A NAME="v%3AgraphRec" ></A ></A ><B >graphRec</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) c -> (c -> d -> d) -> d -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) d</TD ></TR ><TR ><TD CLASS="doc" >encapsulates a simple recursion schema on graphs </TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:graphRec'" ><A NAME="v%3AgraphRec%27" ></A ></A ><B >graphRec'</B > :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3AGraph" >Graph</A > gr, <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr) => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) c -> (c -> d -> d) -> d -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) d</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:graphUFold" ><A NAME="v%3AgraphUFold" ></A ></A ><B >graphUFold</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => (<A HREF="Data-Graph-Inductive-Graph.html#t%3AContext" >Context</A > a b -> c -> c) -> c -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) c</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" ><A NAME="6" ><A NAME="6" >Examples: Graph Algorithms as Instances of Recursion Operators </A ></A ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section2" ><A NAME="7" ><A NAME="7" >Instances of graphRec </A ></A ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:graphNodesM0" ><A NAME="v%3AgraphNodesM0" ></A ></A ><B >graphNodesM0</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:graphNodesM" ><A NAME="v%3AgraphNodesM" ></A ></A ><B >graphNodesM</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:graphNodes" ><A NAME="v%3AgraphNodes" ></A ></A ><B >graphNodes</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => m (gr a b) -> m [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:graphFilterM" ><A NAME="v%3AgraphFilterM" ></A ></A ><B >graphFilterM</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => (<A HREF="Data-Graph-Inductive-Graph.html#t%3AContext" >Context</A > a b -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="Data-Graph-Inductive-Graph.html#t%3AContext" >Context</A > a b]</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:graphFilter" ><A NAME="v%3AgraphFilter" ></A ></A ><B >graphFilter</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => (<A HREF="Data-Graph-Inductive-Graph.html#t%3AContext" >Context</A > a b -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A >) -> m (gr a b) -> m [<A HREF="Data-Graph-Inductive-Graph.html#t%3AContext" >Context</A > a b]</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" ><A NAME="8" ><A NAME="8" >Example: Monadic DFS Algorithm(s) </A ></A ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:dfsGT" ><A NAME="v%3AdfsGT" ></A ></A ><B >dfsGT</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >] -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="doc" ><P >Monadic graph algorithms are defined in two steps: </P ><OL ><LI > define the (possibly parameterized) graph transformer (e.g., dfsGT) (2) run the graph transformer (applied to arguments) (e.g., dfsM) </LI ></OL ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:dfsM" ><A NAME="v%3AdfsM" ></A ></A ><B >dfsM</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >] -> m (gr a b) -> m [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="doc" >depth-first search yielding number of nodes </TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:dfsM'" ><A NAME="v%3AdfsM%27" ></A ></A ><B >dfsM'</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => m (gr a b) -> m [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:dffM" ><A NAME="v%3AdffM" ></A ></A ><B >dffM</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >] -> <A HREF="Data-Graph-Inductive-Query-Monad.html#t%3AGT" >GT</A > m (gr a b) [<A HREF="/usr/share/doc/ghc/html/libraries/containers-0.3.0.0/Data-Tree.html#t%3ATree" >Tree</A > <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="doc" >depth-first search yielding dfs forest </TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:graphDff" ><A NAME="v%3AgraphDff" ></A ></A ><B >graphDff</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => [<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >] -> m (gr a b) -> m [<A HREF="/usr/share/doc/ghc/html/libraries/containers-0.3.0.0/Data-Tree.html#t%3ATree" >Tree</A > <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:graphDff'" ><A NAME="v%3AgraphDff%27" ></A ></A ><B >graphDff'</B > :: <A HREF="Data-Graph-Inductive-Monad.html#t%3AGraphM" >GraphM</A > m gr => m (gr a b) -> m [<A HREF="/usr/share/doc/ghc/html/libraries/containers-0.3.0.0/Data-Tree.html#t%3ATree" >Tree</A > <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode" >Node</A >]</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="botbar" >Produced by <A HREF="http://www.haskell.org/haddock/" >Haddock</A > version 2.6.1</TD ></TR ></TABLE ></BODY ></HTML >