Modulefgl-5.8.3.1Haskell98

Data.Graph.Inductive.Query.Monad

Monadic Graph Algorithms

Contents

Additional Graph Utilities
Graph Transformer Monad
Graph Computations Based on Graph Monads
Monadic Graph Accessing Functions
Derived Graph Recursion Operators
Examples: Graph Algorithms as Instances of Recursion Operators
Instances of graphRec
Example: Monadic DFS Algorithm(s)

Synopsis

value mapFst
value mapSnd
value ><
value orP
newtype GT
value apply
value apply'
value applyWith
value applyWith'
value runGT
value condMGT'
value recMGT'
value condMGT
value recMGT
value getNode
value getContext
value getNodes'
value getNodes
value sucGT
value sucM
value graphRec
value graphRec'
value graphUFold
value graphNodesM0
value graphNodesM
value graphNodes
value graphFilterM
value graphFilter
value dfsGT
value dfsM
value dfsM'
value dffM
value graphDff
value graphDff'

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

Additional Graph Utilities

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

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.3.1 · Data.Graph.Inductive.Query.Monad
Monad m => Functor (GT m g)Defined in fgl-5.8.3.1 · Data.Graph.Inductive.Query.Monad
Monad m => Applicative (GT m g)Defined in fgl-5.8.3.1 · 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

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

Source#

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

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)

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

Source#

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]

Source#

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]

Source#

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]