Data type for a simple, undirected graph without multiple edges or loops in Haskell-CodePudding

I am new to Haskell and I am trying to come up with a suitable way to represent a graph. First some background for an undirected simple graph. For all vertices u and v, an edge between u and v is the same as an edge between v and u, there is at most one edge between u and v, and there is no edge between u and u.

Later on I want to be able to write functions to check if the graph is 1) empty, 2) add new vertices, 3) add new edges, 4) obtain all neighbors to a vertex and 5) obtain a list of all vertices in a graph.

After doing research, I am a bit confused by all the ways to define a graph data type, which I also hope to get some help to clarify. All seem to agree that a you need some way to represent a Vertex/Node and the edges/links to other Vertices/Nodes. However, the implementations differ.

Before I have done a Tree with infinite amount of branches, following this question

What I came up with first was defining a data type using recursive data structures with a type variable where each Vertex/Node has a list with its associated nodes:

data Node a = Node a [a] 
    deriving Show
data Graph a = Graph [Node a] 
    deriving Show

However, what I am a bit unsure about is whether this representation makes it possible to insert new edges later on. With this definition a graph is just a list of nodes that in turn contains list of nodes they link/edge to.

After doing research about how to represent a graph in Haskell I found some interesting ideas. The first was to define a graph just using type synonyms:

type Node = Int
type Element = String
type Edge = (Node, Node)
type Node = (Node, Element)
type Graph = ([Node], [Edge])

Here we have that a Graph is a list of nodes with an associated list of its connections/links/edges. However, I was not sure what the corresponding data type definition would look like and with a type variable/parameter instead of a concrete type. In this regard, I found this question declare-data-constructor-for-graphs suggesting to represent a graph like this:

type Vertex = Integer
data Graph = Graph [Vertex] [(Vertex, Vertex)]

Which I guess with type parameter instead could be translated to:

data Graph a = Graph [a] [(a, a)]

Is this correct? Would this solution work for creating a simple, undirected graph without multiple edges or loops in Haskell? That also support the creation of the specified functions above.

In continuation, similar to this representation, I found this question directed-acyclic-graph where a graph is defined as:

data Graph a = Graph [(a,[a])] -- Graph is a list of origins paired with edgeends

Here I guess the author defines a graph as a list of tuples where each tuple consists of one node and a list of its linked nodes.

Another way I found was to use record syntax in the question graph-data-type-representation.

data Node a = Node { value :: a
                   , neighbors :: [Node a]
                   } deriving (Show)
-- or simply, 
data Node a = Node a [Node a] 
  deriving (Show)

Which I guess is the same reasoning. A Node/Vertex has a value, and neighbors that a just a list of other Vertices. Building on top of this, a graph definition would be:

data Graph a = Graph [Node a]

Or am I wrong? If so, this implementation is similar to what my initial thinking, but differs in the data Node definition. Not sure whats more correct here.

In summary, I have found many ways to represent a graph data type in Haskell. But I am a bit confused about which way that best suits my use-case, to create a simple, undirected graph without multiple edges or loops that also supports the functions I would like to implement.

Looking forward answers and comments to clarify this!

CodePudding user response：

Ended up using

data Graph a = Graph [(a, [a])] deriving (Show)

Since Algebraic data types are just a way to represent data, it is mostly about choosing a design that fits your needs. Here is a good source to read more about it: Learn you a haskell

For example, choosing this data type representation makes adding vertices to a graph possible in this way.

addVertex :: Eq a => Graph a -> a -> Graph a
addVertex (Graph vList) v
  | not (containsVertex v vList) = Graph (vList    makeVertex v)
  | otherwise = Graph vList

makeVertex :: a -> [(a, [a])]
makeVertex x = [(x, [])]

containsVertex :: Eq a => a -> [(a, [a])] -> Bool
containsVertex _ [] = False
containsVertex x ((v, _) : ys) = x == v || containsVertex x ys

Thus, just easy to deal with and manage the Graph when expressed in this way.