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

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

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

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

Просто для смеха, вот немного пугающий обратный постпорядковый поиск в глубину вперед, выполненный в стиле продолжения-прохождения на языке 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

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

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

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

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

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

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

В этой книге это подробно рассматривается 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=lpo-top-stripe-1&pf_rd_t=201&pf_rd_i=0262011530&pf_rd_m=ATVPDKIKX0DER&pf_rd_r=114DJE8K5BG75B86E1QS