How do I create a Haskell class instance including a predefined type?

Question

I am trying to create a Haskell class instance that includes a predefined type, but I keep getting this error: " Illegal instance declaration for Graph (AdjListGraph a)' (All instance types must be of the form (T t1 ... tn) where T is not a synonym. Use -XTypeSynonymInstances if you want to disable this.) In the instance declaration forGraph (AdjListGraph a)' "

Can somebody help me with this problem? Here is the code:

type Node = Int

type Arc = (Node, Node) 

containsArc :: Node -> Node -> [Arc] ->Bool
containsArc a b [] = False
containsArc a b (x:xs)
    | (fst x == a && snd x == b) = True
    | otherwise = containsArc a b xs

fstNode :: [Arc] -> Node -> [Node]
fstNode arcs n
    | (n == (fst (head arcs))) = (snd (head arcs)) : (fstNode (tail arcs) n)
    | otherwise = fstNode (tail arcs) n

sndNode :: [Arc] -> Node -> [Node]
sndNode arcs n
    | (n == (snd(head arcs))) = (fst (head arcs)) : (sndNode (tail arcs) n)
    | otherwise = sndNode (tail arcs) n 

class Graph g where

    build :: [Node] -> [Arc] -> g

    nodes :: g -> [Node] -- lista nodurilor din graf

    arcs :: g -> [Arc] -- lista muchiilor din graf

    nodeOut :: g -> Node -> [Node]

    nodeIn :: g -> Node -> [Node]

    arcExists :: g -> Node -> Node -> Bool

    arcExists g a b
        | (arcs g) == [] = False
        | otherwise = if (fst (head (arcs g)) == a && snd (head (arcs g)) == b) then True else containsArc a b (tail (arcs g))

    nodeIn g n = sndNode (arcs g) n
    nodeOut g n = fstNode (arcs g) n


type AdjListGraph a = [(a, [a])]

makePairs :: Node -> [Node] -> [(Node, Node)]
makePairs a [] = []
makePairs a (x:xs) = (a, x) : makePairs a xs

instance Graph a => Graph (AdjListGraph a) --this is where i get the error-- where
    arcs a 
        | a == [] = []
        | otherwise = (makePairs (fst (head a)) (snd (head a))) ++ (arcs (tail a))

    nodes a
        | a == [] = []
        | otherwise = (fst (head a)) : (nodes (tail a))

Well... have you tried GHC's suggested fix? As a side note, why are you demanding Graph a in the head of your instance declaration? — Daniel Wagner
(makePairs (fst (head a)) (snd (head a))) is also wrong. The type of a is AdjListGraph a, namely [(a, [a])]. It contradicts makePairs :: Node -> [Node] -> [(Node, Node)]. If you make makePairs generic, e.g. removing its type annotation, (makePairs (fst (head a)) (snd (head a))) ++ (arcs (tail a)) will contradict arcs :: g -> [Arc] — nymk

Gabriella Gonzalez Gabriella Gonzalez · Accepted Answer · 2013-04-07T16:46:05

Use a newtype for AdjListGraph instead of a type synonym. You can use the TypeSynonymInstances extension like it asks, but that causes problems with type inference because type synonyms don't "stick" and when they expand out they won't necessarily have the right form necessary to select the correct type class instance. Using a newtype will help you avoid a lot of headaches down the road, even if it does require wrapping and unwrapping.

The reason is that ghc resolves which type class instance by matching on the principal type of something. Your AdjacencyListGraph's principal type is actually a [(a, [a])], and the type synonym just creates an alias for that but does not change its principal type. A newtype actually changes the principal type, which is why it plays nicely with type classes. However, it requires that you specifically wrap and unwrap values so that ghc always knows which principal type to match on at all times.

How do I create a Haskell class instance including a predefined type?

1 Answers