-- 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 incremental, 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 casted for uniquely edged graphs
--   </pre>
--   
--   The nodes are separate from edges; graph may be not connected:
--   
--   <pre>
--   data Cool = AllRight
--             | Radical
--             | SuperDuper
--   
--   graph =
--     GCons "foo" AllRight $
--     GCons "bar" Radical $
--     GCons "baz" SuperDuper $
--     GNil edges
--   </pre>
--   
--   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
--   
--   *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" '[]]
--   
--   *Data.Graph.DAG&gt; reflect $ getSpanningTrees $ edges
--   
--     [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.2

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
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.Edge.Utils

-- | Trivial rose tree for creating spanning trees
data Tree a_aa2d
Node :: a_aa2d -> [Tree a_aa2d] -> Tree a_aa2d
type STree (z_aa2w :: Tree a_aa2d) = Sing z_aa2w
type NodeSym2 (t_aa2p :: a_aa2d) (t_aa2q :: [] (Tree a_aa2d)) = Node t_aa2p t_aa2q
data NodeSym1 (l_aa2u :: a_aa2d) (l_aa2t :: TyFun ([] (Tree a_aa2d)) (Tree a_aa2d))
NodeSym1KindInference :: NodeSym1
data NodeSym0 (l_aa2r :: TyFun a_aa2d (TyFun ([] (Tree a_aa2d)) (Tree a_aa2d) -> *))
NodeSym0KindInference :: NodeSym0

-- | Gives us a generic way to get our spanning trees of the graph, as a
--   value. Credit goes to <a>András Kovács</a>.
reflect :: (SingI a, SingKind (KProxy :: KProxy k)) => Proxy a -> Demote 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 Show a0 => Show (Tree a0)
instance Eq a0 => Eq (Tree a0)
instance (SingI n0, SingI n1) => SingI ('Node n0 n1)
instance SDecide 'KProxy => SDecide 'KProxy
instance SEq 'KProxy => SEq 'KProxy
instance SingKind 'KProxy => SingKind 'KProxy
instance SuppressUnusedWarnings NodeSym0
instance SuppressUnusedWarnings NodeSym1
instance PEq 'KProxy

module Data.Graph.DAG

-- | The graph may be not connected
data DAG es a
GNil :: EdgeSchema es x unique -> DAG es a
GCons :: String -> a -> DAG es a -> DAG es a

-- | A simple <tt>Data.Map.lookup</tt> duplicate.
glookup :: String -> DAG es a -> Maybe a
instance Functor (DAG es)