graph-rewriting 0.7.10 → 0.8.0

raw patch · 5 files changed

+58/−38 lines, 5 filesdep ~basedep ~containersPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base, containers

API changes (from Hackage documentation)

Files

• GraphRewriting/Graph/Internal.hs +7/−5
• GraphRewriting/Graph/Read.hs +19/−14
• GraphRewriting/Pattern.hs +22/−14
• GraphRewriting/Rule.hs +3/−0
• graph-rewriting.cabal +7/−5

@@ -1,4 +1,4 @@-{-# LANGUAGE UnicodeSyntax, TypeSynonymInstances, FlexibleInstances, MultiParamTypeClasses, FlexibleContexts, GeneralizedNewtypeDeriving, StandaloneDeriving #-}+{-# LANGUAGE UnicodeSyntax, FlexibleInstances, MultiParamTypeClasses, FlexibleContexts, GeneralizedNewtypeDeriving, StandaloneDeriving #-} module GraphRewriting.Graph.Internal where  import Prelude.Unicode@@ -14,6 +14,8 @@ newtype Rewrite n a = Rewrite {rewrite ∷ State (Graph n) a} 	deriving (MonadState (Graph n), Monad, Functor, MonadFix) +instance MonadFail (Rewrite n) where fail = error+ deriving instance Applicative (Rewrite n)  newtype Node = Node {nKey ∷ Int} deriving (Eq, Ord) -- TODO: change this into Integer to avert overflow@@ -25,12 +27,12 @@  instance MonadReader (Graph n) (Rewrite n) where 	ask = Rewrite get-	local f m = Rewrite $ liftM (evalState (rewrite m) . f) get+	local f m = Rewrite $ gets (evalState (rewrite m) . f) -readRef ∷ Monad m ⇒ Int → IntMap a → m a+readRef ∷ MonadFail m ⇒ Int → IntMap a → m a readRef key = maybe (fail "readRef: referentiation failed") return . Map.lookup key -readEdge ∷ MonadReader (Graph n) r ⇒ Edge → r IntSet+readEdge ∷ MonadFail r ⇒ MonadReader (Graph n) r ⇒ Edge → r IntSet readEdge (Edge e) = maybe (fail $ "readEdge: edge with ID " ⧺ show e ⧺ " does not exist") return . readRef e =<< asks edgeMap  modifyNodeMap ∷ (IntMap n → IntMap n) → Rewrite n ()@@ -48,7 +50,7 @@  -- | Hand out an infinite number of fresh refs, without reserving them (obviously). freeRefs ∷ MonadReader (Graph n) r ⇒ r [Int]-freeRefs = enumFrom `liftM` asks nextKey+freeRefs = asks (enumFrom . nextKey)  reserveRefs ∷ [Int] → Rewrite n () reserveRefs refs = modify $ \g → g {nextKey = maximum refs}

@@ -1,4 +1,4 @@-{-# LANGUAGE UnicodeSyntax, FlexibleContexts, FlexibleInstances, TypeSynonymInstances, MultiParamTypeClasses #-}+{-# LANGUAGE UnicodeSyntax, FlexibleContexts, FlexibleInstances, TypeSynonymInstances, MultiParamTypeClasses, ScopedTypeVariables #-}  -- | Enquiry of the graph structure. Note: In this module the term "node" is often used synonymously to "node reference" and "node value". The two can easily distinguished by their type: the former has type 'Node' the latter usually 'n'. module GraphRewriting.Graph.Read@@ -26,15 +26,15 @@ existNode ∷ MonadReader (Graph n) m ⇒ Node → m Bool existNode (Node n) = liftM (Map.member n) (asks nodeMap) -readNode ∷ MonadReader (Graph n) m ⇒ Node → m n+readNode ∷ (MonadReader (Graph n) m, MonadFail m) ⇒ Node → m n readNode (Node n) = maybe (fail $ "readNode: node with ID " ⧺ show n ⧺ " does not exist") return . readRef n =<< asks nodeMap  -- | a wrapper to 'inspect' the given node-inspectNode ∷ (View v n, MonadReader (Graph n) m) ⇒ Node → m v+inspectNode ∷ (View v n, MonadReader (Graph n) m, MonadFail m) ⇒ Node → m v inspectNode = liftM inspect . readNode  -- | a wrapper to 'examine' the given node-examineNode ∷ (View v n, MonadReader (Graph n) m) ⇒ (v → a) → Node → m a+examineNode ∷ (View v n, MonadReader (Graph n) m, MonadFail m) ⇒ (v → a) → Node → m a examineNode f = liftM (examine f) . readNode  -- | all of the graph's nodes@@ -46,39 +46,44 @@ readEdgeList = liftM (map Edge . Map.keys) (asks edgeMap)  -- | edges attached to the given node-attachedEdges ∷ (View [Port] n, MonadReader (Graph n) m) ⇒ Node → m [Edge]+attachedEdges ∷ (View [Port] n, MonadReader (Graph n) m, MonadFail m) ⇒ Node → m [Edge] attachedEdges = liftM nub . inspectNode  -- | non-empty set of nodes attached to the given edge-attachedNodes ∷ MonadReader (Graph n) m ⇒ Edge → m [Node]+attachedNodes ∷ (MonadReader (Graph n) m, MonadFail m) ⇒ Edge → m [Node] attachedNodes = liftM (map Node . Set.elems) . readEdge  -- | amount of ports the given hyperedge is connected to-edgeCardinality ∷ (View [Port] n, MonadReader (Graph n) m) ⇒ Edge → m Int+edgeCardinality ∷ (View [Port] n, MonadReader (Graph n) m, MonadFail m) ⇒ Edge → m Int edgeCardinality e = liftM (length . filter (e ≡) . concat) (mapM inspectNode =<< attachedNodes e)  -- | list of nodes that are connected to the given node, not including the node itself-neighbours ∷ (View [Port] n, MonadReader (Graph n) m) ⇒ Node → m [Node]+neighbours ∷ (View [Port] n, MonadReader (Graph n) m, MonadFail m) ⇒ Node → m [Node] neighbours n = do-	is ← liftM Set.unions $ mapM readEdge =<< inspectNode n+	ports ∷ [Port] ← inspectNode n+	edges ← mapM readEdge ports+	let is = Set.unions edges+	-- TODO: implement in terms of [relatives] 	return $ map Node $ Set.elems $ Set.delete (nKey n) is  -- | list of nodes that are connected to the given node, including the node itself-relatives ∷ (View [Port] n, MonadReader (Graph n) m) ⇒ Node → m [Node]+relatives ∷ (View [Port] n, MonadReader (Graph n) m, MonadFail m) ⇒ Node → m [Node] relatives n = do-	is ← liftM Set.unions $ mapM readEdge =<< inspectNode n+	ports ∷ [Port] ← inspectNode n+	edges ← mapM readEdge ports+	let is = Set.unions edges 	return $ map Node $ Set.elems is  -- | nodes connected to given port of the specified node, not including the node itself-adverseNodes ∷ MonadReader (Graph n) m ⇒ Node → Port → m [Node]+adverseNodes ∷ (MonadReader (Graph n) m, MonadFail m) ⇒ Node → Port → m [Node] adverseNodes (Node n) p = liftM (map Node . Set.elems . Set.delete n) (readEdge p)  -- | whether two nodes are connected-connected ∷ (View [Port] n, MonadReader (Graph n) m) ⇒ Node → Node → m Bool+connected ∷ (View [Port] n, MonadReader (Graph n) m, MonadFail m) ⇒ Node → Node → m Bool connected n1 n2 = liftM (n2 ∈) (relatives n2)  -- | whether the given ports features a dangling edge-dangling ∷ (View [Port] n, MonadReader (Graph n) m) ⇒ Port → m Bool+dangling ∷ (View [Port] n, MonadReader (Graph n) m, MonadFail m) ⇒ Port → m Bool dangling = liftM (≡ 1) . edgeCardinality  -- | Map node-relative enquiry over the nodes of the graph.

@@ -7,7 +7,7 @@ import GraphRewriting.Graph.Read import Control.Monad.Reader import Control.Monad.List-import Control.Monad.Identity+import Data.Functor.Identity import qualified Data.Set as Set (empty, insert, member) import Control.Applicative @@ -15,12 +15,17 @@ -- | A pattern represents a graph scrutinisation that memorises all the scrutinised nodes during matching. type Pattern n = PatternT n Identity +instance MonadFail Identity where+	fail = error+ instance Monad m ⇒ Monad (PatternT n m) where 	return x = PatternT $ \h → return ([],x) 	p >>= f = PatternT $ \h → do 		(m1,x) ← patternT p h 		(m2,y) ← patternT (f x) (reverse m1 ⧺ h) 		return (m1 ⧺ m2, y)++instance MonadFail m ⇒ MonadFail (PatternT n m) where 	fail str = PatternT $ \h → lift (fail str)  instance MonadTrans (PatternT n) where@@ -38,15 +43,18 @@ 		f' ← f 		f' <$> x -instance Monad m ⇒ Alternative (PatternT n m) where+instance MonadFail m ⇒ Alternative (PatternT n m) where 	empty = mzero 	(<|>) = mplus -instance Monad m ⇒ Monoid (PatternT n m a) where+instance MonadFail m ⇒ Semigroup (PatternT n m a) where+	(<>) = mplus++instance MonadFail m ⇒ Monoid (PatternT n m a) where 	mempty = mzero 	mappend = mplus -instance Monad m ⇒ MonadPlus (PatternT n m) where+instance MonadFail m ⇒ MonadPlus (PatternT n m) where 	mzero = fail "empty result list" 	mplus p q = PatternT $ \h → do -- TODO: this implements choice. Is mplus the right function for that? 		g ← ask@@ -72,7 +80,7 @@ branch xs = PatternT $ \h → lift $ ListT $ return [([],x) | x ← xs]  -- | 'branch' on each node, add it to the history, and return it-branchNodes ∷ Monad m ⇒ [Node] → PatternT n m Node+branchNodes ∷ MonadFail m ⇒ [Node] → PatternT n m Node branchNodes ns = do -- TODO: express this using Alternative? 	n ← branch ns 	visit n@@ -99,15 +107,15 @@ anyOf = foldr (<|>) empty  -- | conditional rewriting: 'fail' when predicate is not met-require ∷ Monad m ⇒ Bool → m ()+require ∷ MonadFail m ⇒ Bool → m () require p = unless p $ fail "requirement not met"  -- | 'fail' if given pattern succeeds, succeed if it fails.-requireFailure ∷ Monad m ⇒ PatternT n m a → PatternT n m ()+requireFailure ∷ MonadFail m ⇒ PatternT n m a → PatternT n m () requireFailure p = require . not =<< probe p  -- | 'fail' when monadic predicate is not met-requireM ∷ Monad m ⇒ m Bool → m ()+requireM ∷ MonadFail m ⇒ m Bool → m () requireM p = p >>= require  -- some base patterns --------------------------------------------------------@@ -119,7 +127,7 @@ 	return ([],x)  -- | any node anywhere in the graph-node ∷ (Monad m, View v n) ⇒ PatternT n m v+node ∷ (MonadFail m, View v n) ⇒ PatternT n m v node = liftReader . inspectNode =<< branchNodes =<< liftReader readNodeList  -- | A specific node@@ -133,7 +141,7 @@ edge = branch =<< liftReader readEdgeList  -- | node that is connected to given edge-nodeWith ∷ (Monad m, View v n) ⇒ Edge → PatternT n m v+nodeWith ∷ (MonadFail m, View v n) ⇒ Edge → PatternT n m v nodeWith e = liftReader . inspectNode =<< branchNodes =<< liftReader (attachedNodes e)  -- | edge that is attached to given node@@ -141,22 +149,22 @@ edgeOf n = branch =<< liftReader (attachedEdges n)  -- | node that is connected to the given node, but not that node itself-neighbour ∷ Monad m => (View [Port] n, View v n) ⇒ Node → PatternT n m v+neighbour ∷ (MonadFail m) => (View [Port] n, View v n) ⇒ Node → PatternT n m v neighbour n = liftReader . inspectNode =<< branchNodes =<< liftReader (neighbours n)  -- | node that is connected to the given node, permitting the node itself-relative ∷ (Monad m, View [Port] n, View v n) ⇒ Node → PatternT n m v+relative ∷ (MonadFail m, View [Port] n, View v n) ⇒ Node → PatternT n m v relative n = liftReader . inspectNode =<< branchNodes =<< liftReader (relatives n)  -- | nodes connected to given port of the specified node, not including the node itself. -- Consider as an alternative 'linear' combined with 'nodeWith'.-adverse ∷ (Monad m, View [Port] n, View v n) ⇒ Port → Node → PatternT n m v+adverse ∷ (MonadFail m, View [Port] n, View v n) ⇒ Port → Node → PatternT n m v adverse p n = liftReader . inspectNode =<< branchNodes =<< liftReader (adverseNodes n p)  -- controlling history and future --------------------------------------------  -- | A specific node-visit ∷ Monad m ⇒ Node → PatternT n m ()+visit ∷ MonadFail m ⇒ Node → PatternT n m () visit n = do 	exists ← liftReader $ existNode n 	if exists

@@ -69,6 +69,9 @@ 		return (f x, merges1 ⧺ merges2) 	pure = return +instance Semigroup (Replace n ()) where+	(<>) = (>>)+ instance Monoid (Replace n ()) where 	mempty = return () 	mappend = (>>)

@@ -1,5 +1,5 @@ Name:           graph-rewriting-Version:        0.7.10+Version:        0.8.0 Copyright:      (c) 2010, Jan Rochel License:        BSD3 License-File:   LICENSE@@ -11,15 +11,16 @@ Description:   This library provides a monadic EDSL to define your own port graph rewrite system in Haskell. Once you have specified the signature of your nodes and a set of rewrite rules, you can apply these rules on a graph to effect a graph transformation. The aim of this library is to make it as convenient as possible to define such a system and experiment with it and is not intended as a backend for high-performance computation. Category:       Graphs-Cabal-Version:  >= 1.6+Cabal-Version:  >= 1.10 Extra-Source-Files: AUTHORS  Library+  Default-Language: Haskell2010   Build-Depends:-    base >= 4.8 && < 4.10,+    base >= 4.9 && < 5,     base-unicode-symbols >= 0.2 && < 0.3,     mtl >= 1.1 && < 2.3,-    containers >= 0.3 && < 0.6+    containers >= 0.3 && < 0.7   Exposed-Modules:     Data.View     GraphRewriting@@ -35,11 +36,12 @@     GraphRewriting.Graph.Internal     GraphRewriting.Pattern.Internal     GraphRewriting.Rule.Internal-  Extensions:+  Other-Extensions:     UnicodeSyntax     FlexibleContexts     FlexibleInstances     TypeSynonymInstances     MultiParamTypeClasses     GeneralizedNewtypeDeriving+    ScopedTypeVariables   GHC-Options:    -fno-warn-duplicate-exports -fwarn-unused-binds -fwarn-unused-imports -fwarn-unused-do-bind -fwarn-wrong-do-bind -fwarn-unrecognised-pragmas -fno-warn-tabs