Couldn't match type error when implementing type class function

Question

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

Answer 1

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.