Popularity
6.3
Growing
Activity
0.0
Stable
9
4
2

Monthly Downloads: 21
Programming language: Haskell
License: BSD 3-clause "New" or "Revised" License
Tags: Unclassified    

dag alternatives and similar packages

Based on the "Unclassified" category

Do you think we are missing an alternative of dag or a related project?

Add another 'Unclassified' Package

README

Stories in Ready

dag

Directed Acyclic Graphs for Haskell

Description

This is a type-safe directed acyclic graph library for Haskell. This library differs from others in a number of ways:

  • Edge construction is incremental, creating a "schema":
  {-# LANGUAGE DataKinds #-}

  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
  • Type safety throughout edge construction:
  *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
  • Various type-level computation
  *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 in these graphs - ideal for dependency graphs.

Usage

You will need -XDataKinds for the type-level symbols:

{-# LANGUAGE DataKinds #-}

import Data.Graph.DAG
import GHC.TypeLits

...