ja po prostu zachować odwiedzanym ustawiony jako zestaw i przekazać ją jako parametr. Istnieją wydajne implementacje log-time zestawów dowolnego uporządkowanego typu i bardzo wydajnych zestawów liczb całkowitych.
do reprezentowania wykresu używam list sąsiedztwa lub użyję skończoną mapę, która odwzorowuje każdy węzeł do listy swoich następców. To zależy od tego, co chcę zrobić.
Zamiast Abelsona i Sussmana polecam Chrisa Okasakiego Purely Functional Data Structures. Mam powiązania z rozprawą Chrisa, ale jeśli masz pieniądze, rozwinął je w excellent book.
Po prostu dla uśmiechu, oto nieco przerażające, odwrócone postorderowe wyszukiwanie w pierwszej kolejności w stylu kontynuacji-przemijania w Haskell. Jest to prosto z biblioteki Hoopl optymalizatora:
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
Wyciągnąłem te linki od strony funkcjonalnej biblioteki wykresu: Wyjaśnia teorię: http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html#JFP01 Ta dokumentuje szczegóły programowania: http://web.engr.oregonstate.edu/~erwig/fgl/haskell/old/fgl0103.pdf Razem, te artykuły najlepiej odpowiadają na moje pytanie, szczególnie drugie, które jest nieco bardziej praktyczne. Dzięki! – brad