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)