Non empty graphs

[snowleopard]

Non empty graphs

[phadej]

A side note, Data.Map.Strict.Map and Data.Map.Lazy.Map are the same datatype! (only functions differ).

I'd prefer to have different names for the types, as the functions will be the same, thanks to the type class machinery,

[snowleopard]

Perhaps, a slightly better approach would be to stick to the name Graph, but use module names to distinguish between general and non-empty graphs?

More specifically:

module Algebra.Graph.NonEmpty (Graph (..)) where

data Graph a = Vertex a
             | Overlay (Graph a) (Graph a)
             | Connect (Graph a) (Graph a)

Now, if one would like to be explicit about the data type, it's possible to write NonEmpty.Graph. And if non-empty graphs are assumed throughout the codebase, then a simple Graph will work.

This is similar to Data.Map.Strict and Data.Map.Lazy that both definine data type Map.

Following this approach we can also have Undirected.Graph, Reflexive.Graph, Undirected.NonEmpty.Graph etc. without the need to invent longer and longer names for various graph data-types.

[snowleopard]

Done!

@phadej Thanks for the suggestion and let me know if you spot any issues with the implementation.

I decided not to add a type class for non-empty graphs for now. I think it deserves a new issue.