मेरे पास इस तरह से डेटाटाइप है

datatype 'a bin_tree = 
    Leaf of 'a
  | Node of 'a bin_tree    (* left tree *)
           * int           (* size of left tree *)
           * int           (* size of right tree *)
           * 'a bin_tree   (* right tree *)

तो सही पेड़ के लिए एक उदाहरण होगा:

val tree1 =
  Node(Node(Node(Leaf 47, 1, 1, Leaf 38),
            2,1,
            Leaf 55),
       3,2,
       Node(Leaf 27, 1, 1, Leaf 96))

और पेड़ का उल्लंघन करने का एक उदाहरण होगा

val tree1false =
  Node(Node(Node(Leaf 47, 1, 1, Leaf 38),
            2,1,
            Leaf 55),
       4,2,
       Node(Leaf 27, 1, 1, Leaf 96))

मैं एक विधेय परीक्षा कैसे लिख सकता हूँ जैसे कि

- test tree1;
val it = true : bool
- test tree1false;
val it = false : bool
1
Jon Anderson 13 सितंबर 2020, 02:55

1 उत्तर

सबसे बढ़िया उत्तर

यह एक पुनरावर्ती समस्या है। पेड़ों पर पुनरावर्ती समस्याओं को हल करने से पहले, सूचियों पर पुनरावर्तन पर दृढ़ समझ होना एक अच्छा विचार है। आप कह सकते हैं कि पेड़ सूचियों के सामान्यीकरण हैं, या यह कि सूचियाँ पेड़ों के विशेष मामले हैं: सूचियों में एक पूंछ होती है, पेड़ के प्रकार के आधार पर पेड़ों की कोई भी संख्या हो सकती है। तो यहां बताया गया है कि आप सूचियों का उपयोग करके समस्या का पुनर्निर्माण और समाधान कैसे कर सकते हैं:

यदि, सामान्य सूची परिभाषा के बजाय, आपके पास एक सूची है जो अपनी लंबाई को भी याद करती है:

(* datatype 'a list = [] | :: of 'a * 'a list *)

datatype 'a lenlist = Nil | Cons of int * 'a * 'a lenlist

फिर आप परीक्षण कर सकते हैं कि संग्रहीत लंबाई मानों की वास्तविक संख्या के अनुसार है।

मैं एक फंक्शन बनाकर शुरू करूँगा जो रिकर्सन करने वाले फंक्शन के हिस्से को चित्रित करने के लिए मायने रखता है:

(* For regular built-in lists *)
fun count0 [] = 0
  | count0 (x::xs) = 1 + count0 xs

(* Counting the memoized list type disregarding the n *)
fun count1 Nil = 0
  | count1 (Cons (n, x, xs)) = 1 + count1 xs

अगला भाग यह है कि मैं प्रत्येक पुनरावर्ती चरण में, यह परीक्षण करना चाहता हूं कि संग्रहीत संख्या n भी वास्तविक गणना के अनुसार है। इस फ़ंक्शन का रिटर्न प्रकार क्या है? ठीक है, आप जो test फ़ंक्शन चाहते हैं वह 'a lenlist -> bool होना चाहिए और count फ़ंक्शन जो मैंने बनाया है वह 'a lenlist -> int है।

मैं सुझाव दूंगा कि आप एक ऐसा testcount बनाएं जो दोनों काम करता हो। लेकिन आप ऐसा कई तरह से कर सकते हैं, उदा. इसे "अतिरिक्त तर्क" देकर, या इसे "अतिरिक्त वापसी मान" देकर। मैं दोनों का प्रदर्शन करूंगा, बस यह दिखाने के लिए कि कभी-कभी एक दूसरे से बेहतर होता है और अनुभव आपको बताएगा कि कौन सा है।

यहाँ एक val testcount1 : 'a lenlist -> bool * int फ़ंक्शन है:

fun testcount1 Nil = (true, 0)
  | testcount1 (Cons (n, x, xs)) =
    let val (good_so_far, m) = testcount1 xs
        val still_good = good_so_far andalso n = m + 1
    in (still_good, m + 1)
    end

val goodList = Cons (4, #"c", Cons (3, #"o", Cons (2, #"o", Cons (1, #"l", Nil))))
val badList = Cons (3, #"d", Cons (2, #"e", Cons (1, #"r", Cons (0, #"p", Nil))))

इसका परीक्षण,

- testcount1 goodList;
> val it = (true, 4) : bool * int
- testcount1 badList;
> val it = (false, 4) : bool * int

इससे पता चलता है कि testcount1, संख्याएं जोड़ते हैं या नहीं और सूची की वास्तविक लंबाई लौटाता है, जो यह जांचने के लिए आवश्यक था कि प्रत्येक चरण में संख्याएं जुड़ती हैं, लेकिन अंत में अब आवश्यक नहीं है। आप इस testcount फ़ंक्शन को एक सरल test फ़ंक्शन में लपेट सकते हैं जो केवल bool की परवाह करता है:

fun test xs = #1 (testcount1 xs)

इसके बारे में जाने का एक और तरीका यहां दिया गया है: testcount1 रिकर्स के तरीके से कुछ संतोषजनक नहीं है। यह m + 1s की गणना करता रहता है, भले ही यह निर्धारित करने में सक्षम हो कि एक सूची (जैसे Cons (0, #"p", Nil) पर) टूटी हुई है।

यहाँ एक वैकल्पिक val testcount2 : 'a lenlist * int -> bool है जो एक संख्या को इसके बजाय एक अतिरिक्त तर्क में संग्रहीत करता है:

fun testcount2 (Nil, 0) = true
  | testcount2 (Nil, _) = false
  | testcount2 (Cons (n, x, xs), m) =
      n = m andalso testcount2 (xs, m - 1)

यह मेरे लिए बहुत अधिक साफ-सुथरा लगता है: फ़ंक्शन पूंछ-पुनरावर्ती है, और जब यह महसूस होता है कि कुछ गड़बड़ है तो यह तुरंत बंद हो जाता है। तो अगर यह सिर पर टूट गया है तो इसे पूरी सूची को पार करने की आवश्यकता नहीं है। नकारात्मक पक्ष यह है कि इसे लंबाई जानने की जरूरत है, जिसे हम अभी तक नहीं जानते हैं। लेकिन हम यह मानकर क्षतिपूर्ति कर सकते हैं कि जो कुछ भी विज्ञापित है वह सही है जब तक कि यह स्पष्ट रूप से मामला न हो, या नहीं।

इस फ़ंक्शन का परीक्षण करने के लिए, आपको इसे न केवल goodList या badList बल्कि एक m भी देना होगा:

- testcount2 (goodList, 4);
> val it = true : bool
- testcount2 (badList, 4);
> val it = false : bool
- testcount2 (badList, 3);
> val it = false : bool

यह महत्वपूर्ण है कि यह फ़ंक्शन केवल n = m की तुलना नहीं करता है, क्योंकि badList में, इसका परिणाम यह होगा कि badList 3 तत्व लंबा है, क्योंकि n = m के लिए सत्य है सभी Cons मामलों में प्रत्येक पुनरावृत्ति। यह उन दो Nil मामलों में मदद करता है जिनके लिए हमें 0 तक पहुंचना होता है, उदाहरण के लिए नहीं। ~1 जैसा कि badList के मामले में है।

इस फ़ंक्शन को इस तथ्य को छिपाने के लिए test के अंदर भी लपेटा जा सकता है कि हम इसे 'a lenlist से प्राप्त एक अतिरिक्त तर्क खिलाते हैं:

fun size Nil = 0
  | size (Cons (n, _, _)) = n

fun test xs = testcount2 (xs, size xs)

कुछ नैतिकता अब तक:

  • कभी-कभी आपकी प्रारंभिक समस्या को हल करने के लिए सहायक कार्यों को बनाना आवश्यक होता है।
  • उन सहायक कार्यों को आपके द्वारा प्रदान किए जाने वाले फ़ंक्शन के समान प्रकार के हस्ताक्षर के लिए प्रतिबंधित नहीं किया जाता है (चाहे यह स्कूल में अभ्यास के लिए हो, या बाहरी एपीआई/लाइब्रेरी के लिए)।
  • कभी-कभी यह उस प्रकार का विस्तार करने में मदद करता है जो आपका फ़ंक्शन देता है।
  • कभी-कभी यह आपके कार्यों के तर्कों को बढ़ाने में मदद करता है।
  • सिर्फ इसलिए कि आपका कार्य "फ़ंक्शन लिखें foo -> bar" है, इसका मतलब यह नहीं है कि आप इसे ऐसे फ़ंक्शंस बनाकर नहीं बना सकते हैं जो foo या bar से अधिक या कम रिटर्न देते हैं।

अब, बाइनरी ट्री पर इसे हल करने के लिए कुछ संकेतों के लिए:

डेटा प्रकार को दोहराते हुए,

datatype 'a bin_tree = 
    Leaf of 'a
  | Node of 'a bin_tree    (* left tree *)
           * int           (* size of left tree *)
           * int           (* size of right tree *)
           * 'a bin_tree   (* right tree *)

आप उपरोक्त विचारों के आधार पर अपने कार्य के लिए एक कंकाल का निर्माण शुरू कर सकते हैं:

fun testcount3 (Leaf x, ...) = ...
  | testcount3 (Leaf x, ...) = ...
  | testcount3 (Node (left, leftC, rightC, right), ...) = ...

मैंने यहां कुछ संकेत एम्बेड किए हैं:

  • आपके समाधान में संभवतः Leaf x और Node (left, leftC, rightC, right) के विरुद्ध पैटर्न मिलान होना चाहिए। और "अतिरिक्त तर्क" प्रकार के समाधान (जो कम से कम सूचियों के लिए अच्छा साबित हुआ, लेकिन हम देखेंगे) को दो Leaf x मामलों की आवश्यकता है। ऐसा क्यों था?
  • यदि, सूचियों के मामले में, "अतिरिक्त तर्क" m सूची की अपेक्षित लंबाई का प्रतिनिधित्व करता है, तो पेड़ों के मामले में "अतिरिक्त तर्क" क्या दर्शाता है? आप यह नहीं कह सकते कि "यह सूची की लंबाई है", क्योंकि यह एक पेड़ है। आप उस हिस्से पर कब्जा कैसे करते हैं जहां एक पेड़ शाखा करता है?
  • यदि यह अभी भी बहुत कठिन है, तो बिना कॉपी-पेस्ट के सूचियों की समस्या को हल करने पर विचार करें। यानी, आपको इस उत्तर में समाधान देखने की अनुमति है (लेकिन कोशिश न करें), लेकिन आपको कोड कॉपी-पेस्ट करने की अनुमति नहीं है। अगर आप इसे कॉपी करना चाहते हैं तो आपको इसे टाइप करना होगा।
  • शुरुआत के रूप में, सहायक फ़ंक्शन size को परिभाषित करने का प्रयास करें जिसका उपयोग test testcount2 से किया गया था, लेकिन पेड़ों के लिए। तो हो सकता है कि नाम ओवरलैप से बचने के लिए इसे sizeTree कहें, लेकिन इसके अलावा, कोशिश करें और इसे समान बनाएं। यहाँ एक कंकाल है:
fun sizeTree (Leaf x) = ...
  | sizeTree (Node (left, leftC, rightC, right)) = ...

एक बार लिखे जाने पर testcount3 और sizeTree को एक साथ चिपकाना ताऊ की तरह आसान होना चाहिए।

1
Simon Shine 17 सितंबर 2020, 04:05