-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Basic type-safe directed acyclic graphs.
--   
--   This is a type-safe approach for a directed acyclic graph.
--   
--   Edge construction is inductive, creating a "schema":
--   
--   <pre>
--   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 for uniquely edged graphs
--   </pre>
--   
--   Which we use to populate nodes with values:
--   
--   <pre>
--   data Cool = AllRight
--             | Radical
--             | SuperDuper
--   
--   graph = GCons "foo" AllRight $
--     GCons "bar" Radical $
--     GCons "baz" SuperDuper $
--     GNil edges
--   </pre>
--   
--   It's an instance of <a>Functor</a>, but we haven't done much here - it
--   will require a lot of reflection that I don't have time to implement
--   right now - there isn't even binding of value-based <a>GCons</a> keys
--   and <a>ECons</a> edge node labels.
--   
--   Some type tomfoolery:
--   
--   <pre>
--   *Data.Graph.DAG&gt; :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
--   </pre>
--   
--   <pre>
--   *Data.Graph.DAG&gt; :t getSpanningTrees $ edges
--   getSpanningTrees $ edges
--     :: Data.Proxy.Proxy
--          '['Node "foo" '['Node "bar" '['Node "baz" '[]],
--                          'Node "baz" '[]],
--            'Node "bar" '['Node "baz" '[]],
--            'Node "baz" '[]]
--   </pre>
--   
--   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.
@package dag
@version 0.0.1

module Data.Graph.DAG.Edge

-- | We use promoted symbol values for the <tt>from</tt> and <tt>to</tt>
--   type parameters. This is the user-level data type when declaring the
--   list of edges.
data EdgeValue (from :: Symbol) (to :: Symbol)
Edge :: EdgeValue

-- | We need this for type-level computation list.
data EdgeKind
EdgeType :: from -> to -> EdgeKind

-- | Some people just want to watch the world burn. Ideally, this shouldn't
--   exist; poor error messages, and is very square peg - round hole.

-- | <tt>not . elem</tt> for lists of types, resulting in a constraint.

-- | A simple <tt>Data.List.lookup</tt> function for type maps.

-- | Trivial inequality for non-reflexivity of edges

-- | Simply reject anything that's been reached in the other direction. We
--   expect an explicit type signature when uniqueness is needed, otherwise
--   we will wait until invocation to see if the edges are unique.
class Acceptable (a :: EdgeKind) (oldLoops :: [(Symbol, [Symbol])]) (unique :: Bool)

-- | Add an explicit element to the head of a list, if the test is inside
--   that list.

-- | Update the exclusion map with the new edge: the <tt>from</tt> key gets
--   <tt>to</tt> added, likewise with keys that have <tt>from</tt> in it's
--   value list. We need to track if the key exists yet.

-- | <tt>edges</tt> is a list of types with kind <tt>EdgeKind</tt>, while
--   <tt>nearLoops</tt> is a map of the nodes transitively reachable by
--   each node.
data EdgeSchema (edges :: [EdgeKind]) (nearLoops :: [(Symbol, [Symbol])]) (unique :: Bool)
ENil :: EdgeSchema [] [] unique
ECons :: !a -> EdgeSchema old oldLoops unique -> EdgeSchema (b : old) c unique

-- | Utility for constructing an <tt>EdgeSchema</tt> granularly
unique :: EdgeSchema [] [] True
notUnique :: EdgeSchema [] [] False

-- | Trivial rose tree for creating spanning trees
data Tree a
Node :: a -> [Tree a] -> Tree a

-- | Adds an empty <tt>c</tt> tree to the list of trees uniquely

-- | Adds <tt>c</tt> as a child of any tree with a root <tt>t</tt>. Assumes
--   unique roots.

-- | We need to track if <tt>from</tt> has is a root node or not. TODO:
--   Some code repeat.

-- | Add <tt>to</tt> as a child to every <tt>from</tt> node in the
--   accumulator.

-- | Auxilliary function normally defined in a <tt>where</tt> clause for
--   manual folding.

-- | Expects edges to already be type-safe
getSpanningTrees :: EdgeSchema es x unique -> Proxy (SpanningTrees es)
instance (Excluding from (Lookup to excludeMap), Excluding to (Lookup from excludeMap), from =/= to) => Acceptable ('EdgeType from to) excludeMap 'True
instance (Excluding from (Lookup to excludeMap), from =/= to) => Acceptable ('EdgeType from to) excludeMap 'False

module Data.Graph.DAG
data DAG es a
GNil :: EdgeSchema es x unique -> DAG es a
GCons :: key -> a -> DAG es a -> DAG es a
glookup :: String -> DAG es a -> Maybe a
instance Functor (DAG es)