Je viens de continuer à le visité définir comme un ensemble et passer en tant que paramètre. Il y a efficace log-temps implémentations de jeux de a commandé le type et extra-efficace des ensembles d'entiers.
Pour représenter un graphe-je utiliser les listes d'adjacence, ou je vais utiliser un fini de carte des cartes à chaque nœud de la liste de ses successeurs. Cela dépend de ce que je veux faire.
Plutôt que d'Abelson et Sussman, je vous recommande de Chris Okasaki est Purement Fonctionnelle des Structures de Données. Je suis lié à Chris de la thèse, mais si vous avez l'argent, il a développé dans un excellent livre.
Juste pour sourire, voici un peu effrayant inverse postorder la profondeur de recherche est réalisé dans le prolongement de passage de style en Haskell. C'est tout droit sorti de la Hoopl optimiseur de la bibliothèque:
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
