1

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))
3
  • 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? Commented Apr 7, 2013 at 15:58
  • The error is exactly what the error message says it is. Commented Apr 7, 2013 at 16:45
  • (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] Commented Apr 7, 2013 at 17:58

1 Answer 1

4

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.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.