haskell - 如何反转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 顶点边 的反转。这将采用 G vertices' edges' 的形式。

很明显vertices' = vertices。

edges' 呢？那么，对于任何值 v，edges' v 必须返回

• “vertices 中所有 w 的列表，使得 edge w 包含 v 作为元素”

您可以使用列表理解将上述英文描述翻译成 Haskell 代码。您可以使用 x `elem` list 来检查 x 是否是 list 的元素。