Haskell NB: ‘Edge’ is a non-injective type family

Question

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 Data.Map. I am trying to write Dijkstra's algorithm, but I am running into some trouble with type families. I have the following typeclass and concrete implementation:

{-# LANGUAGE TypeFamilies, AllowAmbiguousTypes, ScopedTypeVariables, TypeFamilyDependencies #-}

class Graph g where
  type Node g
  type Edge g
  nodeSet :: g -> S.Set (Node g)
  neighbours :: g -> (Node g) -> 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) => 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)

To represent the Infinity value of unvisited nodes in Dijkstra's algorithm I have created a sum data type:

data MaxBoundedNum a = Inf | Num a deriving Show

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:

go :: (Graph g) =>
  g -> (Node g) -> (Node g) ->
  S.Set (Node g) ->
  M.Map (Node g) (MaxBoundedNum (Edge g)) ->
  Maybe (M.Map (Node g) (MaxBoundedNum (Edge g)))
go graph curr dest uset vals = do
  currNeighbours <- neighbours graph curr
  undefined

This appears to work correctly for a graph g where graph :: MapGraph Int String

go graph
  :: [Char]
     -> [Char]
     -> S.Set [Char]
     -> M.Map [Char] (MaxBoundedNum Int)
     -> Maybe (M.Map [Char] (MaxBoundedNum Int))

The next part of my go function needs to lookup the current distance from the vals map.

currDist <- M.lookup curr vals

This works outside the go function if I do the following:

currDist = M.lookup current vals

*Main> :t currDist
currDist :: Maybe (MaxBoundedNum Integer)

However, inside the do block I get this error:

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 =>
                         g
                         -> Node g
                         -> Node g
                         -> S.Set (Node g)
                         -> M.Map (Node g) (MaxBoundedNum (Edge g))
                         -> Maybe (M.Map (Node g) (MaxBoundedNum (Edge g)))
        at WithClass.hs:(96,1)-(100,49)
    • In a stmt of a 'do' block: currDist <- M.lookup curr vals

The part Could not deduce made me think I need to give it a type annotation, so I did that:

currDist <- M.lookup curr vals :: Maybe (MaxBoundedNum (Edge g))

But that gives me this error:

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 <- M.lookup curr vals :: Maybe (MaxBoundedNum (Edge g))
      In the expression:
        do currDist <- M.lookup curr vals :: Maybe (MaxBoundedNum (Edge g))
           currNeighbours <- neighbours graph curr
           undefined
      In an equation for ‘go’:
          go graph curr dest uset vals
            = do currDist <- M.lookup curr vals ::
                               Maybe (MaxBoundedNum (Edge g))
                 currNeighbours <- 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
              -> Node g
              -> Node g
              -> S.Set (Node g)
              -> M.Map (Node g) (MaxBoundedNum (Edge g))
              -> Maybe (M.Map (Node g) (MaxBoundedNum (Edge g)))
          (bound at WithClass.hs:101:1)

I had a look at this question but the accepted answer just said to add the TypeFamilyDependencies 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.

Answer 1

Operations on Set (Node g) and Map (Node g) require you to be able to compare nodes. This is what the Ord (Node g) constraint represents. The type you gave for go says it works for any definition of Node g, even those that can't be compared. The error tells you that when you use M.lookup, that needs an Ord (Node g) constraint, but there is no way to satisfy it.

You can satisfy that constraint by adding it to the signature of go:

{-# LANGUAGE FlexibleConstraints #-}  -- Also enable this extension

go :: (Graph g, Ord (Node g)) => ...