Reputation: 11
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 for
Graph (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))
Upvotes: 1
Views: 260
Reputation: 35099
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.
Upvotes: 4