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


-- | Compile-time, 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
--   
--   nodes =
--     nadd "foo" AllRight $
--     nadd "bar" Radical $
--     nadd "baz" SuperDuper $
--     nempty
--   </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>
--   
--   We can also look at the edges, first-class:
--   
--   <pre>
--   *Data.Graph.DAG&gt; fcEdges edges
--   
--     [("foo","bar"),("foo","baz"),("bar","baz")]
--   </pre>
--   
--   Note that a <tt>NodeSchema</tt>'s keys don't have to be in-sync with
--   it's paired <tt>EdgeSchema</tt>. After we have both, we can construct
--   a <tt>DAG</tt>:
--   
--   <pre>
--   graph = DAG edges nodes
--   </pre>
--   
--   Now we can do fun things, like get the spanning tree of a node:
--   
--   <pre>
--   *Data.Graph.DAG&gt; gtree "foo" graph
--   
--     Just (AllRight :@-&gt; [Radical :@-&gt; [SuperDuper :@-&gt; []]
--                         ,SuperDuper :@-&gt; []])
--   </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.
--   
--   The main deficiency of this graph is that our <tt>EdgeSchema</tt>
--   can't be <i>deconstructed</i> soundly - there is just too much
--   information loss between the value and type levels. This means we
--   can't delete edges or look inside, but we can still add edges or work
--   with the resulting structure.
@package dag
@version 0.1

module Data.Graph.DAG.Node

-- | This is just a simple inductive list
data NodeSchema a

-- | Simple lookup function.
nlookup :: String -> NodeSchema a -> Maybe a

-- | Delete a node from a collection of nodes.
nremove :: String -> NodeSchema a -> NodeSchema a

-- | We overwrite with rightward prescedence.
ncombine :: NodeSchema a -> NodeSchema a -> NodeSchema a

-- | Uniquely append, or overwrite a node to a collection of nodes.
nadd :: String -> a -> NodeSchema a -> NodeSchema a

-- | Smart constructor for <tt>GNil</tt>.
nempty :: NodeSchema a
instance Show a => Show (NodeSchema a)
instance Eq a => Eq (NodeSchema a)
instance Monoid (NodeSchema a)
instance Functor NodeSchema

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> incrementally without
--   a type signature.
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. We make control
--   structure instances "parallel" (instead of cartesian) by default for
--   simplicity.
data RTree a_abad
(:@->) :: a_abad -> [RTree a_abad] -> RTree a_abad
type SRTree (z_abaw :: RTree a_abad) = Sing z_abaw
type (:@->$$$) (t_abap :: a_abad) (t_abaq :: [] (RTree a_abad)) = (:@->) t_abap t_abaq
data (:@->$$) (l_abau :: a_abad) (l_abat :: TyFun ([] (RTree a_abad)) (RTree a_abad))
(:@->$$###) :: (:@->$$)
data (:@->$) (l_abar :: TyFun a_abad (TyFun ([] (RTree a_abad)) (RTree a_abad) -> *))
(:@->$###) :: (:@->$)

-- | 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)

-- | Get the spanning trees of an <tt>EdgeSchema</tt>. Operate on the
--   assumtion that the data returned is actually <tt>[Tree String]</tt>.
espanningtrees :: SingI (SpanningTrees' es []) => EdgeSchema es x unique -> Demote (SpanningTrees' es [])

-- | Get a single tree.
etree :: SingI (SpanningTrees' es []) => String -> EdgeSchema es x unique -> Maybe (RTree String)

-- | Degenerate (but type-safe!) <tt>head</tt>.
ehead :: (EdgeType from to ~ b, EdgeValue from to ~ a) => EdgeSchema (b : old) c u -> a

-- | For now, we only suport unique edges.
eTreeToEdges :: RTree String -> [(String, String)]

-- | Get a first-class list of edges from spanning trees. Only works on
--   uniqely edged <tt>EdgeSchema</tt>'s.
eForestToEdges :: [RTree String] -> [(String, String)]

-- | Get the <a>First-Class</a> edges of a uniquely-edged
--   <tt>EdgeSchema</tt>.
fcEdges :: SingI (SpanningTrees' es []) => EdgeSchema es x True -> [(String, String)]
instance Show a0 => Show (RTree a0)
instance Eq a0 => Eq (RTree a0)
instance Functor RTree
instance Foldable RTree
instance Monoid a => Monoid (RTree a)
instance Monad RTree
instance Applicative RTree
instance (SingI n0, SingI n1) => SingI (n0 ':@-> n1)
instance SDecide 'KProxy => SDecide 'KProxy
instance SEq 'KProxy => SEq 'KProxy
instance SingKind 'KProxy => SingKind 'KProxy
instance SuppressUnusedWarnings (:@->$)
instance SuppressUnusedWarnings (:@->$$)
instance PEq 'KProxy

module Data.Graph.DAG

-- | A (potentially sparse) directed acyclic graph, composed of edges and
--   nodes.
data DAG es x u a
DAG :: (EdgeSchema es x u) -> (NodeSchema a) -> DAG es x u a
getEdgeSchema :: DAG es x u a -> (EdgeSchema es x u)
getNodeSchema :: DAG es x u a -> (NodeSchema a)

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