Check, if list is a sublist of another list

Question

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

Answer 1

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

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

Some example calls:

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

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.

Another approach:

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)

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)

Which behaves like:

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.

Here is an example using 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

Which now behaves as follows:

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

Answer 2

You could use the function intersect like this:

intersect [list1] [list2] == [list1]

*Test> intersect [] [] == []
True
*Test> intersect [1] [] == [1]
False
*Test> intersect [2,4,6,4] [9,5,4,2,6,3,3] == [2,4,6,4]
True
*Test> intersect [1,2,3] [3,2,5,4] == [1,2,3]
False

You will have to import Data.List for this.