dag: Compile-time, type-safe directed acyclic graphs.

[ bsd3, library, unclassified ] [ Propose Tags ]

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 $

Some type tomfoolery:

 *Data.Graph.DAG> :t 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


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.


Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


  • No Candidates
Versions [RSS] 0.0.1, 0.0.2,, 0.1,, (info)
Dependencies base (>=4.7 && <5), constraints, singletons [details]
License BSD-3-Clause
Author Athan Clark <athan.clark@gmail.com>
Maintainer Athan Clark <athan.clark@gmail.com>
Source repo head: git clone https://github.com/athanclark/dag
Uploaded by athanclark at 2015-01-23T18:19:26Z
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 3433 total (8 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]