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.
