हास्केल - पैटर्न मिलान और रिकर्सन

Question

मैं हास्केल और प्रोग्रामिंग दोनों के लिए नया हूं। पैटर्न-मिलान, रिकर्सिव फ़ंक्शंस में बाध्यकारी के बारे में मेरा प्रश्न। उदाहरण के लिए, मान लीजिए कि मेरे पास एक ऐसा फ़ंक्शन है जो जांचता है कि दी गई सूची (x: xs) किसी अन्य सूची का उपमहाद्वीप है, (y: ys)। मेरे प्रारंभिक सोचा, मेरे पाठ्यपुस्तक में उदाहरण निम्नलिखित, था:

sublist [] ys = True 
sublist xs [] = False 
sublist (x:xs) (y:ys) 
    | x == y = sublist xs ys 
    | x /= y = sublist (x:xs) ys 

यह परीक्षण डेटा, उदा पर काम करता है,

sublist [1, 2, 3] [1, 2, 4, 1, 2, 3] 

जहाँ मैं यह उम्मीद विफल। मैं इसे विफल करने की उम्मीद है, क्योंकि

sublist [1, 2, 3] [1, 2, 4, 1, 2, 3] 
    = sublist [2, 3] [2, 4, 1, 2, 3] 
    = sublist [3] [4, 1, 2, 3] 

और इस बिंदु पर, मैंने सोचा, [3] = 3: sublist में [4, 1, 2, 3, और: [] के साथ (XS एक्स) मिलान किया जाएगा ] sublist में (वाई: वाईएस) के साथ मिलान किया जाएगा। तो, कैसे काम कर रहा है?

संपादित करें: यहां सभी को धन्यवाद, मुझे लगता है कि मैंने अपनी समस्या हल कर ली है। जैसा कि ध्यान दिया गया था, मैं ("अवचेतन रूप से") मेरे लिए बैकट्रैक के लिए उपन्यास चाहता था। अंतिम उत्तर का उपयोग (बीएमएफ) एक गाइड के रूप में पोस्ट किया गया, मैंने "बाध्यकारी समस्या" को हल करने के लिए समस्या को अलग करने का फैसला किया, यानी "बैकट्रैकिंग" समस्या।

subseq :: (Eq a) => [a] -> [a] -> Bool 
subseq [] _ = True 
subseq _ [] = False 
subseq (x:xs) (y:ys) = 

-- subseq' decides whether the list bound to (x:xs) = M is a prefix of the list 
-- bound to L = (y:ys); it recurses through L and returns a Bool value. subseq 
-- recurses through M and L, returning a disjunction of Bool 
-- values. Each recursive call to subseq passes M and ys to subseq', which 
-- decides whether M is a prefix of the **current list bound to ys**. 

    let subseq' :: (Eq a) => [a] -> [a] -> Bool 
     subseq' [] _ = True 
     subseq' _ [] = False 
     subseq' (x:xs) (y:ys) = (x == y) && subseq' xs ys 
      in subseq' (x:xs) (y:ys) || subseq (x:xs) ys 

Answer 1

यह क्योंकि काम कर रहा है:

• [3]x:xs3:[] के रूप में के रूप में मिलान किया जाता है,
• [4, 1, 2, 3] रूप 4:[1,2,3]
• 3/=4 तो sublist (x:xs) ysy:ys के रूप में मिलान किया जाता है का मूल्यांकन किया जाता है, जो अंततः यह सच है

ट्रेस: ​​

sublist [1, 2, 3] [1, 2, 4, 1, 2, 3] 
    = sublist [2, 3] [2, 4, 1, 2, 3] 
    = sublist [3] [4, 1, 2, 3] 
    = sublist [3] [1, 2, 3] 
    = sublist [3] [2, 3] 
    = sublist [3] [3] 
    = sublist [] [] = True 

Answer 2

sublist [1, 2, 3] [1, 2, 4, 1, 2, 3] 
= sublist [2, 3] [2, 4, 1, 2, 3] 
= sublist [3] [4, 1, 2, 3] 
= sublist [3] [4, 1, 2, 3] 
= sublist (3:[]) (4:[1,2,3])  -- Since 3 /= 4, we take sublist (x:xs) ys 
= sublist (3:[]) [1,2,3] 
= sublist (3:[]) (1:[2,3]) 
= sublist (3:[]) [2,3] 
= sublist (3:[]) (2:[3]) 
= sublist (3:[]) [3] 
= sublist [] [] 
= True 

sublist जांच करता है कि सूचियों के प्रमुखों बराबर हैं। यदि हां, तो यह उन्हें हटा देता है और कमाता है (sublist xs ys)। यदि नहीं, तो यह दूसरी सूची (sublist (x:xs) ys) से सिर हटा देता है। इस तरह से यह निम्नलिखित संघ "पाता है":

1 2 3 
| | | 
| | \-----\ 
| |  | 
1 2 4 1 2 3 

दूसरे शब्दों में, कुछ सूची ys यह जब तक वे नहीं कर रहे हैं ys से तत्वों पॉप के लिए sublist [1,2,3] ys जाँच करने के लिए 1. तो यह जब तक वे कर रहे हैं के रूप में तत्वों पॉप नहीं 2. फिर यह तब तक तत्वों को पॉप करता है जब तक वे 3 नहीं होते। यदि [1,2,3] समाप्त हो गया है, तो यह सत्य की रिपोर्ट करता है; अगर ys समाप्त हो गया है, तो यह गलत है।

Answer 3

युप्पीनेटवर्किंग और एसडीसीडब्ल्यूसी ने पहले ही समझाया है कि मिलान कैसे काम करता है। तो sublistsubsequence के समान अर्थ में एक उपन्यास की खोज करता है (आवश्यक रूप से एक ही पंक्ति में एक ही वस्तु नहीं है, बीच में कुछ भी हो सकता है)।

मैं यह ध्यान रखना चाहता हूं कि आप अक्सर dropWhile के साथ सूची के सामने अनावश्यक वस्तुओं को हटाने के लिए स्पष्ट रिकर्सन से बच सकते हैं।साथ ही, मैं एक उदाहरण देना चाहता था कि कैसे जांचें कि दो सूचियों में एक ही उपसर्ग है (आपको यह जांचने की आवश्यकता है कि दूसरी सूची में पंक्ति में पहले व्यक्ति के आइटम हैं या नहीं)।

पहला उदाहरण अपने कार्य के लिए समान है, यह के बीच में आइटम के लिए अनुमति देता है, लेकिन यह dropWhile का उपयोग करता ys के सामने आइटम हटाने के लिए:

-- Test: 
-- map ("foo" `subListOf`) ["kungfoo", "f-o-o!", "bar"] == [True,True,False] 

[] `subListOf` _ = True 
(x:xs) `subListOf` ys = 
    let ys' = dropWhile (/= x) ys  -- find the first x in ys 
    in case ys' of 
     (_:rest) -> xs `subListOf` rest 
     [] -> False 

दूसरे उदाहरण एक "घने" sublist के लिए लग रहा है:

-- Test: 
-- map ("foo" `denseSubListOf`) ["kungfoo!", "-f-o-o-"] == [True,False] 

[] `denseSubListOf` _ = True 
_ `denseSubListOf` [] = False 
xs `denseSubListOf` ys = 
    let ps = zip xs ys in 
    (length ps == length xs && all (uncurry (==)) ps) -- same prefix of xs and ys 
    || xs `denseSubListOf` (tail ys)     -- or search further 

दें कि यह देखना होगा कि दूसरी सूची शुरुआत मैं तत्वों जोड़ी द्वारा जोड़ी की तुलना (मैं उन्हें एक साथ ज़िप यह करने के लिए) के सभी पहले एक होता है ध्यान दें।

यह उदाहरण के द्वारा समझाने के लिए आसान है:

zip [1,2,3] [1,2,3,4,5] -- gives [(1,1), (2,2), (3,3)], 4 and 5 are truncated 
uncurry (==)    -- an equivalent of (\(a,b) -> a == b) 
all      -- gives True iff (uncurry (==)) is True for all pairs 
length ps == length xs -- this is to ensue that the right list is long enough 

Answer 4

Debug.Trace अपने दोस्त है। sublist रूप

sublist [] ys = trace ("A: [] "   ++ show ys) True 
sublist xs [] = trace ("B: " ++ (show xs) ++ " []") False 
sublist (x:xs) (y:ys) 
    | x == y = trace (info "C" "==") 
       sublist xs ys 
    | x /= y = trace (info "D" "/=") 
       sublist (x:xs) ys 
    where info tag op = 
      tag ++ ": " ++ (show x) ++ " " ++ op ++ " " ++ (show y) ++ 
      "; xs=" ++ (show xs) ++ ", ys=" ++ show ys 

instrumented के साथ आप देखते हैं कि क्या हो रहा है, अर्थात् है कि यह बार-बार दूसरी सूची के सिर दूर फेंक रहा है जब तक यह एक मैच पाता है:

*Main> sublist [1, 2, 3] [1, 2, 4, 1, 2, 3] 
C: 1 == 1; xs=[2,3], ys=[2,4,1,2,3] 
C: 2 == 2; xs=[3], ys=[4,1,2,3] 
D: 3 /= 4; xs=[], ys=[1,2,3] 
D: 3 /= 1; xs=[], ys=[2,3] 
D: 3 /= 2; xs=[], ys=[3] 
C: 3 == 3; xs=[], ys=[] 
A: [] [] 
True

एक और आप sublist सही ढंग से लागू करने में मदद मिलेगी उपकरण Test.QuickCheck है, एक लाइब्रेरी जो आपके द्वारा निर्दिष्ट गुणों को सत्यापित करने में उपयोग के लिए स्वचालित रूप से परीक्षण डेटा बनाती है।

उदाहरण के लिए, आप xs और ys को सेट के रूप में उपयोग करने के लिए sublist चाहते हैं और यह निर्धारित करते हैं कि पूर्व बाद वाले का सबसेट है या नहीं। हमें इस प्रॉपर्टी को निर्दिष्ट करने के Data.Set उपयोग कर सकते हैं:

prop_subsetOf xs ys = 
    sublist xs ys == fromList xs `isSubsetOf` fromList ys 
    where types = (xs :: [Int], ys :: [Int]) 

यह कहते sublist सही पर परिभाषा के बराबर होना चाहिए। prop_ उपसर्ग क्विक चेक के साथ उपयोग किए जाने वाले परीक्षण गुणों का नामकरण करने के लिए एक लोकप्रिय सम्मेलन है।

चल रहा है यह भी एक विफलता मामले को दिखाता है:

*Main> quickCheck prop_subsetOf 
*** Failed! Falsifiable (after 6 tests):     
[0,0] 
[0]

Answer 5

मुझे लगता है कि जहां गलतफहमी हो सकता है, कि (जब आप पहली बार समारोह लिखा था) आप मान लिया है कि आपके चेक x /= y = sublist (x:xs) ys में हैं (सब-बूझकर?) ने माना कि समारोह बैकट्रैक होगा और मूल फ़ंक्शन की पूंछ के साथ अपना फ़ंक्शन दोबारा करेगा, न कि उस सूची के किसी भी टुकड़े की पूंछ जो आप मेल नहीं खाते हैं।

एक अच्छा (और बेचैन) हास्केल के बारे में बात यह सिर्फ कैसे हास्यास्पद शक्तिशाली है।

एक उदाहरण के लिए, आपके द्वारा क्या चाहता था ध्यान दिया है चाहिए:

sublist []  ys = True 
sublist xs  [] = False 
sublist (x:xs) (y:ys) | x /= y = False 
         | otherwise = sublist xs ys || sublist (x:xs) ys 

जो पहली सूची के टुकड़े के सभी के लिए जाँच करेगा। फ़ंक्शन के लिए "आधिकारिक" परिभाषा (अपने दस्तावेज़ में "isInfixOf" देखें) में कुछ अतिरिक्त कार्य हैं जो मूल रूप से एक ही चीज़ का अर्थ है।

यहाँ एक और तरीका यह लिखते हैं, कि लग रहा है और अधिक मेरी आँखों के लिए "व्याख्यात्मक" है:

sublist [] ys = True 
sublist xs [] = False 
sublist xs ys = (xs == take (length xs) ys) || sublist xs (tail ys)