Reverse list of tuples of nodes and edges (Haskell)-CodePudding

I have a list of nodes and edges, represented as tuples where the first element is a node, and the second element is a list of all nodes it has an edge to. I am trying to reverse the list like so:

ghci> snuN [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
ghci> [("a",["c"]),("b",["a"]),("c",["b"]),("d",["c","e"]),("e",[])]

So far, I've written this code:

snuH :: Eq t => [(t,[t])] -> [(t,[t])]
snuH [] = []
snuH ps@((x, xs):rest) =
    if (length xs <= 1) && not (x `isInSublist` ps)
        then [(y,[x])| y <- xs]    snuH rest    [(x, [])]
    else [(y,[x])| y <- xs]    snuH rest

isInSublist :: Eq t => t -> [(t,[t])] -> Bool
isInSublist _ [] = False
isInSublist x ((y, ys):rest) = (x `elem` ys) || isInSublist x rest

combine :: Eq t => [(t,[t])] -> [(t,[t])]
combine ps@((x, xs):(y, ys):rest) = if x == y then (x, xs  ys):rest else (x, xs):combine((y, ys):rest)

snuN :: Eq t => [(t, [t])] -> [(t, [t])]
snuN ls = combine $ snuH ls

The first function gives me this output:

ghci> snuH [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
ghci> [("b",["a"]),("c",["b"]),("a",["c"]),("d",["c"]),("d",["e"]),("e",[]),("b",[])]

Which is not quite the result I wanted, because it creates two tuples with the same first element (("d",["c"]),("d",["e"])), and it has the extra ("b",[]) as an element when it shouldn't. I wrote the combine helper-function to fix the problem, which gives me this output:

ghci> snuN [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
ghci> [("b",["a"]),("c",["b"]),("a",["c"]),("d",["c","e"]),("e",[]),("b",[])]

Which fixes the problem with the two tuples with the same first element, but I still have the extra ("b",[]) which I can't figure out how to fix, I assume there's something wrong with my snuH but I can't see where the problem is.

Can you tell me what im doing wrong here? I don't understan why I get the extra ("b",[]). All help is appreciated!

CodePudding user response：

I'd argue that the following list comprehension gives you what you need:

type Graph node = [(node, [node])]

converse :: Eq node => Graph node -> Graph node
converse g = [(v, [e | (e, es) <- g, v `elem` es]) | (v, _) <- g]

However, if you try it out, you'll get:

> converse [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
[("a",["c"]),("b",["a"]),("c",["b"]),("e",[])]

Compared to the example you gave, the entry for "d" is missing from the output. That's because the input did not mention an explicit entry ("d", []).

To compensate for this, we could put a bit more logic in retrieving the complete list of nodes from the graph, also accounting for the "implied" ones:

nodes :: Eq node => Graph node -> [node]
nodes g = nub $ concat [v : es | (v, es) <- g]

Note: this requires importing nub from Data.List.

Then, we can write:

converse' :: Eq node => Graph node -> Graph node
converse' g = [(v, [e | (e, es) <- g, v `elem` es]) | v <- nodes g]

And, indeed, we yield:

> converse' [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
[("a",["c"]),("b",["a"]),("c",["b"]),("d",["c","e"]),("e",[])]