Как поменять график в 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.