Modulefgl-5.8.2.0Haskell98

Data.Graph.Inductive.Query.Monad

Monadic Graph Algorithms

1 type
33 values

Packagefgl-5.8.2.0
Exports34
LanguageHaskell98
LicenceBSD-3-Clause
SourceMonad.hs

Additional Graph Utilities

4 declarations

valuemapFst :: (a -> b) -> (a, c) -> (b, c)

valuemapSnd :: (a -> b) -> (c, a) -> (c, b)

value(><) :: (a -> b) -> (c -> d) -> (a, c) -> (b, d)

valueorP :: (a -> Bool) -> (b -> Bool) -> (a, b) -> Bool

Graph Transformer Monad

10 declarations

newtypenewtype GT (m :: Type -> Type) g a

Constructors

MGT (m g -> m (a, g))

Instances3Monad, Functor, Applicative

Monad m => Monad (GT m g)Defined in fgl-5.8.2.0 · Data.Graph.Inductive.Query.Monad
Monad m => Functor (GT m g)Defined in fgl-5.8.2.0 · Data.Graph.Inductive.Query.Monad
Monad m => Applicative (GT m g)Defined in fgl-5.8.2.0 · Data.Graph.Inductive.Query.Monad

valueapply :: GT m g a -> m g -> m (a, g)

valueapply' :: Monad m => GT m g a -> g -> m (a, g)

valueapplyWith :: Monad m => (a -> b) -> GT m g a -> m g -> m (b, g)

valueapplyWith' :: Monad m => (a -> b) -> GT m g a -> g -> m (b, g)

valuerunGT :: Monad m => GT m g a -> m g -> m a

valuecondMGT' :: Monad m => (s -> Bool) -> GT m s a -> GT m s a -> GT m s a

valuerecMGT'

:: Monad m
=> s -> Bool
-> GT m s a
-> a -> b -> b
-> b
-> GT m s b

valuecondMGT :: Monad m => (m s -> m Bool) -> GT m s a -> GT m s a -> GT m s a

valuerecMGT

:: Monad m
=> m s -> m Bool
-> GT m s a
-> a -> b -> b
-> b
-> GT m s b

Graph Computations Based on Graph Monads

0 declarations

Monadic Graph Accessing Functions

valuegetNode :: GraphM m gr => GT m (gr a b) Node

valuegetContext :: GraphM m gr => GT m (gr a b) (Context a b)

valuegetNodes' :: (Graph gr, GraphM m gr) => GT m (gr a b) [Node]

valuegetNodes :: GraphM m gr => GT m (gr a b) [Node]

valuesucGT :: GraphM m gr => Node -> GT m (gr a b) (Maybe [Node])

valuesucM :: GraphM m gr => Node -> m (gr a b) -> m (Maybe [Node])

Derived Graph Recursion Operators

valuegraphRec

:: GraphM m gr
=> GT m (gr a b) c
-> c -> d -> d
-> d
-> GT m (gr a b) d

encapsulates a simple recursion schema on graphs

valuegraphRec'

:: (Graph gr, GraphM m gr)
=> GT m (gr a b) c
-> c -> d -> d
-> d
-> GT m (gr a b) d

valuegraphUFold :: GraphM m gr => (Context a b -> c -> c) -> c -> GT m (gr a b) c

Examples: Graph Algorithms as Instances of Recursion Operators

0 declarations

Instances of graphRec

valuegraphNodesM0 :: GraphM m gr => GT m (gr a b) [Node]

valuegraphNodesM :: GraphM m gr => GT m (gr a b) [Node]

valuegraphNodes :: GraphM m gr => m (gr a b) -> m [Node]

valuegraphFilterM

:: GraphM m gr
=> Context a b -> Bool
-> GT m (gr a b) [Context a b]

valuegraphFilter

:: GraphM m gr
=> Context a b -> Bool
-> m (gr a b)
-> m [Context a b]

Example: Monadic DFS Algorithm(s)

6 declarations

valuedfsGT :: GraphM m gr => [Node] -> GT m (gr a b) [Node]

Monadic graph algorithms are defined in two steps:

define the (possibly parameterized) graph transformer (e.g., dfsGT)
run the graph transformer (applied to arguments) (e.g., dfsM)

valuedfsM :: GraphM m gr => [Node] -> m (gr a b) -> m [Node]

depth-first search yielding number of nodes

valuedfsM' :: GraphM m gr => m (gr a b) -> m [Node]

valuedffM :: GraphM m gr => [Node] -> GT m (gr a b) [Tree Node]

depth-first search yielding dfs forest

valuegraphDff :: GraphM m gr => [Node] -> m (gr a b) -> m [Tree Node]

valuegraphDff' :: GraphM m gr => m (gr a b) -> m [Tree Node]