Einen Baum verfolgen?

Question

Ich habe einen Typ für einen Baum, wie so:

data Tree a = EmptyTree | Tree a [Tree a] deriving (Show, Ord, Eq) 

freeTree :: Tree Integer 
freeTree = Tree 2 [Tree 5 [], Tree 6 [Tree 8 [], Tree 9 []], Tree 7 []] 

main = print freeTree 

Was ich zu tun versuche, eine Funktion zu schreiben, die sagen, wie so verwendet werden könnten:

trace freeTree 

Und was für eine Spur auf dieser Baum zurückkehren würde ist: [2],[2,5],[2,6],[2,7],[2,6,8],[2,6,9]

im Grunde, was es tut, ist:

eine Liste von Knoten Halten sie bereits auf den ‚Stapel‘ (die Wurzel nein in jeder Tiefe, die uns hierher gebracht hat). Jedes Mal, wenn Sie einen neuen Knoten erreichen, fügen Sie der Ergebnisliste eine Liste hinzu, bei der es sich um die Liste der Stack-Knoten ++ current_node handelt.

Kann mir jemand einen Rat geben, wie man das macht?

Dank

Answer 1

Eine erste (nicht wirklich effiziente Implementierung):

trace :: Tree a -> [[a]] 
trace t = trace' [([],t)] [] 

type Level a = [([a],Tree a)] 

trace' :: Level a -> Level a -> [[a]] 
trace' [] [] = []           -- current and next level empty? We're done! 
trace' [] l = trace' l []         -- current level exhausted? Next level becomes current level and we construct a new level 
trace' ((_,EmptyTree):ts) lu = trace' ts lu    -- currently an EmptyTree? Skip it 
trace' ((h,Tree t c):ts) lu = ht : trace' ts (lu++el)  -- currently a tree? Enumerate and add childs 
    where ht = h++[t] 
      el = map (\x -> (ht,x)) c 

Der Algorithmus verwendet zwei Level a ‚s, das aktuelle Niveau und das nächste Level. Sie iterieren immer zuerst über die aktuelle Ebene und für jedes Element der aktuellen Ebene fügen Sie die untergeordneten Elemente dieser Ebene der nächsten Ebene hinzu, bis die aktuelle Ebene erschöpft ist. Das einzige Problem bei diesem Ansatz besteht darin, dass die Operationen sehr teuer sind, insbesondere da sie links assoziativ und nicht rechts assoziativ angewendet werden. Durch die Verwendung einer kompakteren Tupel-Listendarstellung kann man es auch etwas speichereffizienter machen.

Sie können es effizienter machen, indem eine FIFO-Warteschlange, zum Beispiel this one (lasst sie für alle Warteschlangen zumindest die Schnittstelle übernimmt das gleiche ist, so, wenn Sie ein anderes bevorzugen, können Sie Plätze tauschen).

In diesem Fall würde der Code gelesen:

type Level a = [([a],Tree a)] 
type LevelFiF a = FIFO ([a],Tree a) 

trace' :: Level a -> LevelFiF a -> [[a]] 
trace' [] ln | isEmpty ln = [] 
      | otherwise = trace' (toList ln) empty 
trace' ((h,Tree t c):ts) ln = ht : trace' ts (foldl (flip enqueue) ln el) 
    where ht = h++[t] 
      el = map (\x -> (ht,x)) c 
trace' (_:ts) ln = ht : trace' ts ln 

Sie können wahrscheinlich auch monadischen Warteschlangen über einen Link Haskells es effizienter gestalten.

Answer 2

Im Grunde wollen Sie Zustand über rekursive Aufrufe zu trace halten. Betrachten Sie eine Funktionssignatur wie folgt:

-- First argument is the tree to trace 
-- Second argument is the accumulated route 
trace :: Tree a -> [a] -> [[a]] 

Mit dieser Struktur machen Sie effektiv eine Tiefensuche in diesem Baum.

Answer 3

Wir denken, dass wir ein trie haben, wobei jeder Knoten eine gültigen Wortmarken, und dann ist die Aufgabe, die Worte zu gewinnen:

trace :: Tree a -> [[a]] 
trace (Tree a ts) = [a] : map (a:) (trace =<< ts) 
trace Empty  = [] 

tree1 = Tree 1 [Tree 2 [ Tree 3 [ Tree 4 [Tree 5 [] ]]]] 
tree2 = Tree 2 [Tree 5 [], Tree 6 [Tree 8 [], Tree 9 []], Tree 7 []] 

-- trace tree1 = [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]] 
-- trace tree2 = [[2],[2,5],[2,6],[2,6,8],[2,6,9],[2,7]] 

Diese eine Tiefe erste Lösung, die träge verarbeitet werden kann, mit Platz benötigt nur für das aktuelle Wort. Es gibt keine Wörter in genau der von Ihnen angegebenen Reihenfolge zurück. wenn strenge Breiten erster Ordnung kritisch ist, sollten Sie sich für iterative Vertiefung gehen:

traceIDeep :: Tree a -> [[a]] 
traceIDeep t = concat $ takeWhile (not . null) $ map (`lvl` t) [0..] 
    where 
    lvl 0 (Tree a ts) = [[a]] 
    lvl l (Tree a ts) = map (a:) (lvl (l - 1) =<< ts) 
    lvl _ Empty  = [] 

-- Now we have bfs order: 
-- trace tree2 = [[2],[2,5],[2,6],[2,7],[2,6,8],[2,6,9]]