Comments (13)
@l-d-s Many thanks for the link! All ringad laws given in Fig. 1 hold when we define empty = mzero
and overlay = mplus
. There is also this interesting quote in the conclusions:
The laws that one should require for
MonadPlus
andMonadZero
are a subject of great debate; arguably, one expects different laws for backtracking search, for nondeterministic enumeration, and for collections of results [...]
So, it looks like I'm wrong that MonadPlus
semantically corresponds to choice.
I think the intention for type classes is that a given class has no semantics beyond its laws
Hmm, this sounds a bit unexpected to me, but this approach surely allows to maximise code reuse.
To sum up: I think I'm gradually getting convinced that higher-kinded graphs should be defined as:
class MonadPlus g => Graph g where
connect :: g a -> g a -> g a
empty :: Graph g => g a
empty = mzero
vertex :: Graph g => a -> g a
vertex = pure
overlay :: Graph g => g a -> g a -> g a
overlay = mplus
With the above definitions we can reuse a couple of standard functions:
overlays :: Graph g => [g a] -> g a
overlays = msum
induce :: Graph g => (a -> Bool) -> g a -> g a
induce = mfilter
from alga.
Interesting thanks for letting me know! By the way my interest comes from having started to contribute to purescript-alga with the intention to play with graph comonads as described here http://blog.higher-order.com/blog/2016/04/02/a-comonad-of-graph-decompositions/
I might contribute back here if there's interest :) And maybe help move Relations in its own package too.
By the way, once you start postponing the actual evaluation (which requires Ord a), you might as well switch to working with the algebraic data type (from Algebra.Graph) until the last moment you need to go to sets and start needing Ord a everywhere.
I think I get what you mean, I'm not working with concrete graphs yet so I'm focusing on the type class hierarchy as I find it easier to reason about for now. I think I understand that it somewhat makes the computational complexity more opaque about but I'm willing to trade that off, I was wondering if it was even possible or if there was something I was missing :)
from alga.
The good thing about this approach is that fully-parametric graph representations, such as, data Graph a
can define both instances and therefore users can work with them using the most convenient interface.
Here is a snippet from Algebra.Graph.Data
:
data Graph a = Empty
| Vertex a
| Overlay (Graph a) (Graph a)
| Connect (Graph a) (Graph a)
deriving (Foldable, Functor, Show, Traversable)
instance C.Graph (Graph a) where
type Vertex (Graph a) = a
empty = Empty
vertex = Vertex
overlay = Overlay
connect = Connect
instance H.Graph Graph where
empty = Empty
overlay = Overlay
connect = Connect
from alga.
You can also add a stronger MonadPlus
constraint to the Graph
class, where mzero
takes the role of empty
and mplus
takes the role of connect
from alga.
Oops, I meant that mplus
takes the role of overlay
. My understanding is that overlay
is associative and empty
is its identity
from alga.
@Gabriel439 Interesting! I think formally, empty = mzero
and overlay = mplus
does satisfy all MonadPlus
laws listed here: https://wiki.haskell.org/MonadPlus (apart from Left Catch, which seems to be a rather rare alternative to Left Distribution):
mzero
andmplus
should form a monoid, andempty
andoverlay
is a monoid.mzero >>= k = mzero
translates to vertex substitution in theempty
graph:empty >>= k = empty
.mplus a b >>= k = mplus (a >>= k) (b >>= k)
means: if we substitute vertices in anoverlay a b
we get the same result as if we substituted vertices separately ina
andb
and then overlaid the results.
However, we need to also make sure this makes sense semantically. As far as I understand, MonadPlus
is used to represent alternatives, similar to the Alternative
type class. But, as I mentioned before, overlay
doesn't represent alternatives, which is emphasised by the decomposition axiom abc = ab + ac + bc
.
This makes me think that although we formally could make MonadPlus
a superclass of Graph
, we shouldn't do that, because it doesn't make sense semantically and could therefore lead to confusion.
from alga.
MonadPlus
is also used for collections (see e.g. here).
I think the intention for type classes is that a given class has no semantics beyond its laws (and its relationship to other type classes). But I also suspect that overlay
might turn out to have an "alternative"-ish meaning in some contexts.
from alga.
I just realised that we can make Relation
an instance of higher-kinded graphs by postponing the actual evaluation which requires Ord a
until we actually need it, say, to implement the Eq
instance. This essentially means that we can turn pretty much all data structures into higher-kinded equivalents by hiding Data.Graph
inside, which is used to build up fully parametric trees, and then at some point collapsing these trees into more efficient representations, on demand (perhaps, caching this somehow). This collapsing will require various constraints like Ord a
, but it doesn't have to be at the Graph
instance declaration.
from alga.
The latest definition is:
class MonadPlus g => Graph g where
connect :: g a -> g a -> g a
-- reuse empty from Alternative
vertex :: Graph g => a -> g a
vertex = pure
overlay :: Graph g => g a -> g a -> g a
overlay = (<|>)
If we are going this way, it may be useful to also make Foldable
a superclass.
from alga.
I've released the library with higher-kinded class available in the Algebra.Graph.HigherKinded.Class
module:
http://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph-HigherKinded-Class.html
from alga.
Hello there, I'm curious about whether this turned out to be false or if there is another reason why Relation doesn't have a H.Graph
instance?
I just realised that we can make Relation an instance of higher-kinded graphs by postponing the actual evaluation which requires Ord a until we actually need it, say, to implement the Eq instance.
from alga.
@jmatsushita I think the reason is that Relation
isn't used much and so no one really wanted an instance of H.Graph
. In fact, it's not clear we should keep Relation
in the library since a few people remarked that it can be confusing to see so many different versions of more or less the same thing. (Perhaps, we could move it to a separate library algebraic-relations
?)
By the way, once you start postponing the actual evaluation (which requires Ord a
), you might as well switch to working with the algebraic data type (from Algebra.Graph
) until the last moment you need to go to sets and start needing Ord a
everywhere.
from alga.
with the intention to play with graph comonads as described here
That's cool! I remember reading that blog post and thinking about how I could possibly make an efficient comonad instance for algebraic graphs. I never came up with anything but I hope you'll succeed where I failed!
I might contribute back here if there's interest :) And maybe help move Relations in its own package too.
Sure, that would be great!
from alga.
Related Issues (20)
- How to handle goodness inherited from other libraries HOT 2
- Bump upper bound for base-compat for version 0.4 on Hackage HOT 4
- Unable to use ghcid HOT 6
- Algorithms should be in terms of typeclasses not data structures HOT 15
- Acyclic graphs with Int labels HOT 5
- Tests failed to build with QuickCheck 2.14.2
- Multitree HOT 3
- Monoid instance HOT 6
- support for GraphViz "HTML strings" for node or edge labels HOT 1
- Add benchmarks to CI HOT 2
- Supporting different node and edge types HOT 7
- v0.6 fails to build with GHC 8.0 and 8.2 HOT 3
- Doubt about decorating a Graph HOT 4
- Compatibility with mtl-2.3 HOT 2
- Smart constructor for Symbol rather than requiring -XOverloadedLists HOT 1
- Proposal : foldgM HOT 2
- Algebra.Graph.Labelled.AdjacencyMap.edges appears to be broken HOT 2
- Semigroup version of Algebra.Graph.Labelled.AdjacencyMap HOT 7
- Bump "deepseq" dependency bounds to 1.5.0.0 HOT 2
- Warnings when building with ghc-9.10
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from alga.