Return graph modified by two insertions in Haskell-CodePudding

I am trying to add an edge to a graph in Haskell where the graph data type is defined as:

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

Effectively, my data type is defined as: A Graph is a list of nodes stored as tuples, where the first element is the node value and the second element is a list of its edges (i.e., which other nodes it is connected to).

When inserting an edge between two nodes (u,v), you first have to check that both nodes exist and that the edge does not already exist. That is, that (u, [a,b...n]) and (v,[a,b...n]) their respective lists of edges does not contain u or v. Thus, I have two functions that performs this check. If this check passes and due to that my data type is defined as above mentioned, I must insert u and v in respective node's lists. After this, I must return a new Graph.

addEdge :: Eq a => Graph a -> (a, a) -> Graph a
addEdge g (u, v)
  | (existsNode u g) && (existsNode v g) && (not (existsEdge (u, v) g)) = undefined
  | otherwise = g

-- Check if an edge between two nodes exists
existsEdge :: Eq a => (a, a) -> Graph a -> Bool
existsEdge (u, v) g = elem u (getEdges (u, v) g) && elem v (getEdges (u, v) g)

getEdges :: Eq a => (a, a) -> Graph a -> [a]
getEdges (u, v) g =
  let rightNeighbours = getNodeNeighbours (getNode u g)
      leftNeihbours = getNodeNeighbours (getNode v g)
   in rightNeighbours    leftNeihbours

-- Get a node given its node id
getNode :: Eq a => a -> Graph a -> (a, [a])
getNode y (Graph []) = (y, [])
getNode y (Graph (x : xs))
  | y == fst x = x 
  | otherwise = getNode y (Graph xs)

I need a way to fill the part where undefined is now with something that takes each node u and v, and appends v to u's neighbors list (u,[v]) and vice versa (v, [u]), that results in returning a Graph.

For example, if we have that:

g = (Graph [(1,[2]),(2,[1]), (3,[2])])

And we want to add an edge between nodes 3 and 1. We first see that both nodes exist, and that an edge does not already exist -->

g = (Graph [(1,[2,3]),(2,[1]), (3,[2,1])])

Is there a way to do this in Haskell?

CodePudding user response：

This is a nice example for a common rule of thumb:

Avoid boolean checks and then conditionally doing something. Instead write functions that attempt doing something, and fail if it's not possible.

Your task can be broken down to:

Pick out both of the nodes between which you want the edge (if they exist). You should do this in a way that allows also tweaking them, not just reading out.
Modify the edges-list of one of the nodes, inserting the new edge (if it doesn't exist).

The failure cases should be associated with a Maybe type: if an operation isn't possible, it's typically a bad idea to have it silently fail, instead you should make it clear that the update wasn't applied and then leave it to the caller to ignore it or do something else.

addEdge :: Eq a => Graph a -> (a, a) -> Maybe (Graph a)

Now, what do I mean by “do this in a way that allows also tweaking [the nodes]”? It means that you should return a view into the old version, as well as a function that, given a modified value of the node, reconstructs the corresponding modified version of the entire graph. Specifically, you want to modify the outgoing edges. (Modifying the node's key would require also updating all other nodes that may point to it; we don't need that.)

getNode :: Eq a => a -> Graph a -> Maybe ((a, [a]), [a] -> Graph a)

This signature looks a bit daunting; let's introduce some type synonyms to make it easier:

type Node a = (a, [a])
type NodeView a = (Node a, [a] -> Graph a)

getNode :: Eq a => a -> Graph a -> Maybe (NodeView a)

The main change in implementation is that you need to “remember” the nodes in the list that were skipped because they didn't match. I would do this with an auxiliary function

getNode' :: Eq a => a -> Graph a
     -> [Node a]  -- ^ The nodes that need to be prepended in the reconstructed graph
     -> Maybe (NodeView a)

getNode' _ _ (Graph []) = Nothing  -- Node was not found
getNode' y prep (Graph ((x,es):ns))
  | x==y        -- Node was found, now create a view to it:
               = Just ( (x,es)
                      , \es' -> Graph $ prep    (x,es') : xs )
  | otherwise   -- Not found yet, but maybe later. Add currently tried node to the prep-list.
               = getNode' y ((x,es):prep) (Graph ns)

Obs: the above makes a change to the reconstructed graph that may or may not matter for you. Can you spot what it is?

In practice, you shouldn't use getNode' directly, but always call it with empty prep list. In fact you should probably make it a local “loop body” function:

getNode :: Eq a => a -> Graph a -> Maybe (NodeView a)
getNode y = go y []
 where go _ _ (Graph []) = Nothing
       go y prep (Graph ((x,es):ns)) = ...

For the rest of the task, you can use the NodeView given by this function as a helper to create the whole updated graph.