Comments (12)
There are good discussions on TF vs MPTC+FD in the "Associated Type Synonyms" paper:
https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/at-syns.pdf
and here: https://ghc.haskell.org/trac/ghc/wiki/TFvsFD
However, most arguments (e.g. expressivity) appear to be non-applicable to our simple case.
from alga.
@ndmitchell has written a draft implementation with MPTC
here: https://gist.github.com/ndmitchell/800fb7bf65f5875a22e72b1b868e1442
There is no functional dependency | g -> a
which I have in the above snippet, which makes me wonder if it's really necessary (I think it seemed to be in my experiments).
from alga.
Note that g
is higher kinded. If g
had been *
kind then you would need the FD. As it is, often g
gives you the restriction automatically. Having | g -> a
with the higher-kind would be a bad idea, since it rules out lots of useful instances.
from alga.
Ah, I see!
So it is possible to have a higher-kinded g
and define not fully-parametric Graph
instances... we probably still lose some instances though, for example, IntAdjacencyMap
or ()
... not that the latter is very useful :-) But the former probably is.
Thanks! This is an interesting design point I haven't considered.
from alga.
You don't really lose any instances since you can have a new type with a phantom parameter. You certainly make those ones a bit harder to use though - but they are pretty rare so no big deal.
from alga.
Good point.
So, let's summarise the pros and cons of TF
and your higher-kinded version of MPTC
.
Some examples of type signatures:
ab :: (Graph g, Vertex g ~ Char) => g
ab :: Graph g Char => g Char
ab = connect (vertex 'a') (vertex 'b')
overlays :: Graph g => [g] -> g
overlays :: Graph g a => [g a] -> g a
edges :: Graph g => [(Vertex g, Vertex g)] -> g
edges :: Graph g a => [(a, a)] -> g a
path :: Graph g => [Vertex g] -> g
path :: Graph g a => [a] -> g a
gmap :: Graph g => (a -> Vertex g) -> GraphFunctor a -> g
gmap :: Graph g b => (a -> b) -> GraphFunctor a -> g b
box :: (Graph g, Vertex g ~ (u, v)) => GraphFunctor u -> GraphFunctor v -> g
box :: Graph g (u, v) => GraphFunctor u -> GraphFunctor v -> g (u, v)
I'd say there is no clear winner here. MPTC
signatures are usually a bit shorter, but TF
may be easier to parse since Vertex g
is quite readable/self-documentary. My weak vote goes to TF
.
Dealing with non-fully parametric instances may require workarounds with MPTC
. Here TF
win.
Any other points to consider?
from alga.
MPTC is a much older, simpler and more common extension than TF. I suspect you are less likely to have type inference problems in corner cases, especially when composing things.
I find the MPTC much simpler to read than TF. Yes, Vertex isn't explicit, but as soon as you define more complex operations it is easier to keep track of. As examples of things mentioning more than one graph/vertex type:
replaceGraph :: (Graph g1, Graph g2, Vertex g1 ~ a, Vertex g2 ~ a) => g1 -> g2
replaceVertex :: (Graph g1, Graph g2, Vertex g1 ~ a, Vertex g2 ~ b) => g1 -> g2
replaceGraph :: (Graph g1 a, Graph g2 a) => g1 a -> g2 a
replaceVertex :: (Graph g a, Graph g b) => g a -> g b
What issues were you expecting with non-fully parametric instances?
from alga.
As examples of things mentioning more than one graph/vertex type:
Indeed, these are good examples where MPTC
is clearer.
What issues were you expecting with non-fully parametric instances?
Well, as discussed above, you can't make IntAdjacencyMap
and ()
an instance without workarounds.
P.S.: Just to show why I care about strange things like ()
having a Graph
instance -- in some cases ()
acts as the identity on graph operations, particularly various products:
-- Below ~~ stands for the equality up to an isomorphism, e.g. (x, ()) ~~ x
box x y ~~ box y x
box x (box y z) ~~ box (box x y) z
box x () ~~ x
box x empty ~~ empty -- i.e. empty is annihilating zero for the box operation!
from alga.
Hmm, the following ConstraintKinds
hack seems to work:
{-# LANGUAGE ConstraintKinds #-}
type Graphable g a = (Graph g, Vertex g ~ a)
edges :: Graphable g a => [(a, a)] -> g
Here g
is not higher-kinded because the underlying type class isn't.
With this approach we can have both TF
and MPTC
like type signatures.
We can define Graphable g a
in Algebra.Graph.Classes
, or let users of the library define it themselves, which saves us from the struggle of finding a good name for this constraint synonym. (Not sure about the name Graphable
, just reusing @ndmitchell's name.)
from alga.
You still don't get MPTC like type signatures - you get a simpler context in the examples above, but the signature itself is still clearer with MPTC (the bit changing is clearer).
For things like ()
you can make Const ()
instead and it behaves the same. It's definitely not as clear as TF though.
from alga.
@ndmitchell Have a look at #9 -- higher-kinded class MonadPlus g => Graph g
clearly gives us best type signatures, which can be used when working with Data.Graph
and other fully parametric graph representations.
Furthermore, 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 collapsing these trees into more efficient representations. This collapsing will require various constraints like Ord a
, but it doesn't have to be at the Graph
instance declaration.
from alga.
I think the solution we currently have is optimal: Algebra.Graph.Class
defines a kind-* class, which is most general, and Algebra.Graph.HigherKinded.Class
defines higher-kinded graphs with nice type signatures.
Users who don't care about type classes can happily use Algebra.Graph
with nicest possible (monomorphic) type signatures.
from alga.
Related Issues (20)
- Hackage Release HOT 5
- 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
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.