Haskell - 模式匹配和递归

Question

我对 Haskell 和编程都是新手。我关于在模式匹配的递归函数中绑定(bind)的问题。例如，假设我有一个函数可以检查给定列表 (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 )，我决定以不同的方式解决问题，以解决“绑定(bind)问题”，即“回溯”问题。

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被评估，最终为 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