我是一名新手,对于Haskell和编程都不太熟悉。我的问题是关于模式匹配和递归函数中的绑定。例如,假设我有一个函数,检查给定列表(x:xs)是否为另一个列表(y:ys)的子列表。我的初始想法是,按照我的教科书中的示例,编写以下代码:
在这一点上,我认为[3] = 3: []将会与子列表中的(x:xs)匹配,并且[4,1,2,3]将会与子列表中的(y:ys)匹配。那么,子列表是如何工作的呢?
编辑:感谢这里的所有人,我想我已经解决了我的问题。正如注意到的那样,我“下意识地”希望子列表能够为我回溯。使用BMeph最后发表的答案作为指南,我决定以不同的方式来解决问题,以解决“绑定问题”,即“回溯”问题。
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