Haskell - 模式匹配和遞歸

Question

我是Haskell和編程的新手。我的問題綁定模式匹配，遞歸函數。例如，假設我有一個函數來檢查給定列表（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：在子列表[4,1，2，3，和：[]下面將（XS x）的匹配]將在子列表中與（y：ys）匹配。那麼，子列表是如何工作的呢？

編輯：感謝這裏的每個人，我想我已經解決了我的問題。如前所述，我是（「潛意識」）想要子列表爲我回溯。使用最後回答（BMeph）作爲指導，我決定以不同的方式解決問題，以解決「綁定問題」，即「回溯」問題。

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:xs爲3:[]匹配，
• [4, 1, 2, 3]匹配的y:ys爲4:[1,2,3]
• 3/=4所以sublist (x:xs) ys進行評估，最終爲真

trace：

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 xs ys）。如果不是，則刪除第二個列表中的頭（sublist (x:xs) ys）。這樣，「發現」下面的關聯關係：

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

換句話說，檢查sublist [1,2,3] ys一些列表ys它彈出從ys元素，只要他們不是1。然後它，只要他們是彈出元素不是2.然後，只要它們不是3，就會彈出元素。如果[1,2,3]用盡，則它報告爲真;如果ys用盡，則報告爲False。

Answer 3

YuppieNetworking和sdcwc已經解釋了匹配是如何工作的。因此，您的sublist搜索的子列表與subsequence搜索子列表（不一定是連續的相同項目，其間可能有任何內容）。

我想指出，你可以經常避免顯式遞歸從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 

第二個例子查找「密集」子列表：

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

你看到發生了什麼，即它的反覆丟掉第二列表的頭，直到它找到一個匹配：

*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，它是一個自動創建測試數據以用於驗證您指定的屬性的庫。

例如，假設您想要sublist將xs和ys作爲集合並確定前者是否是後者的子集。我們可以用Data.Set指定此屬性：

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

這是說sublist應相當於右邊的定義。前綴prop_是命名與QuickCheck一起使用的測試屬性的流行慣例。

運行它也指出故障狀態下：

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

Answer 5

我想，你可能是誤會，是（當你第一次寫的功能），您認爲在您的支票x /= y = sublist (x:xs) ys你（潛意識？ ）假定函數將回溯並重新做你的函數與原始的第二個列表的尾巴，而不是你使用的列表中不匹配的任何一部分的尾部。

一個不錯的（和不安）關於Haskell是它是多麼可笑強大。

舉一個例子，這裏是你如何想什麼應該看：

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)