search

haskell / fgl

A Functional Graph Library for Haskell
http://hackage.haskell.org/package/fgl
Other
184 stars 54 forks source link

Custom graph invariants #70

Open JeffreyBenjaminBrown opened 6 years ago

JeffreyBenjaminBrown commented 6 years ago

Is there a some canonical way to enforce graph invariants in FGL?

I have been using FGL to implement a generalization of graphs that allows for arbitrary arity and nesting of relationships. It looks like this:

type RSLT = Gr Expr Role
data Expr = Word String
          | Template [String] -- e.g. "_ needs _ to _"
          | Relationship      -- e.g. "Gotham needs Batman to hurry"
data Role = TemplateRole | Member Int

Words and Templates emit no edges. Each Relationship emits an edge labeled "TemplateRole" to a Template of arity k, and k more edges, labeled "Member i" for i in [1,k]. Thus the model permits lots of invalid state.

I don't know whether it's relevant, but I just learned about the dependent map library, which implements a map that allows keys to specify the types of values associated with them.

ivan-m commented 6 years ago

There's no way to constrain in FGL which edges are legal.

It may be possible to implement a new FGL type using dependent-maps, but I'm hesitant to add any extra dependencies as it's part of the Haskell Platform.