I am trying to build my own simple graph library that I can use for advent of code. I have a type class Graph and one concrete implementation MapGraph that uses Data.Map
class Graph g where
nodeSet :: (Ord n) => g -> S.Set n
data MapGraph e n = MapGraph {mGraph :: M.Map n [(e,n)]} deriving Show
instance (Ord e,Ord n) => Graph (MapGraph e n) where
nodeSet mapGraph = S.fromList $ M.keys $ mGraph mapGraph
The nodeSet function works correctly if I have it as a standalone function outside of the instance declaration
testNodeSet mapGraph = S.fromList $ M.keys $ mGraph mapGraph
*Main> testNodeSet $ mapGraphFromEdgeList $ parseEdgeList connectionList
fromList ["B","C","D","E","F","G","H","I","J","K","L","S"]
But I get a compile error from it inside of the instance
Main.hs:59:22: error:
• Couldn't match type ‘n1’ with ‘n’
‘n1’ is a rigid type variable bound by
the type signature for:
nodeSet :: forall n1. Ord n1 => MapGraph e n -> S.Set n1
at Main.hs:59:3-9
‘n’ is a rigid type variable bound by
the instance declaration
at Main.hs:58:10-46
Expected type: S.Set n1
Actual type: S.Set n
• In the expression: S.fromList $ M.keys $ mGraph mapGraph
In an equation for ‘nodeSet’:
nodeSet mapGraph = S.fromList $ M.keys $ mGraph mapGraph
In the instance declaration for ‘Graph (MapGraph e n)’
• Relevant bindings include
mapGraph :: MapGraph e n (bound at Main.hs:59:11)
nodeSet :: MapGraph e n -> S.Set n1 (bound at Main.hs:59:3)
|
59 | nodeSet mapGraph = S.fromList $ M.keys $ mGraph mapGraph
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
I have no idea what the error message is trying to tell me except that I have something wrong with type signatures. The type of tetsNodeSet looks correct to me
testNodeSet :: Ord a => MapGraph e a -> S.Set a
What do I need to do to fix my issue? I did wonder if I need to add (Ord e,Ord n) => to my declaration of the data type MapGraph but I couldn't work out how to put it there without getting a compile error
The class is making a very strong promise, which is hard to keep later on:
class Graph g where
nodeSet :: (Ord n) => g -> S.Set n
This is promising that, from any Graph type g, we can build a set of n, for any ordered type n.
That is, if we have instance Graph G where ... then from G we must be able to construct a nodeSet of type S.Set Bool, another of type S.Set String, and so on for S.Set Int, S.Set [Bool], etc.
Likely, this is not what you want. You don't want to promise "from a graph you can get a set of any type", but something like "from a graph you can get a set of nodes of a fixed type which depends on the graph type".
This dependency can be expressed in Haskell in many ways, e.g. using type families
class Graph g where
type Node g
nodeSet :: g -> S.Set (Node g) -- no need for Ord right now
Here we declare a type family Node g which depends on g. Then we can write
instance (Ord e,Ord n) => Graph (MapGraph e n) where
type Node (MapGraph e n) = n
nodeSet mapGraph = S.fromList $ M.keys $ mGraph mapGraph
to define the type of nodes specific to the instance at hand.
You will need to enable a bunch of Haskell extensions to make this work, but hopefully the idea is clear.
Here's how to read the compiler's error:
• Couldn't match type ‘n1’ with ‘n’
A type n1 should have been equal to n, but it was not. Here's where these two type come from:
‘n1’ is a rigid type variable bound by
the type signature for:
nodeSet :: forall n1. Ord n1 => MapGraph e n -> S.Set n1
n1 is the type which is mentioned in the class (the one called n in your code)
‘n’ is a rigid type variable bound by
the instance declaration
n is the type mentioned din the instance (which bares no relation to n1).
Expected type: S.Set n1
Actual type: S.Set n
The class promised S.Set n1, but your code returned a S.Set n. To make these two types equal, we would need n1 and n equal, but there is no guarantee that they are such.