Как реализовать графики и графические алгоритмы на языке функционального программирования?

В принципе, я знаю, как создавать структуры данных графа и использовать алгоритм Дейкстры в языках программирования, где допускаются побочные эффекты. Как правило, алгоритмы графа используют структуру для обозначения определенных узлов как "посещенных", но у этого есть побочные эффекты, которых я пытаюсь избежать.

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

Ответ 1

Вы можете проверить, как работает Martin Erwig Haskell функциональная библиотека графиков. Например, его функции кратчайшего пути являются чистыми, и вы можете видеть исходный код для его реализации.

Другим вариантом, как fmark, упомянутым, является использование абстракции, которая позволяет реализовать чистые функции с точки зрения состояния. Он упоминает государственную монаду (которая доступна как в lazy, так и strict). Другой вариант, если вы работаете в компиляторе/интерпретаторе GHC Haskell (или, я думаю, любую реализацию Haskell, которая поддерживает типы ранга 2), другой вариант ST monad, которая позволяет вам писать чистые функции, которые обрабатывают изменяемые переменные внутри.

Ответ 2

Если вы использовали haskell, единственный функциональный язык, с которым я знаком, я бы рекомендовал использовать State monad. Государственная монада является абстракцией для функции, которая принимает состояние и возвращает промежуточное значение и некоторое новое значение состояния. Это считается idiomatic haskell для тех ситуаций, где необходимо поддерживать большое состояние.

Это гораздо более приятная альтернатива наивному "возврату" как результат функции и передает его как параметр "идиома", которая подчеркивается в учебниках по программированию начального функционального программирования. Я полагаю, что большинство функциональных языков программирования имеют аналогичную конструкцию.

Ответ 3

Я просто сохраняю посещенный набор как набор и передаю его как параметр. Имеются эффективные реализации времени в лог-времени множеств любого упорядоченного типа и экстра-эффективных наборов целых чисел.

Чтобы представить граф, я использую списки смежности, или я буду использовать конечную карту, которая отображает каждый node в список его преемников. Это зависит от того, что я хочу делать.

Вместо Абельсона и Суссмана я рекомендую Криса Окасаки Чисто функциональные структуры данных. Я связался с диссертацией Криса, но если у вас есть деньги, он расширил ее в отличную книгу.

Просто для усмешек, здесь немного страшный обратный поиск по глубине после первого порядка, выполненный в стиле продолжения прохождения в Haskell. Это прямо из библиотеки Hoopl:

postorder_dfs_from_except :: forall block e . (NonLocal block, LabelsPtr e)
                          => LabelMap (block C C) -> e -> LabelSet -> [block C C]
postorder_dfs_from_except blocks b visited =
 vchildren (get_children b) (\acc _visited -> acc) [] visited
 where
   vnode :: block C C -> ([block C C] -> LabelSet -> a) 
                      -> ([block C C] -> LabelSet -> a)
   vnode block cont acc visited =
        if setMember id visited then
            cont acc visited
        else
            let cont' acc visited = cont (block:acc) visited in
            vchildren (get_children block) cont' acc (setInsert id     visited)
      where id = entryLabel block
   vchildren bs cont acc visited = next bs acc visited
      where next children acc visited =
                case children of []     -> cont acc visited
                                 (b:bs) -> vnode b (next bs) acc     visited
   get_children block = foldr add_id [] $ targetLabels bloc
   add_id id rst = case lookupFact id blocks of
                      Just b -> b : rst
                      Nothing -> rst

Ответ 4

Мне бы хотелось услышать о какой-то действительно умной технике, но я думаю, что есть два фундаментальных подхода:

Изменить некоторый объект глобального состояния. то есть побочные эффекты
Передайте граф как аргумент вашим функциям, а возвращаемое значение будет измененным графиком. Я предполагаю, что это ваш подход "преодоления большого количества состояний".

Это то, что сделано в функциональном программировании. Если компилятор/интерпретатор хорош, это поможет вам управлять памятью. В частности, вы захотите убедиться, что используете хвостовую рекурсию, если вам приходится выполнять какие-либо функции.

Ответ 5

Вот пример Swift. Вы можете найти это немного более читаемым. На самом деле эти переменные на самом деле носят описательный характер, в отличие от суперкритических примеров Haskell.

https://github.com/gistya/Functional-Swift-Graph

Ответ 6

Большинство функциональных языков поддерживают внутренние функции. Таким образом, вы можете просто создать представление графика в самом внешнем слое и просто ссылаться на него из внутренней функции.

Эта книга подробно описывает его http://www.amazon.com/gp/product/0262510871/ref=pd_lpo_k2_dp_sr_1?ie=UTF8&cloe_id= aa7c71b1-f0f7-4fca-8003-525e801b8d46 & attrMsgId = LPWidget-A1 & pf_rd_p = 486539851 & pf_rd_s = ПОЛ-топ-полоса-1 & pf_rd_t = 201 & pf_rd_i = 0262011530 & pf_rd_m = ATVPDKIKX0DER & pf_rd_r = 114DJE8K5BG75B86E1QS