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

Answer 1

它的工作原因是:

• [3]匹配x:xs为3:[],
• [4, 1, 2, 3]匹配y:ys为4:[1,2,3]
• 3/=4所以sublist (x:xs) ys被评估,最终是真的

跟踪:

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用尽,则报告错误.