title: Haskell NB: ‘Edge’ is a non-injective type family
body: <p>I am trying to write my own graph library in Haskell for use in the advent of code. I am trying to use a class for graphs and one concrete implementation using <code>Data.Map</code>. I am trying to write Dijkstra's algorithm, but I am running into some trouble with type families. I have the following <code>typeclass</code> and concrete implementation:</p>
  <pre><code>{-# LANGUAGE TypeFamilies, AllowAmbiguousTypes, ScopedTypeVariables, TypeFamilyDependencies #-}
  
  class Graph g where
    type Node g
    type Edge g
    nodeSet :: g -&gt; S.Set (Node g)
    neighbours :: g -&gt; (Node g) -&gt; Maybe [(Edge g, Node g)]
  
  data MapGraph e n = MapGraph {mGraph :: M.Map n [(e,n)]} deriving Show
  instance (Num e,Ord e,Ord n) =&gt; Graph (MapGraph e n) where
    type Node (MapGraph e n) = n
    type Edge (MapGraph e n) = e
    nodeSet mapGraph = S.fromList $ M.keys $ mGraph mapGraph
    neighbours mapGraph node = M.lookup node (mGraph mapGraph)
  </code></pre>
  <p>To represent the <code>Infinity</code> value of unvisited nodes in Dijkstra's algorithm I have created a sum data type:</p>
  <pre><code>data MaxBoundedNum a = Inf | Num a deriving Show
  </code></pre>
  <p>I am trying to work on the recursive function for the algorithm which will take in the graph, the current node, the destination node, the unvisited set, and a map of nodes and their length from the source node. The following skeleton function seems to be what I want:</p>
  <pre><code>go :: (Graph g) =&gt;
    g -&gt; (Node g) -&gt; (Node g) -&gt;
    S.Set (Node g) -&gt;
    M.Map (Node g) (MaxBoundedNum (Edge g)) -&gt;
    Maybe (M.Map (Node g) (MaxBoundedNum (Edge g)))
  go graph curr dest uset vals = do
    currNeighbours &lt;- neighbours graph curr
    undefined
  </code></pre>
  <p>This appears to work correctly for a <code>graph g</code> where <code>graph :: MapGraph Int String</code></p>
  <pre><code>go graph
    :: [Char]
       -&gt; [Char]
       -&gt; S.Set [Char]
       -&gt; M.Map [Char] (MaxBoundedNum Int)
       -&gt; Maybe (M.Map [Char] (MaxBoundedNum Int))
  </code></pre>
  <p>The next part of my <code>go</code> function needs to lookup the current distance from the <code>vals</code> map.</p>
  <pre><code>currDist &lt;- M.lookup curr vals
  </code></pre>
  <p>This works outside the <code>go</code> function if I do the following:</p>
  <pre><code>currDist = M.lookup current vals
  
  *Main&gt; :t currDist
  currDist :: Maybe (MaxBoundedNum Integer)
  </code></pre>
  <p>However, inside the <code>do</code> block I get this error:</p>
  <pre><code>Could not deduce (Ord (Node g)) arising from a use of ‘M.lookup’
        from the context: Graph g
          bound by the type signature for:
                     go :: forall g.
                           Graph g =&gt;
                           g
                           -&gt; Node g
                           -&gt; Node g
                           -&gt; S.Set (Node g)
                           -&gt; M.Map (Node g) (MaxBoundedNum (Edge g))
                           -&gt; Maybe (M.Map (Node g) (MaxBoundedNum (Edge g)))
          at WithClass.hs:(96,1)-(100,49)
      • In a stmt of a 'do' block: currDist &lt;- M.lookup curr vals
  </code></pre>
  <p>The part <code>Could not deduce</code> made me think I need to give it a type annotation, so I did that:</p>
  <pre><code>currDist &lt;- M.lookup curr vals :: Maybe (MaxBoundedNum (Edge g))
  </code></pre>
  <p>But that gives me this error:</p>
  <pre><code>WithClass.hs:102:15: error:
      • Couldn't match type ‘Edge g’ with ‘Edge g1’
        Expected type: Maybe (MaxBoundedNum (Edge g1))
          Actual type: Maybe (MaxBoundedNum (Edge g))
        NB: ‘Edge’ is a non-injective type family
      • In a stmt of a 'do' block:
          currDist &lt;- M.lookup curr vals :: Maybe (MaxBoundedNum (Edge g))
        In the expression:
          do currDist &lt;- M.lookup curr vals :: Maybe (MaxBoundedNum (Edge g))
             currNeighbours &lt;- neighbours graph curr
             undefined
        In an equation for ‘go’:
            go graph curr dest uset vals
              = do currDist &lt;- M.lookup curr vals ::
                                 Maybe (MaxBoundedNum (Edge g))
                   currNeighbours &lt;- neighbours graph curr
                   undefined
      • Relevant bindings include
          vals :: M.Map (Node g) (MaxBoundedNum (Edge g))
            (bound at WithClass.hs:101:25)
          uset :: S.Set (Node g) (bound at WithClass.hs:101:20)
          dest :: Node g (bound at WithClass.hs:101:15)
          curr :: Node g (bound at WithClass.hs:101:10)
          graph :: g (bound at WithClass.hs:101:4)
          go :: g
                -&gt; Node g
                -&gt; Node g
                -&gt; S.Set (Node g)
                -&gt; M.Map (Node g) (MaxBoundedNum (Edge g))
                -&gt; Maybe (M.Map (Node g) (MaxBoundedNum (Edge g)))
            (bound at WithClass.hs:101:1)
  </code></pre>
  <p>I had a look at <a href="https://stackoverflow.com/questions/52547887/non-injective-closed-type-family">this question</a> but the accepted answer just said to add the <code>TypeFamilyDependencies</code> language extension which appears to not do anything for me. What am I doing wrong and how can I fix my code? Thank you in advance.</p>