如何反转haskell中的图形？

Question

对于练习我需要反转图形(反转所有边缘),但我没有得到任何结果.所以我需要一些帮助.

我知道你可能不想为我解决这个问题,所以这不是我要求的.我只需要一些建议......

所以要达到它:

data Graph a = G
  { nodes :: [a]
  , successors :: a -> [a] }

reverseGraph :: Eq a => Graph a -> Graph a

图表必须包含以下参数:节点列表和定义后继者的函数.此函数具有以下类型: a -> [a]

例如:

graph1 :: Graph Int
graph1 = G [1..6] $ \case   1 -> [2,3]
                            2 -> []
                            3 -> [1,4,6]
                            4 -> [1]
                            5 -> [3,5]
                            6 -> [2,4,5]

反转图表将是:

reverseGraph graph1 ~>
    2 -> [1,6]
    3 -> [1,5]
    1 -> [3,4]
    4 -> [3,6]
    6 -> [3]
    5 -> [5,6]

我得到我需要在输入图形的接班人来检查每个节点,并添加每个输入节点到输出节点的新的继任者名单.

但我只是不知道如何在Haskell中做到这一点.

任何帮助表示赞赏!

---

以下是我可以尝试类似事物的人的解决方案:

reverseGraph :: Eq a => Graph a -> Graph a
reverseGraph (G nodes sucs) =  (G nodes sucs') where 
    sucs' a = getVert a nodes sucs

--Makes a list of all occurrences of v in the succeccor list.
getVert :: Eq a => a -> [a] -> (a-> [a]) -> [a]
getVert v [] succs = []
getVert v (n:ns) succs = if v `elem` succs n then [n]++getVert v ns succs else getVert v ns succs

Answer 1

这是一个提示.让我们考虑相反的情况G vertices edges.这将是形式G vertices' edges'.

很明显vertices' = vertices.

怎么样edges'？好吧,对于任何价值v,edges' v必须返回

• "所有的清单w中vertices,使得edge w包含v作为元素"

您可以使用列表推导将上述英语描述翻译成Haskell代码.您可以x `elem` list用来检查是否x是元素list.