8

我对 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
4

5 回答 5

11

它之所以有效，是因为：

  • [3]匹配x:xs为3:[],
  • [4, 1, 2, 3]匹配y:ys为4:[1,2,3]
  • 3/=4sosublist (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
于 2010-07-09T13:56:04.953 回答
8 
  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) 中删除 head。这样它“找到”以下关联：

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

换句话说，要检查sublist [1,2,3] ys某个列表ys，它会弹出元素，ys只要它们不是 1。然后它会弹出元素，只要它们不是 2。然后它会弹出元素，只要它们不是 3。如果[1,2,3]用尽，则它报告真；如果ys用尽，则报告 False。

于 2010-07-09T13:52:05.073 回答
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> 子列表 [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=[]
一种： [] []
真的

另一个可以帮助您sublist正确实现的工具是Test.QuickCheck自动创建测试数据以用于验证您指定的属性的库。

例如，假设您要将和sublist视为集合并确定前者是否是后者的子集。我们可以使用来指定这个属性：xsysData.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
*** 失败的！可证伪（经过 6 次测试）：                  
[0,0]
[0]
于 2010-07-09T14:59:16.317 回答
2

我认为您可能会误解的地方是（当您第一次编写该函数时）您假设在您的检查中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)
于 2010-07-09T18:03:32.420 回答
1

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
于 2010-07-09T14:50:27.827 回答