檢查，如果列表是另一個列表的子列表

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