एक पेड़ का पता लगाने?

Question

मैं बहुत की तरह एक पेड़ के लिए एक प्रकार है:

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 

मुझे क्या करना कोशिश कर रहा हूँ एक समारोह है कि इस्तेमाल किया जा सकता लिखना है तो की तरह कहते हैं:

trace freeTree 

और क्या एक निशान पर इस पेड़ वापसी होगी है: [2],[2,5],[2,6],[2,7],[2,6,8],[2,6,9]

मूल रूप से क्या यह करता है:

पहले से ही 'ढेर' पर नोड्स की एक सूची रखें (रूट नहीं प्रत्येक गहराई पर हमें यहां मिला)। हर बार जब आप एक नए नोड तक पहुंचते हैं, तो एक सूची जोड़ें जो परिणाम सूची में स्टैक नोड्स ++ current_node की सूची है।

क्या कोई इसे करने के तरीके पर कोई सलाह दे सकता है?

धन्यवाद

Answer 1

एक पहला (वास्तव में कुशल नहीं कार्यान्वयन): अगर सख्त चौड़ाई-पहले के आदेश के लिए महत्वपूर्ण है, तो आप पुनरावृत्ति मजबूत बनाने के लिए जाना चाहिए

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 

एल्गोरिथ्म दो Level a के उपयोग करता है, वर्तमान स्तर और अगला स्तर। आप हमेशा मौजूदा स्तर पर पहले और वर्तमान स्तर में प्रत्येक आइटम के लिए फिर से सक्रिय करते हैं, आप वर्तमान स्तर समाप्त होने तक उस स्तर के बच्चे को अगले स्तर तक जोड़ते हैं। इस दृष्टिकोण के साथ एकमात्र समस्या यह है कि ++ संचालन काफी महंगा हैं, खासकर जब से वे बाएं सहयोगी लागू होते हैं और सही सहयोगी नहीं होते हैं। एक और कॉम्पैक्ट टुपल सूची प्रतिनिधित्व का उपयोग करके इसे थोड़ा और अधिक मेमोरी कुशल बना सकता है।

आप इसे और अधिक, एक फीफो कतार का उपयोग कर उदाहरण this one के लिए होने वाले दक्ष बना सकते हैं (मान लेते हैं कम से कम सभी कतारों के लिए इंटरफ़ेस एक ही है, इसलिए मामले में आप एक दूसरे को पसंद करते हैं, तो आप स्थानों स्वैप कर सकते हैं करते हैं)।

उस मामले में कोड लिखा होगा:

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 

आप शायद यह और अधिक कुशल के रूप में अच्छी तरह से हास्केल के monadic कतारों से एक का उपयोग कर सकते हैं।

Answer 2

मूल रूप से आप trace को पुनरावर्ती कॉल भर में राज्य बनाए रखना चाहते हैं। तो इस तरह एक फ़ंक्शन हस्ताक्षर पर विचार करें:

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

इस संरचना के साथ आप प्रभावी रूप से इस पेड़ पर गहराई से पहली खोज कर रहे हैं।

Answer 3

हम सोच सकते हैं कि हम एक trie जहां प्रत्येक नोड एक वैध शब्द के निशान है, और उसके बाद नौकरी शब्द भर्ती के लिए है:

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]] 

यह एक गहराई-प्रथम समाधान है कि lazily के साथ कार्रवाई की जा सकती है अंतरिक्ष केवल वर्तमान शब्द के लिए आवश्यक है। यह आपके द्वारा निर्दिष्ट सटीक क्रम में शब्दों को वापस नहीं करता है;

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]]