[Haskell-cafe] Possible FGL bug

[Ivan Lazar Miljenovic]

When developing my QuickCheck-2 test-suite for graphviz, I wrote the
following Arbitrary instance for FGL graphs (which needs
FlexibleInstances):

,----
| instance (Graph g, Arbitrary n, Arbitrary e, Show n, Show e) => Arbitrary (g n e) where
|   arbitrary = do ns <- liftM nub arbitrary
|                  let nGen = elements ns
|                  lns <- mapM makeLNode ns
|                  trace ("Nodes: " ++ show lns) (return ())
|                  les <- listOf $ makeLEdge nGen
|                  trace ("Edges: " ++ show les) (return ())
|                  return $ mkGraph lns les
|     where
|       makeLNode n = liftM ((,) n) arbitrary
|       makeLEdge nGen = liftM3 (,,) nGen nGen arbitrary
| 
|   shrink gr = map (flip delNode gr) (nodes gr)
`----

However, when I try to run this, I occasionally get irrefutable pattern
match failures as follows:

,----
| *Data.GraphViz.Testing.Instances.FGL Data.Graph.Inductive.Tree> sample (arbitrary :: Gen (Gr Int Char))
| 
| 
| 0:0->[]
| 
| 0:-2->[]
| 1:0->[('\a',0)]
| 2:0->[]
| 
| -4:-3->[('U',-3),('#',1)]
| -3:3->[]
| 1:-1->[('}',-3)]
| 
| -8:8->[]
| -3:2->[]
| -1:-5->[('\US',-3),('&',0)]
| 0:5->[('F',-1),('p',4)]
| 4:-1->[]
| 
| -2:8->[('\177',-2),('(',-2),('d',-2),('4',-2),('D',-2),('\US',-2),('d',-2),('u',-2)]
| 
| -16:11->[]
| -2:-2->[]
| 0:11->[('@',1)]
| 1:13->[('u',11)]
| 9:-11->[('\231',11)]
| 11:12->[('\226',1)]
| 16:15->[]
| 
| -10:2->[]
| -4:8->[]
| 1:30->[]
| 26:26->[('<',1),('K',-4)]
| 31:-21->[]
| 
| -35:51->[('@',-29)]
| -29:21->[('\132',-11)]
| -11:-31->[('j',61)]
| -4:40->[('a',-29)]
| 0:6->[('z',-35),('9',28),('\170',-11),('\SUB',28)]
| 23:8->[('P',-29),('(',61),('\\',28)]
| 28:60->[]
| 61:44->[('q',61)]
| *** Exception: Data/Graph/Inductive/Graph.hs:250:26-59: Irrefutable pattern failed for pattern (Data.Maybe.Just (pr, _, la, su), g')
`----

The actual error comes from the definition of insEdge:

,----
| -- | Insert a 'LEdge' into the 'Graph'.
| insEdge :: DynGraph gr => LEdge b -> gr a b -> gr a b
| insEdge (v,w,l) g = (pr,v,la,(l,w):su) & g'
|                     where (Just (pr,_,la,su),g') = match v g
`----

with the Graph instance for Tree-based graphs using this for its mkGraph
method:

,----
|   mkGraph vs es   = (insEdges' . insNodes vs) empty
|         where
|           insEdges' g = foldl' (flip insEdge) g es
`----

So, is this really a bug in FGL, or am I using mkGraph wrong?

On another note, why doesn't the PatriciaTree graph type have a Show
instance? :(

-- 
Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com
IvanMiljenovic.wordpress.com