检查列表是否为另一个列表的子列表 [英] Check, if list is a sublist of another list

问题描述

我想编写一个函数来检查一个列表是否是另一个列表的子列表.我写了这个，但是没有用，但是我想我需要这样的东西.感谢您的帮助.

I'd like to write a function that checks if one list is a sublist of another list. I wrote this, but it is not working, but I need something like this, I guess. Thanks for help.

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

推荐答案

您的代码已接近正常运行，但只需要进行一些细微的更改.就像其他人在评论中说的那样，您需要包括|模式防护，并从第一个函数调用中删除=.这是最后三行的样子:

Your code is close to working, but just needs some minor changes. As other have said in the comments, you need to include | pattern guards, and remove = from the first function call. Here is what the last 3 lines should look like:

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

这将在很大程度上修复您的代码，但是您还需要添加基本案例subList [] [] = True，因为空列表[]是另一个空列表[]的子列表，就像是[1]的子列表.

This will fix up your code for the most part, but you also need to add the base case subList [] [] = True, because the empty list [] is the a sublist of another empty list [], just like [1] is a sublist of [1].

添加这些更改，您的代码将如下所示:

Adding these changes, your code would look like this:

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

但是，他们在这样的通话中遇到了问题:

However, their is problem with a call like this:

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

暗示[1,3]是[1,2,3]的子列表.这可能是有意的，但如果不是这样，则需要更改方法.

implying that [1,3] is a sublist of [1,2,3]. This could be intended, but if it is not, then you need to change your approach.

另一种方法:

对于两个列表xs和ys，您可以将ys分为长度为xs的子列表，假设为subys，并检查subys中是否存在xs.为此，您可以使用 splitAt ，该列表每n个字符分割一个列表.这是一个示例函数:

For your two lists, xs and ys, You could instead split the ys into sublists of length xs, let's say subys, and check if xs exists in subys. To do this, you could use splitAt, which splits a list every n characters. Here is an example function:

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，则可以执行以下操作:

If you don't wish to use splitAt, you could do something like this:

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]]

然后，您可以使用 检查第一个列表是否存在于拆分为子列表的第二个列表中，或者您可以只使用普通递归.

Then you could just use any to check if the first list exists in the second list splitted into sublists, or you could just use normal recursion, up to you.

以下是使用any的示例:

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

以下是使用递归的示例:

Here is an example using recursion:

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

这篇关于检查列表是否为另一个列表的子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！