查找列表1是否是haskell中列表2的序列

Question

我试图检查给定的列表是否是另一个列表的子序列:

这里是给出真实的列表的例子:

subseq "" "w"
subseq "w" "w"
subseq "ab" "cab"
subseq "cb" "cab"
subseq "aa" "xaxa"
not (subseq "aa" "xax")
not (subseq "ab" "ba")

我刚刚谈到这个,但在某些情况下,它给出了错误的结果

subseq :: Eq a => [a] -> [a] -> Bool
subseq [] [] = True
subseq [] ys = True
subseq xs [] = False
subseq (x:xs) (y:ys) = x == y || subseq xs ( 1 `drop` ys )

Answer 1

两件事,一件是高级,一件是低级.高水平第一:

您的递归案例不正确.在英语中,你写过非空列表是另一个非空列表的子序列,如果它们的第一个字符匹配,或者除了列表1中的第一个字符之外的每个字符都是每个字符的子序列而第二个列表中的前两个字符.这显然是不正确的,因为例如"aaa"不是"abc"的子序列,即使它们的第一个字符匹配,并且"db"不是"cab"的子序列,即使"b"是"b"的子序列.

更好的方法是用英语表示:"非空列表是另一个非空列表的子序列,如果:1.它们的第一个字符匹配,列表1的其余字符是剩余字符的子序列列表2,或2.它们的第一个字符不匹配,列表1是列表2中除第一个字符以外的所有字符的子序列."

由于这看起来像家庭作业,我会留给你把它翻译成Haskell代码.

低级别:代码片段

subseq (x:xs) (y:ys) = x == y || subseq xs ( 1 `drop` ys )

不会做你认为它做的事情.ys已经是第二个列表中除第一个之外的所有元素; 你不需要从中删除任何更多的元素.此外,第一种情况(subseq [] [] = True)是不必要的,因为它将被第二种情况捕获,但这不是什么大问题.