Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell can't match type, claims rigid variable

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?

like image 235
Jordan Kay Avatar asked Jun 07 '11 02:06

Jordan Kay


2 Answers

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
like image 127
Lambdageek Avatar answered Sep 24 '22 17:09

Lambdageek


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)
like image 28
Don Stewart Avatar answered Sep 22 '22 17:09

Don Stewart