Haskell FGL using Graph functions on a DynGraph

Question

My goal is to do things with an intersection graph of shapes. 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 compiles and typechecks fine. A simple thing should be to get the nodes of the graph using the labNodes function.

getNodes sh = labNodes (makeIntersectionGraph sh)

Note that the documentation states:

DynGraph: dynamic, extensible graphs. Dynamic graphs inherit all operations from static graphs but also offer operations to extend and change graphs.

and labNodes is a function for the Graph class. So the above should work.

However, I get 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 perfectly fine. The problem I still have is that I don't see why it is necessary to invoke a concrete implementation of a DynGraph when all DynGraphs have access to the same functions.

Christian Conkle Christian Conkle · Accepted Answer · 2014-10-02T20:47:37

You're working with two functions: one that makes a graph, and one that consumes a graph. Let's simplify the types and ignore the DynGraph/Graph distinction for now.

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: To split it out 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 g doesn't appear in the type signature of f. The compiler could conceivably choose any of several types that satisfy the restriction, but that would be arbitrary and it won't do so.

The fact that all Graphs share the same functions doesn't really answer the question. Will the intermediate graph use a Patricia tree or a normal tree? It makes a difference. Imagine if we were talking about a class like Num: we could use Int or Double or Integer or Decimal, each with totally different performance and semantic characteristics.

So there needs to be some indication, somewhere, of which type you want. Your solution works; if you want to maintain the generality of makeIntersectionGraph you can use an internal type annotation, along these lines:

f' :: [Shape] -> [LNode Shape]
f' xs = consumeGraph (makeGraph xs :: G.Gr Shape)

This problem comes up often. I think of it as the "show . read" problem; that's a similar situation. What type do we use in the middle? The Haskell '98 report has a section on "ambiguous types", which also explains why this problem is masked by the default rules when you try to do this with Num functions.

(Note that in GHCi the type defaulting rules are changed from those specified in the '98 Report, which is why in GHCi show . read doesn't give a type error.)

Oh, I almost forgot about DynGraph/Graph. If you look at Haddock or the source, you'll see that DynGraph is defined as class Graph gr => DynGraph gr where .... As a result, every DynGraph is also a Graph; the type signature f :: DynGraph g => ... allows you to use both DynGraph and Graph functions on the type g. In other words, that's not the problem you're encountering. The problem is that the compiler can't infer that the type gr0 (which is the unstated intermediate type) is a member of either class.

Edit: To be more precise, actually using a class function requires either a class constraint or a specific type known to be a member of the class. Our functions f and f' are monomorphic; all the types are specified, and GHC should be able to generate actual, runnable code. But remember that class functions are defined per type; where can GHC go to get the class functions (the term here is "class dictionary") in f?

Specifying the type, like my f', is one solution. You can also make the function itself polymorphic, in a kind of dependency-injection style. You'll need at least ScopedTypeVariables:

f'' :: Graph g => proxy g -> [Shape] -> [LNode Shape]
f'' _ shapes = consumeGraph (makeGraph shapes :: g)

Notice that the first argument to the function doesn't need to actually exist; it's just a mechanism for callers to specify the type of g. A caller would use Proxy from Data.Proxy. There's a little discussion of Proxy in this SO question and many other places here and elsewhere.

Haskell FGL using Graph functions on a DynGraph

1 Answers