Haskell can't match type, claims rigid variable

Question

I am new to Haskell, and I am playing around with creating a typeclass for graphs and the nodes in them. Since I want both directed and undirected graphs, I have

data Node = Node { label :: Char
                 , index :: Int
                 } deriving (Ord, Eq)
type Graph edgeType = ([Node], [edgeType])
data Edge = DirectedEdge   {h :: Node, t :: Node}
          | UndirectedEdge {a :: Node, b :: Node}
instance Show Node where
    show n = ['(', label n, ')']
instance Show Edge where
    show (DirectedEdge   h t) = show h ++ "->" ++ show t
    show (UndirectedEdge a b) = show a ++ "-"  ++ show b

So I am distinguishing between directed and undirected edges. A graph must only have edges of either type. I also have the following:

nodes :: [Node]
nodes = zipWith Node ['a'..] [0..]

emptyGraph :: [Node] -> Graph edgeType
emptyGraph ns = (ns, [])

So far so good, however I am writing a function connect, with connects a node to an existing graph. Ideally, I only want it to apply to undirected graphs, but that doesn't seem to be an option. Instead, I have something like this:

connect :: Graph edgeType -> Node -> Graph edgeType
connect (ns, es) n = (n:ns, e:es)
    where e = UndirectedEdge n (head ns)

But this gives the following error:

Couldn't match type `edgeType' with `Edge'
  `edgeType' is a rigid type variable bound by
             the type signature for
               connect :: Graph edgeType -> Node -> Graph edgeType

What is the best way to accomplish what I am trying to achieve?

Answer 1

You probably want to have two separate edge types instead of Edge

newtype DirectedEdge = DirectedEdge { h :: Node, t :: Node}
newtype UndirectedEdge = UndirectedEdge { a :: Node, b :: Node}

And you probably want some kind of typeclass that gives you back a (Node, Node) given an arbitrary edge:

class HasNodeEndpoints a where
  endpoints :: a -> (Node, Node)

-- obvious instances for DirectedEdge and UndirectedEdge

Then when you want to talk about arbitrary graphs, you will write functions that work on Graph a, and probably on HasNodeEndpoints a => Graph a. Algorithms that care about the graph kind would work on Graph DirectedEdge and Graph UndirectedEdge for directed and undirected graphs, respectively.

Another natural extension would be labeled directed and undirected edges.

class HasLabeled a where
  type Label a -- associated type synonym
  label :: a -> Label a
  updateLabel :: a -> (Label a -> Label a) -> a

-- now define data types and instances for labeled directed and undirected edges

Answer 2

Because you choose a specific edge type, namely Edge, when you use UndirectedEdge, the result is that your graph is no longer polymorphic in the edge type. It has to have the type:

connect :: Graph Edge -> Node -> Graph Edge
connect (ns, es) n = (n:ns, e:es)
    where e = UndirectedEdge n (head ns)

Since there's noo other type your edges can be, given that clear use of UndirectedEdge.

---

As an aside, I'd use strictness annotations on the nodes, just as a matter of good hygiene:

data Node = Node { label :: !Char
                 , index :: !Int
                 } deriving (Ord, Eq)