Haskell反转节点边元组列表时出现多余空列表项如何解决

错误原因定位 #

1. 多余("b", [])项的来源 #

snuH里的分支判断逻辑存在两处核心错误：

• 调用isInSublist时传入的是当前剩余未处理的列表ps，不是完整的原始输入列表。处理到节点b时，剩余列表是[("b",["c"]),("c",["a","d"]),("e",["d"])]，此时检查b是否在这些列表的子项中，会漏掉前面已经处理完的节点a的出边["b"]，导致误判b没有入边。
• 你在遍历每个节点的过程中就判断是否要追加空列表，逻辑本身不合理：是否需要追加空列表，应该基于整个图的所有边判断，只有完全没有入边的节点才需要对应空列表，不应该在遍历中途判断。

2. 重复元组合并的潜在问题 #

你写的combine函数只能合并相邻的重复元组，如果重复项不相邻就会合并不了，当前示例中d的两项刚好相邻所以合并成功，换其他输入就可能出问题。

修复方案 #

优化思路 #

1. 第一步遍历所有原始边，生成所有反转的边条目
2. 收集图中所有出现过的节点
3. 合并相同节点的入边列表
4. 补充没有入边的节点对应的空列表项

修复后代码 #

import Data.List (lookup, nub)

-- 收集所有反转边
reverseEdges :: Eq t => [(t, [t])] -> [(t, t)]
reverseEdges graph = concat [ [(y, x) | y <- xs] | (x, xs) <- graph ]

-- 合并同节点的入边
groupInEdges :: Eq t => [(t, t)] -> [(t, [t])]
groupInEdges [] = []
groupInEdges ((y, x):rest) = 
  case lookup y rest of
    Just xs -> (y, x:xs) : groupInEdges (filter (\(k, _) -> k /= y) rest)
    Nothing -> (y, [x]) : groupInEdges rest

-- 收集所有节点
getAllNodes :: Eq t => [(t, [t])] -> [t]
getAllNodes graph = nub $ concat [ x:xs | (x, xs) <- graph ]

snuN :: Eq t => [(t, [t])] -> [(t, [t])]
snuN graph = map (\node -> 
  case lookup node reversedGroups of
    Just edges -> (node, edges)
    Nothing -> (node, [])
  ) allNodes
  where
    reversedEdges = reverseEdges graph
    reversedGroups = groupInEdges reversedEdges
    allNodes = getAllNodes graph

运行效果 #

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

完全符合预期输出。

内容的提问来源于stack exchange，提问作者Mampenda