athanclark/dag

A well-typed Directed Acyclic Graph in Haskell

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

...

dag's Issues

Reifiying Strings to Symbols

This will be difficult. At runtime, we only have someSymbolVal to give us a type-level symbol, but it gives us an existentially quantified type instead of a top-level type. This will be troublesome to make legitimate.

Cabal-Version constraint in Cabal file

Hi, the Cabal file for dag specifies that it must be interpreted Cabal 1.20 or later, when in fact Cabal >= 1.10 would suffice. (Just lower the constraint and run cabal check to verify that you're requiring a recent enough version; if you choose something below >= 1.10 then cabal will complain). Anyway, would you mind editing your Cabal file at http://hackage.haskell.org/package/dag/maintain to allow older versions of Cabal to run that build?

Getting the EdgeSchema from a Graph

This is a major flaw. We need a better design for the graphs. Here is what I'm thinking:

type DAG es a = (EdgeSchema es _ _, Graph_ a)

This way, the edges are top-level, and the types (should be) recoverable. Also, this might give rise to a nice monad:

foo = do -- GraphSchema monad
  node "foo" Foo $ -- EdgeSchema monad
    return ()
  node "bar" Bar $
    "foo" `to` "bar"
  none $ -- Auxilliary way to jump into the edges
    "bar" `to` "foo" -- won't compile

TemplateHaskell / QQ generator

So, the only way we can make this work is with a GADT with two generated dealios:

• Tons of typeclass literals representing a dictionary acceptance bound for possible edges

...actually just one.