Describing a typeclass for general graphs in Haskell

Question

I'm trying to write a typeclass for graphs. Basically, the typeclass looks like:

class Graph g where
  adjacentNodes :: g n -> n -> [n]

in which I use n to represent the type of nodes.

Then I have the following Graph defined like this:

data FiniteGraph n = FiniteGraph { runFiniteGraph :: Array n [n] }

where Array is adopted from the standard container Data.Array, the structure is to represent a finite graph in the way to map each node to their adjacent nodes.

Here comes the problem, when I try to make FiniteGraph an instance of Graph.

instance Graph FiniteGraph where
  adjacentNodes g n = (runFiniteGraph g) ! n

Unfortunately this doesn't work, because the ! operator requires the constraint Ix n, but I find no where to declare it.

I expect the instance declaration to be some like:

instance (Ix n) => Graph (FiniteGraph n) where { ... }

But this requires the g in class Graph g to have the kind * instead of * -> *, such that I would have no where to show that n depend on g.

So what can I do with that? Thanks.

Answer 1

It can be done after you add a second param to the Graph class.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}
import Data.Array

class Graph g n | n -> g where
  adjacentNodes :: g n -> n -> [n]

data FiniteGraph n = FiniteGraph { runFiniteGraph :: Array n [n] }

instance Ix n => Graph FiniteGraph n where
  adjacentNodes g n = (runFiniteGraph g) ! n

That makes sense if you think about it: graph requires the notion of a vertex.