haskell / haskell/fgl

Custom graph invariants

Open
#70 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
200
Forks
58
PR merge metrics
No merged PRs in 30d

Description

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](https://www.reddit.com/r/haskell/comments/6tl5fp/invalid_state_complex_traversals_ways_to/) about the [dependent map](https://hackage.haskell.org/package/dependent-map) library, which implements a map that allows keys to specify the types of values associated with them.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.