CODEWITHSUNDEEP
haskellgraphpolymorphismtypeclass
Mortimer McMire
Mortimer McMire

Reputation: 330

Using a typeclass to access fields of similar data types in Haskell

I am in the process of working on some graph problems in Haskell. In the middle of my work, I decided that I wanted to be able to represent edge colors within a graph data type. So I started with edges: Edges could be either colored or uncolored. Here's a quick mock-up of what I was thinking about. Keep in mind, I'm aware that there are terrible flaws in this code.

data BasicEdge v w = BasicEdge { b_endpoints :: (v,v), b_weight :: w}
data ColoredEdge v w c = ColoredEdge { c_endpoints :: (v,v), c_weight :: w, color :: c}

class Edge e where
    endpoints :: e -> (v,v)
    weight :: e -> w

instance Edge (BasicEdge v w) where
    endpoints = b_endpoints
    weight = b_weight

instance Edge (ColoredEdge v w c) where
    endpoints = c_endpoints
    weight = c_weight

Problem 1: v and w in BasicEdge are different type variables than v and w in ColoredEdge. Thus, attempting to access them in a polymorphic manner is preposterous.

Problem 2: return values in the Edge class definition are free type variables, so they cannot be matched with the return values of b_endpoints and c_endpoints, etc.

I do need the type variables - Vertices could be characters, strings, integers, etc.. Edge weights could be any sort of number (Floats are helpful for some problems). Colors could even be a constructed data type.

Is there an "idiomatic" way to do this in the language? It seems that this is a basic type of polymorphism, but I am struggling to understand how to implement it.

Thanks in advance for your help, and please understand that I have spent the past day trying to search on the internet for guidance. It is difficult to structure a search query for this problem.

Upvotes: 4

Views: 321

Answers (1)

shang
shang

Reputation: 24832

Your type class can be fixed by including the type parameters v and w in the class definition.

class Edge e where
    endpoints :: e v w -> (v,v)
    weight :: e v w -> w

Now e has the kind * -> * -> * meaning that it needs to be a type that takes two additional type parameters and these parameters are then used in endpoints and weight to actually link the result type to the type of the edge.

However, you need to tweak your ColoredEdge type a bit so that v and w are the last two parameters, so

data BasicEdge v w = BasicEdge { b_endpoints :: (v,v), b_weight :: w}
data ColoredEdge c v w = ColoredEdge { c_endpoints :: (v,v), c_weight :: w, color :: c}

Now you can define the instances as

instance Edge BasicEdge where
    endpoints = b_endpoints
    weight = b_weight

instance Edge (ColoredEdge c) where
    endpoints = c_endpoints
    weight = c_weight

Another option is to use the TypeFamilies language extension and make the vertex and weight types associated type synonyms in the Edge class. That way the order to type parameters in the instance types becomes irrelevant.

{-# LANGUAGE TypeFamilies #-}

class Edge e where
    type Vertex e
    type Weight e

    endpoints :: e -> (Vertex e, Vertex e)
    weight :: e -> Weight e

instance Edge (BasicEdge v w) where
    type Vertex (BasicEdge v w) = v
    type Weight (BasicEdge v w) = w

    endpoints = b_endpoints
    weight = b_weight

instance Edge (ColoredEdge v w c) where
    type Vertex (ColoredEdge v w c) = v
    type Weight (ColoredEdge v w c) = w

    endpoints = c_endpoints
    weight = c_weight

However, usually type classes are not the best solution for this kind of polymorphism. I would simply include an extra parameter in your Edge type for any additional data, as in

data Edge v w d = Edge { endpoints :: (v,v), weight :: w, edgeData :: d }

Now you can put color in d or a record that contains multiple fields of data for an edge and still query the shape of the graph in a generic way.

Your original edge types could now be represented with the type synonyms

type BasicEdge   v w   = Edge v w ()
type ColoredEdge v w c = Edge v w c

Upvotes: 6

Related Questions