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: []将会与子列表中的（x：xs）匹配，并且[4,1,2,3]将会与子列表中的（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

- emi

---

目前不清楚哪里出了问题，以及你预期哪些部分会失败。在你的示例中，[3] 是 [4,1,2,3] 的子列表，所以会匹配。我猜这不是你想要的。 - mb14

刚开始学习计算机编程并选择了Haskell？我非常尊重你！当你看到我们命令式编程的代码是多么的痛苦时，你已经进入了一个全新的世界。 ：P - wheaties

抱歉，我应该表达得更清楚：我预期这个函数无法按照我的意愿执行，我的意愿是：找出一个特定的序列，例如(1:2:3:[])，是否按照顺序出现在一个列表中，例如(4:1:2:[])。间接地说，我想知道如何让我的“子列表”函数在(x /= y)评估为True时重新从原始的(x:xs)绑定开始执行。 - emi

Answer 1

它有效是因为:

• [3] 被匹配为 x:xs，即3:[]，
• [4, 1, 2, 3]被匹配为 y:ys，即4:[1,2,3]
• 3/=4 因此计算了 sublist (x:xs) ys，最终结果为True

跟踪:

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

- YuppieNetworking

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 是否包含子列表 [1,2,3]，它会从 ys 中弹出元素，只要它们不是 1 就弹出。然后它会弹出元素，只要它们不是 2。接着，它会弹出元素，只要它们不是 3。如果 [1,2,3] 已经用完，则报告 True；如果 ys 已经用完，则报告 False。

- sdcvvc

---

是的，这很有道理。我的“子列表”函数就像一个集合成员函数一样运作，例如，1、2、3是{1、2、4、1、2、3}的成员（尽管列表显然可能包含重复元素）。 - emi

这并不严格属于集合成员关系，例如1、2是{2,1}的成员，但子列表[1,2] [2,1]返回False。请参阅http://en.wikipedia.org/wiki/Subsequence。 - sdcvvc

Answer 3

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应该等同于右侧的定义。在QuickCheck中，prop_前缀是一种常见的命名测试属性的约定。

运行它也会确定一个失败的案例:

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

- Greg Bacon

Answer 4

我认为你可能误解了，当你编写函数时，你假设在检查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)

- BMeph

---

这非常有帮助。然而，在第一段代码中，如果（x /= y）评估为True，即如果x和y不等效，则“sublist list_1 list_2”不会评估为False，那么函数将无法递归。 - emi

Answer 5

YuppieNetworking和sdcwc已经解释了匹配的工作原理。所以你的sublist搜索的是与子序列相同意义的子列表（不一定是连续的项，中间可以有任何东西）。

我想指出，你可以经常使用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

- sastanin