Редактирование чисто функционального графа

Question

Допустим, есть график и некоторый набор функций, таких как:

create-node :: Graph -> (Graph, Node)
split-node :: Graph -> Node -> (Graph, Node, Node)

Я хотел бы создать версии тех функций, которые не ожидают Graph в качестве аргумента, в основном для удобства (желательно без монад, поэтому мне не нужно было бы оборачивать каждый фрагмент кода, манипулирующий графом, в блок монады) , Ну и что с этим:

create-node :: (Graph -> (Graph, Node))
split-node :: (Graph -> Node) -> ((Graph -> Node), (Graph -> Node))

Или, в более общем смысле:

fun :: (Graph -> Argument) -> ... -> (Graph -> Result)

Тогда я смог бы использовать значения (Graph -> ...), как если бы они были нормальными узлами. В конце, чтобы получить реальный график из значения (Graph -> ...), просто примените его к пустому графику. Это разумный подход?

Answer 1

Хорошо, поэтому

create-node :: (Graph -> (Graph, Node))

- это монада состояния, только без причудливого нового типа (и перевернутого возвращаемого значения).Так что я не вижу преимущества от использования State здесь.После всего этого, я могу написать довольно чистый код, используя состояние Monad:

 reverseEdgesM :: State Graph ()
 reverseEdgesM = do --...

Затем выкрикивать его всякий раз, когда у меня есть чистый код для запуска с использованием runState и друзей:

 reverseEdges :: Graph -> Graph
 reverseEdges = execState reverseEdgesM

Если вы действительно хотите продвинуться в своей идее функций, вы можете просмотреть списки различий , чтобы увидеть, как это делается с простыми списками.

Кроме того, если вы 'Только что у вас есть несколько алгоритмов для реализации, вы, возможно, захотите взглянуть на существующие библиотеки структур данных функциональных графов (например, fgl ), а не накатывать свои собственные.Если вы хотите понять теорию, посмотрите статью Эрвига об индуктивных графах .