dag
Compile-time, type-safe directed acyclic graphs.
Latest on Hackage: | 0.1.0.2 |
This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.
This is a type-safe approach for a directed acyclic graph.
Edge construction is incremental, creating a "schema":
import Data.Graph.DAG.Edge
-- | Edges are statically defined:
edges =
ECons (Edge :: EdgeValue "foo" "bar") $
ECons (Edge :: EdgeValue "bar" "baz") $
ECons (Edge :: EdgeValue "foo" "baz")
unique -- ENil, but casted for uniquely edged graphs
The nodes are separate from edges; graph may be not connected:
data Cool = AllRight
| Radical
| SuperDuper
nodes =
nadd "foo" AllRight $
nadd "bar" Radical $
nadd "baz" SuperDuper $
nempty
Some type tomfoolery:
*Data.Graph.DAG> :t edges
edges
:: EdgeSchema
'['EdgeType "foo" "bar", 'EdgeType "bar" "baz",
'EdgeType "foo" "baz"] -- Type list of edges
'['("foo", '["bar", "baz"]), '("bar", '["baz"])] -- potential loops
'True -- uniqueness
*Data.Graph.DAG> :t getSpanningTrees $ edges
getSpanningTrees $ edges
:: Data.Proxy.Proxy
'['Node "foo" '['Node "bar" '['Node "baz" '[]]
,'Node "baz" '[]]
,'Node "bar" '['Node "baz" '[]]
,'Node "baz" '[]]
*Data.Graph.DAG> reflect $ getSpanningTrees $ edges
[Node "foo" [Node "bar" [Node "baz" []]
,Node "baz" []]
,Node "bar" [Node "baz" []]
,Node "baz" []]
We can also look at the edges, first-class:
*Data.Graph.DAG> fcEdges edges
[("foo","bar"),("foo","baz"),("bar","baz")]
Note that a NodeSchema
's keys don't have to be in-sync with it's paired
EdgeSchema
. After we have both, we can construct a DAG
:
graph = DAG edges nodes
Now we can do fun things, like get the spanning tree of a node:
*Data.Graph.DAG> gtree "foo" graph
Just (AllRight :@-> [Radical :@-> [SuperDuper :@-> []]
,SuperDuper :@-> []])
This library is still very naive, but it will give us compile-time enforcement of acyclicity (and uniqueness) in these graphs - ideal for dependency graphs.
The main deficiency of this graph is that our EdgeSchema
can't be
deconstructed soundly - there is just too much information loss between the
value and type levels. This means we can't delete edges or look inside, but we
can still add edges or work with the resulting structure.