[Haskell-cafe] FGL instance constraint

[Kevin Quick]

On Sat, 01 May 2010 15:42:09 -0700, Ivan Lazar Miljenovic <ivan.miljenovic at gmail.com> wrote:

>> instance Graph GrB where
>> -- instance (Cls a) => Graph GrB where -- error: ambiguous constraint, must mention type a
>> -- instance (Cls a) => forall a. Graph GrB where -- error: malformed instance header
>> -- instance (Cls a) Graph GrB | GrB -> a where -- error: parse error on |
>>     -- empty :: (Cls a) => GrB a b -- error: Misplaced type signature (can't redefine the type)
>>     empty = GrB (B []) -- error: could not deduce (Cls a) from context () for B
>>
>>     isEmpty (GrB (B l)) = null l
>>
>>     match _ g = (Nothing, g) -- Actually need Cls methods on 'a' type to generate the non-trivial case
>>
>>     mkGraph n e = GrB (B [])  -- TBD
>>     labNodes g = []  -- TBD
>
> Unless you have something else you haven't put here, I don't see any
> reason why you have to have the constraint on the datatype rather than
> on the actual functions (outside of the class instance) you need them
> for later on.

I was trying to put them on the inside.  Essentially I was trying to use the 'a' portion of the LNode as a type that would provide methods from which I could reconstruct the shape of the Graph.  Or to put it another way, I had a collection of data and I wanted to be able to say "this container of data is also useable as a graph" by using class operations on the data.

I've discovered an alternative, workable approach to the issue.  After coming to terms that the instance of Graph could impose no restrictions on the node (or edge) labels and that they were (as you previously mentioned) simply "decorators" for the node, I determined that I could achieve my goal by writing a converter from "Cls" -> "a Graph instance for a" and I simply used Data.Graph.Inductive.Tree as the "a Graph instance" portion.

import Data.Graph.Inductive.Tree

clsToGraph :: (Cls a) => B a -> Gr a ()
clsToGraph b = mkGraph (nodes b) (edges b)
   where nodes x = ...
         edges x = ...

The downside of this, to my procedurally-trained brain is that (1) I've now duplicated each 'a' in two different datastructures, and (2) I've had to pay--albeit lazily--for the conversion from B to the tree container represented by Gr.  The nascent functionaly-trained portion of my brain would like to think that GHC (or other) is smart enough to not create duplicate copies... I'm not sure that's true though.  I think I was probably fooling myself about (2) though: it was always there, just more explicitly now.

It's one of the joys of Haskell: it saves your from your own stupid ideas.  :-)

-- 
-KQ