graph-visit 0.1 → 0.1.0.1

raw patch · 2 files changed

+24/−9 lines, 2 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• graph-visit.cabal +1/−1
• src/Data/Graph/GraphVisit.hs +23/−8

@@ -1,5 +1,5 @@ Name:				graph-visit-Version:			0.1+Version:			0.1.0.1 cabal-version:      >= 1.6 License:			BSD3 license-file:		LICENSE

@@ -7,6 +7,8 @@     -- * Graph visiting     graphVisitM   , graphVisit+  +    -- * Result   )   where @@ -32,25 +34,38 @@ ------------------------------------------------------------------------------ -- | Abstract graph visit, over arbitrary structures, using state holding visited nodes (also acting als start) and an accumulator 'thr'. -- All is done in strict StateT.-graphVisitM+graphVisitOnStateM   :: (Ord node, Monad m)-     => (thr -> graph -> node -> (thr,Set.Set node))      -- ^ fun: visit node, get new thr and nodes to visit next+     => (thr -> graph -> node -> m (thr,Set.Set node))      -- ^ fun: visit node, get new thr and nodes to visit next      -> graph                                               -- ^ graph over which we visit      -> StateT (GraphVisitState node thr) m ()-graphVisitM visit graph+graphVisitOnStateM visit graph   = v   where v = do           s <- get           unless (Set.null $ s ^. gvsYetToVisit) $ do             let (n, unvisited) 		= Set.deleteFindMin $ s ^. gvsYetToVisit-                (thr, newUnvisited) = visit (s ^. gvsAccum) graph n-                newAndOldVisited 	= Set.insert n $ s ^. gvsVisited-            gvsVisited != newAndOldVisited+            (thr, newUnvisited)    <- lift $ visit (s ^. gvsAccum) graph n+            let newAndOldVisited 	= Set.insert n $ s ^. gvsVisited+            gvsVisited    != newAndOldVisited             gvsYetToVisit != Set.union (newUnvisited `Set.difference` newAndOldVisited) unvisited-            gvsAccum != thr+            gvsAccum      != thr             v  ------------------------------------------------------------------------------+-- | Abstract monadic graph visit, over arbitrary structures, using state holding visited nodes (also acting als start) and an accumulator 'thr'.+graphVisitM+  :: (Ord node, Monad m)+     => (thr -> graph -> node -> m (thr,Set.Set node))      -- ^ fun: visit node, get new thr and nodes to visit next+     -> Set.Set node                                        -- ^ root/start+     -> graph                                               -- ^ graph over which we visit+     -> thr                                                 -- ^ the accumulator, threaded as state+     -> m (thr,Set.Set node)                                -- ^ yield accum and visited+graphVisitM visit start graph thr = do+  s <- execStateT (graphVisitOnStateM visit graph) (GraphVisitState Set.empty start thr)+  return (s ^. gvsAccum, s ^. gvsVisited)++------------------------------------------------------------------------------ -- | Abstract graph visit, running graphVisitM graphVisit   :: (Ord node)@@ -61,4 +76,4 @@      -> (thr,Set.Set node)                                  -- ^ yield accum and visited graphVisit visit start graph thr   = (s ^. gvsAccum, s ^. gvsVisited)-  where s = execState (graphVisitM visit graph) (GraphVisitState Set.empty start thr)+  where s = execState (graphVisitOnStateM (\t g n -> return $ visit t g n) graph) (GraphVisitState Set.empty start thr)