| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell98 |
Reactive.Banana.Prim.Low.GraphGC
Contents
Synopsis
- data GraphGC v
- listReachableVertices :: GraphGC v -> IO [Ref v]
- getSize :: GraphGC v -> IO Int
- new :: IO (GraphGC v)
- insertEdge :: (Ref v, Ref v) -> GraphGC v -> IO ()
- clearPredecessors :: Ref v -> GraphGC v -> IO ()
- data Step
- walkSuccessors :: Monad m => [Ref v] -> (WeakRef v -> m Step) -> GraphGC v -> IO (m [WeakRef v])
- walkSuccessors_ :: Monad m => [Ref v] -> (WeakRef v -> m Step) -> GraphGC v -> IO (m ())
- removeGarbage :: GraphGC v -> IO ()
- printDot :: (Unique -> WeakRef v -> IO String) -> GraphGC v -> IO String
Documentation
A directed graph whose edges are mutable and whose vertices are subject to garbage collection.
The vertices of the graph are mutable references of type 'Ref v'.
Generally, the vertices of the graph are not necessarily kept reachable
by the GraphGC data structure
— they need to be kept reachable by other parts of your program.
That said, the edges in the graph do introduce additional reachability
between vertices:
Specifically, when an edge (x,y) is present in the graph,
then the head y will keep the tail x reachable.
(But the liveness of y needs to come from elsewhere, e.g. another edge.)
Use insertEdge to insert an edge.
Moreover, when a vertex is removed because it is no longer reachable, then all edges to and from that vertex will also be removed. In turn, this may cause further vertices and edges to be removed.
Concerning garbage collection:
Note that vertices and edges will not be removed automatically
when the Haskell garbage collector runs —
they will be marked as garbage by the Haskell runtime,
but the actual removal of garbage needs
to be done explicitly by calling removeGarbage.
This procedure makes it easier to reason about the state of the GraphGC
during a call to e.g. walkSuccessors.
listReachableVertices :: GraphGC v -> IO [Ref v] Source #
List all vertices that are reachable and have at least one edge incident on them. TODO: Is that really what the function does?
insertEdge :: (Ref v, Ref v) -> GraphGC v -> IO () Source #
Insert an edge from the first vertex to the second vertex.
clearPredecessors :: Ref v -> GraphGC v -> IO () Source #
Remove all the edges that connect the vertex to its predecessors.
walkSuccessors :: Monad m => [Ref v] -> (WeakRef v -> m Step) -> GraphGC v -> IO (m [WeakRef v]) Source #
Walk through all successors. See walkSuccessors.
walkSuccessors_ :: Monad m => [Ref v] -> (WeakRef v -> m Step) -> GraphGC v -> IO (m ()) Source #
Walk through all successors. See walkSuccessors_.
removeGarbage :: GraphGC v -> IO () Source #
Explicitly remove all vertices and edges that have been marked as garbage by the Haskell garbage collector.