हास्केल: फ्लैट बाइनरी पेड़

Question

मैं बाद में प्रसंस्करण के लिए एक सूची में एक बाइनरी पेड़ को फ़्लैट करने के बारे में सोच रहा था।

मैंने पहली बार बाएं और दाएं शाखाओं में शामिल होने के लिए (++) का उपयोग करने का विचार किया, लेकिन फिर खराब स्थिति में सोचा जो O(n^2) समय लेगा।

मैंने बाद में रैखिक समय में आगे बढ़ने के लिए (:) का उपयोग करके सूची को पीछे की ओर बनाने का विचार किया। हालांकि, मैंने सोचा कि अगर मैं इस सूची को एक फोल्ड-फ़ंक्शन पर भेजता हूं, तो उसे तब तक इंतजार करना पड़ेगा जब तक कि पूरे पेड़ को फोल्डिंग शुरू करने से पहले ट्रैवर्स नहीं किया जाता है, और इसलिए list fusion का उपयोग नहीं कर सकता।

मैं तो following के साथ आया था:

data Tree a = Node a (Tree a) (Tree a) | Tip 

flatten :: Tree a -> [a] 
flatten x = (flatten' x) [] 

flatten' :: Tree a -> [a] -> [a] 
flatten' (Node x left right) l = (flatten' left (x:(flatten' right l))) 
flatten' Tip l = l 

main = 
    putStrLn $ show $ flatten $ 
    (Node 2 (Node 1 Tip Tip) (Node 4 (Node 3 Tip Tip) Tip)) 

करेंगे O(n) समय में इस काम है, पेड़ की सबसे बड़ी गहराई को "ढेर अंतरिक्ष" कोई आनुपातिक की तुलना में अधिक लेने के लिए और यह एक उपभोक्ता के साथ जुड़े हुए किया जा सकता है कार्य (यानी मध्यवर्ती सूची समाप्त)? क्या यह एक पेड़ को फटकारने का "सही" तरीका है?

Answer 1

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

वैसे भी, मुझे लगता है कि यह एक पेड़ को फटकारने का सबसे अच्छा तरीका है। जब एल्गोरिदम का आउटपुट एक सूची होती है लेकिन अन्यथा सूची अनपेक्षित होती है, और वहां पर संगतता चल रही है, तो difference lists (DList एस) आमतौर पर जाने का सबसे अच्छा तरीका है। वे एक "प्रीपेन्डर फ़ंक्शन" के रूप में एक सूची का प्रतिनिधित्व करते हैं, जो आपके द्वारा संलग्न होने पर ट्रैवर्सल की आवश्यकता को समाप्त करता है, क्योंकि संलग्न करना केवल कार्य संरचना है।

type DList a = [a] -> [a] 

fromList :: [a] -> DList a 
fromList xs = \l -> xs ++ l 

append :: DList a -> DList a -> DList a 
append xs ys = xs . ys 

toList :: DList a -> [a] 
toList xs = xs [] 

ये कार्यान्वयन के अनिवार्य हैं, शेष उस से प्राप्त किए जा सकते हैं। DList रों में अनुभवहीन सपाट एल्गोरिथ्म है:

flatten :: Tree a -> DList a 
flatten (Node x left right) = flatten left `append` fromList [x] `append` flatten right 
flatten Tip = fromList [] 

के एक छोटे से विस्तार करते हैं। दूसरे समीकरण के साथ शुरू करें:

flatten Tip = fromList [] 
      = \l -> [] ++ l 
      = \l -> l 
flatten Tip l = l 

देखें कि यह कहां जा रहा है? अब पहले समीकरण:

flatten (Node x left right) 
    = flatten left `append` fromList [x] `append` flatten right 
    = flatten left . fromList [x] . flatten right 
    = flatten left . (\l -> [x] ++ l) . flatten right 
    = flatten left . (x:) . flatten right 
flatten (Node x) left right l 
    = (flatten left . (x:) . flatten right) l 
    = flatten left ((x:) (flatten right l)) 
    = flatten left (x : flatten right l) 

से पता चलता कौन कैसे DList तैयार करने के लिए अपने समारोह के बराबर है!

flatten' :: Tree a -> [a] -> [a] 
flatten' (Node x left right) l = (flatten' left (x:(flatten' right l))) 
flatten' Tip l = l 

मैं क्यों DList अन्य तरीकों से बेहतर है के लिए किसी प्रमाण की जरूरत नहीं है (और अंततः यह कैसे आप अपने उत्पादन उपभोग कर रहे हैं पर निर्भर करता है), लेकिन DList इस कुशलता से करने के लिए विहित तरीका है, और वह यह है कि आपने क्या किया है।

Answer 2

flatten' पूंछ रिकर्सिव है, इसलिए इसे किसी भी स्टैक स्पेस नहीं लेना चाहिए। हालांकि यह पेड़ के बाईं ओर नीचे चलेगा, ढेर में थोंक्स का एक गुच्छा थूक जाएगा।आप अपने उदाहरण के पेड़ पर यह आह्वान है, और WHNF तक कम हैं, तो आप कुछ है कि इस तरह दिखता है मिलना चाहिए:

: 
/\ 
1 flatten' Tip : 
      /\ 
       2 flatten' (Node 4) [] 
         / \ 
         (Node 3) Tip 
         /  \ 
         Tip  Tip 

एल्गोरिथ्म O(N) है, लेकिन यह Tip रों के साथ-साथ Node रों जांच करने के लिए है ।

यह आपके पेड़ के क्रम में फ़्लैट करने का सबसे प्रभावी तरीका प्रतीत होता है। Data.Tree मॉड्यूल में flatten फ़ंक्शन here है जो एक ही चीज़ करता है, सिवाय इसके कि यह प्री-ऑर्डर ट्रैवर्सल पसंद करता है।

अद्यतन:

   @ 
      /\ 
      @ [] 
      /\ 
     / \ 
     / \ 
     flatten' Node 2 
       / \ 
      / \ 
      /  \ 
      Node 1 Node 4 
     / \ / \ 
      Tip Tip/ \ 
       /  \ 
       Node 3  Tip 
       / \ 
       Tip Tip 

आदेश WHNF को यह कम करने के लिए ग्राफ में कमी इंजन उतारना होगा:

एक ग्राफ में कमी इंजन में, main में flatten इस तरह एक ग्राफ उत्पन्न होगा रीढ़ की हड्डी पर [] और Node 2 दबाकर रीढ़ की हड्डी। यह तो लागू करेगा flatten' समारोह है, जो इस को ग्राफ पुनर्लेखन देगा:

    @ 
       /\ 
      / \ 
      / \ 
      @  : 
      /\ /\ 
     / \ 2 \ 
     / \  \ 
     flatten' Node 1 \ 
       / \  \ 
       Tip Tip @ 
         /\ 
         @ [] 
         /\ 
        / \ 
        / \ 
        flatten' Node 4 
          / \ 
         / \ 
         /  \ 
         Node 3  Tip 
        / \ 
         Tip Tip 

और ढेर से दो तर्क पॉप करेगा। रूट नोड अभी भी डब्ल्यूएचएनएफ में नहीं है, इसलिए ग्राफ़ कमी इंजन रीढ़ की हड्डी को अनलोल करेगा, 2:... और Node 1 स्टैक पर धक्का देगा। यह तो लागू करेगा flatten' समारोह है, जो इस को ग्राफ पुनर्लेखन देगा:

    @ 
       /\ 
      / \ 
      / \ 
      @  : 
      /\ /\ 
     / \ 1 \ 
     / \  \ 
     flatten' Tip  @ 
         /\ 
        / \ 
        / : 
        @ /\ 
        /\ 2 \ 
       /Tip  @ 
       /  /\ 
       flatten'  @ [] 
          /\ 
         / \ 
         / \ 
         flatten' Node 4 
           / \ 
          / \ 
          /  \ 
          Node 3  Tip 
         / \ 
          Tip Tip 

और ढेर से दो तर्क पॉप करेगा। रूट नोड अभी भी डब्ल्यूएचएनएफ में नहीं है, इसलिए ग्राफ़ कमी इंजन रीढ़ की हड्डी को अनलोल करेगा, 1:... और Tip को स्टैक पर दबाएगा। यह तो लागू करेगा flatten' समारोह है, जो इस को ग्राफ पुनर्लेखन देगा:

    : 
       /\ 
       1 \ 
        \ 
        @ 
        /\ 
       / \ 
       / : 
       @ /\ 
       /\ 2 \ 
      /Tip  @ 
      /  /\ 
      flatten'  @ [] 
         /\ 
        / \ 
        / \ 
        flatten' Node 4 
          / \ 
         / \ 
         /  \ 
         Node 3  Tip 
        / \ 
         Tip Tip 

और ढेर से दो तर्क पॉप करेगा। अब हम डब्ल्यूएचएनएफ में हैं, जिसमें अधिकतम दो स्टैक प्रविष्टियां खपत हुई हैं (मानते हैं कि Tree नोड्स थंक्स नहीं थे जिन्हें मूल्यांकन के लिए अतिरिक्त स्टैक स्पेस की आवश्यकता थी)।

तो, flatten' पूंछ-पुनरावर्ती है। यह अतिरिक्त नेस्टेड रेडएक्स का मूल्यांकन किए बिना खुद को बदल देता है। दूसरा flatten' ढेर में एक थंक बना हुआ है, ढेर नहीं।