检查，如果列表是另一个列表的子列表

Question

我想编写一个函数，检查一个列表是否是另一个列表的子列表。我写了这个，但它不起作用，但我想我需要这样的东西。感谢帮助。

subList :: Eq a => [a] -> [a] -> Bool 
subList _ [] = False 
subList [] _ = True 
subList (x:xs) (y:ys) = 
    x == y = subList xs ys 
    otherwise = subList (x:xs) ys 

Answer 1

您的代码已接近正常工作，但只需稍作更改。正如其他人在评论中所说的，您需要包含|花样守卫，并从第一个函数调用中删除=。这里是最后的3条线应该是什么样子：

subList (x:xs) (y:ys) 
    | x == y = subList xs ys 
    | otherwise = subList (x:xs) ys 

这将解决你的大部分代码，但是你还需要添加的基本情况subList [] [] = True，因为空单[]是的一个子表另一个空列表[]，就像[1]是[1]的子列表。

添加这些改变，你的代码应该是这样的：

subList :: Eq a => [a] -> [a] -> Bool 
subList [] [] = True 
subList _ [] = False 
subList [] _ = True 
subList (x:xs) (y:ys) 
    | x == y = subList xs ys 
    | otherwise = subList (x:xs) ys 

一些示例要求：

Prelude> subList [] [] 
True 
Prelude> subList [1] [1,2,3] 
True 
Prelude> subList [1] [4,2,3] 
False 
Prelude> subList [1] [] 
False 
Prelude> subList [1,2] [1,2] 
True 
Prelude> subList [1,2] [2,1] 
False 
Prelude> subList [1,2] [1,2,2,1] 
True 

然而，他们与这样的调用问题：

Prelude> subList [1,3] [1,2,3] 
True 

意味着[1,3]是[1,2,3]的子列表。这可能是有意的，但如果不是，那么你需要改变你的方法。

另一种方法：

为了您的两份名单，xs和ys，您可以改为分裂成ys长度xs的子列表，让我们说subys，并检查是否存在subysxs。要做到这一点，你可以使用splitAt，每n字符分割一个列表。下面是一个例子功能：

split_lists :: Int -> [a] -> [[a]] 
split_lists _ [] = [] 
split_lists n xs 
    | length first == n = first : restxs 
    | otherwise = restxs 
    where (first, rest) = splitAt n xs 
      restxs = split_lists n (tail first ++ rest) 

如果你不希望使用splitAt，你可以做这样的事情：

split_lists :: Int -> [a] -> [[a]] 
split_lists _ [] = [] 
split_lists n xs = filter (\x -> length x == n) list 
    where list = take n xs : split_lists n (drop 1 xs) 

它的行为，如：

Prelude> split_lists 3 [1,2,3,4,5,6,7,8,9,10] 
[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9,10]] 

然后你可以使用any来检查第一个列表是否存在于第二个列表中，或者您可以使用正常递归，直至您。

下面是一个例子使用any：

subList :: (Eq a) => [a] -> [a] -> Bool 
subList [] [] = True 
subList xs ys = any (==xs) subys 
    where subys = (split_lists (length xs) ys) 

下面是一个例子使用递归：

subList :: (Eq a) => [a] -> [a] -> Bool 
subList [] [] = True 
subList xs ys = check_lists xs subys 
    where subys = (split_lists (length xs) ys) 

check_lists :: (Eq a) => [a] -> [[a]] -> Bool 
check_lists _ [] = False 
check_lists xs (y:ys) 
    | xs == y = True 
    | otherwise = check_lists xs ys 

现在的行为如下：

Prelude> subList [] [] 
True 
Prelude> subList [1] [1,2,3] 
True 
Prelude> subList [1] [4,2,3] 
False 
Prelude> subList [1] [] 
False 
Prelude> subList [1,2] [1,2] 
True 
Prelude> subList [1,2] [2,1] 
False 
Prelude> subList [1,2] [1,2,2,1] 
True 
Prelude> subList [1,3] [1,2,3] 
False 
Prelude> subList [1,2] [0,1,2,3] 
True