dag: Basic 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

 graph =
   GCons "foo" AllRight $
   GCons "bar" Radical $
   GCons "baz" SuperDuper $
   GNil edges

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" []]

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.

Versions 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 Wed Jan 21 17:59:55 UTC 2015
Distributions NixOS:
Downloads 1909 total (63 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]
Hackage Matrix CI




Maintainer's Corner

For package maintainers and hackage trustees