# conic-graphs
Vinyl-style extensible graphs.
A [vinyl](https://hackage.haskell.org/package/vinyl) style extensible record is
a hetrogenous list, using a type-level list to track the indicies. The
constructors of `Rec` mirror the constructors of the list used to index them.
```{.haskell}
data Rec :: (u -> *) -> [u] -> * where
RNil :: Rec f '[]
(:&) :: !(f r) -> !(Rec f rs) -> Rec f (r ': rs)
```
We can apply the same method to the
[algebraic-graphs](https://hackage.haskell.org/package/algebraic-graphs)
definition, albeit with four constructors instead of two.
```{.haskell}
data RGraph :: (u -> *) -> Graph u -> * where
REmpty :: RGraph f 'Empty
RVertex :: !(f r) -> RGraph f ('Vertex r)
ROverlay :: !(RGraph f xs) -> !(RGraph f ys) -> RGraph f ('Overlay xs ys)
RConnect :: !(RGraph f xs) -> !(RGraph f ys) -> RGraph f ('Connect xs ys)
```
Then each vertex of the `RGraph` may be of a different type, with the types
tracked in the type level `Graph`.
```{.haskell}
type G = 'Connect ('Vertex Int) ('Vertex String)
myGraph :: RGraph Identity G
myGraph = RConnect (RVertex (Identity 5)) (RVertex (Identity "foo"))
```
Using [fcf-graphs](https://hackage.haskell.org/package/fcf-graphs), we are able
to perform type-level graph computations to match the operations at the term
level.
```{.haskell}
edge :: f a -> f b -> RGraph f (Eval (Edge a b))
edge x y = RConnect (RVertex x) (RVertex y)
```
Including, collapsing RGraphs to vinyl Recs by computing the type level list of
vertex types.
```{.haskell}
data VertexList :: Graph a -> Exp [a]
type instance Eval (VertexList 'Empty) = '[]
type instance Eval (VertexList ('Vertex x)) = '[x]
type instance Eval (VertexList ('Overlay x y)) = Eval (LiftM2 (++) (VertexList x) (VertexList y))
type instance Eval (VertexList ('Connect x y)) = Eval (LiftM2 (++) (VertexList x) (VertexList y))
vertexList :: RGraph f xs -> Rec f (Eval (VertexList xs))
vertexList REmpty = RNil
vertexList (RVertex x) = x :& RNil
vertexList (ROverlay x y) = rappend (vertexList x) (vertexList y)
vertexList (RConnect x y) = rappend (vertexList x) (vertexList y)
```
```
ghci> vertexList myGraph
{5, "foo"}
```
(Note, we use a different version of rappend that makes it more obvious to fcf
that this is what we mean, defined in [fcf-vinyl](https://hackage.haskell.org/package/fcf-vinyl).