Я просто сохраняю посещенный набор как набор и передаю его в качестве параметра. Существуют эффективные реализации во время журнала наборов любого упорядоченного типа и сверхэффективные наборы целых чисел.
Для представления графа я использую списки смежности, или я буду использовать конечную карту, которая отображает каждый узел в список его наследников. Это зависит от того, что я хочу сделать.
Вместо Абелсона и Суссмана я рекомендую чисто функциональных структур данных Криса Окасаки . Я связался с диссертацией Криса, но если у вас есть деньги, он расширил их до превосходной книги .
Только ради ухмылки, вот немного пугающий обратный поиск в глубину в обратном порядке, выполненный в стиле продолжения в 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