Haskell FGL using DynGraph Graph functions
My goal is to do things with a shape intersection graph. An intersection graph has nodes: shapes in R ^ n and there is an edge between nodes if they intersect.
In Haskell, one implements a function,
makeIntersectionGraph :: DynGraph g => [Shape] -> g Shape ()
makeIntersectionGraph sh = ... begin with the empty graph and add nodes and edges as you walk
... through all possible intersections
The above compilations and typechecks are great. The simple thing should be to get the nodes of the graph using the labNodes function.
getNodes sh = labNodes (makeIntersectionGraph sh)
Please note that the documentation states:
DynGraph: dynamic, extensible graphics. Dynamic charts inherit all operations from static charts, but also offer operations for expanding and modifying charts.
and labNodes
is a function of the class Graph
. So the above should work.
However, I am getting the error:
No instance for (Graph gr0) arising from a use of `labNodes'
In the expression: labNodes (makeIntersectionGraph es)
In an equation for `makeIntersectionGraphComplete':
makeIntersectionGraphComplete es
= labNodes (makeIntersectionGraph es)
DFN2Graph.hs:346:46:
No instance for (DynGraph gr0)
arising from a use of `makeIntersectionGraph'
In the first argument of `labNodes', namely
`(makeIntersectionGraph es)'
In the expression: labNodes (makeIntersectionGraph es)
In an equation for `makeIntersectionGraphComplete':
makeIntersectionGraphComplete es
= labNodes (makeIntersectionGraph es)
---- Update ---- I found a solution, but I don't understand what the problem is. If I change the type
makeIntersectionGraph :: DynGraph g => [Shape] -> g Shape ()
To
makeIntersectionGraph :: [Shape] -> G.Gr Shape ()
Where
import qualified Data.Graph.Inductive.PatriciaTree as G
Then
getNodes sh = labNodes (makeIntersectionGraph sh)
works great. The problem I still have is that I don't understand why a specific DynGraph implementation needs to be used when all DynGraphs have access to the same functionality.
source to share
You are working with two functions, one that creates a graph and the other that creates a graph. Let's simplify the types and ignore the difference DynGraph
/ Graph
.
makeGraph :: Graph g => [Shape] -> g Shape () makeGraph = undefined consumeGraph :: Graph g => g Shape () -> [LNode Shape] consumeGraph = undefined f :: [Shape] -> [LNode Shape] f = consumeGraph . makeGraph -- same as f x = consumeGraph (makeGraph x)
Edit: break it down a bit:
f :: [Shape] -> [LNode Shape] -- Note: no g!
f shapes = consumeGraph g
where g :: Graph g => g -- This annotation is just illustrative
g = makeGraph shapes
The problem is that it g
doesn't appear in the type signature f
. The compiler could choose any of several types that satisfy the constraint, but this would be arbitrary and it will not.
The fact that everyone Graph
shares the same functionality doesn't really answer the question. Will the intermediate graph use Patricia's tree or the normal tree? It matters. Imagine if we were talking about a type class Num
: we could use Int
either Double
or Integer
or Decimal
, each with completely different performance characteristics and semantics.
So there must be some indication, somewhere, what type you want. Your solution works; if you want to keep the generality makeIntersectionGraph
, you can use internal type annotation on the following lines:
f' :: [Shape] -> [LNode Shape]
f' xs = consumeGraph (makeGraph xs :: G.Gr Shape)
This problem occurs frequently. I think of it as a problem " show . read
"; that's a similar situation. What type are we using in the middle? The Haskell '98 report has a section on "ambiguous types" , which also explains why this problem is masked by default rules when trying to do this with functions Num
.
(Note that GHCi overrides the default rules from the '98 report, so GHCi show . read
does not give a type error.)
Oh, I almost forgot about DynGraph
/ Graph
. If you look at Haddock or the source, you can see what DynGraph
is defined as class Graph gr => DynGraph gr where ...
. As a result, everyone is DynGraph
also Graph
; signature type f :: DynGraph g => ...
allows you to use features DynGraph
and Graph
type g
. In other words, this is not the problem you are facing. The problem is that the compiler cannot infer that the type gr0
(which is a non-stationary intermediate type) is a member of any of the classes.
Edit. To be more precise, actually using a class function requires either a class constraint or a specific type that is known to be a member of the class. Our functions are f
both f'
monomorphic; all types are specified and GHC should be able to generate actual, executable code. But remember that class functions are defined for each type; where can ghc go to class functions (term "class dictionary") in f
?
Specifying a type like my f'
is one solution. You can also make the function polymorphic itself, in the form of a dependency nesting style. You will need at least ScopedTypeVariables
:
f'' :: Graph g => proxy g -> [Shape] -> [LNode Shape]
f'' _ shapes = consumeGraph (makeGraph shapes :: g)
Note that the first argument to the function does not actually exist; it's just a mechanism for callers to indicate the type g
. The caller uses Proxy
from Data.Proxy
. There's a bit of discussion Proxy
in this SO question and many more places here and elsewhere.
source to share