Haskell: Check if the first list is a prefix of the second

Question

I am trying to write a program that checks if the first list is a prefix of the second list. for example, [5,6] is prefix of [1,5,6,7]. here is my working code but basically I don't have an idea on how to do it.

prefix [Int] -> [Int] -> Bool 
prefix [] [] = [] 
prefix y (x:xs)  
| x == y    = prefix y xs 
| otherwise = 0 

any help please ?

Answer 1

Your code does not make much sense if we look at the types:

prefix [Int] -> [Int] -> Bool 
prefix [] [] = [] 
prefix y (x:xs)  
| x == y    = prefix y xs 
| otherwise = 0

Since the two arguments are lists ([Int]), this thus means that y is an [Int], x is an Int, and xs is an [Int]. But then you compare x == y, you can not compare a list with an element. (==) is defined as (==) :: Eq a => a -> a -> Bool.

There are also other problems here: you return a list in the first clause, but the return type is a Bool, and later you return a 0 (again, it should be a Bool).

In case we define a function, we first need to define a certain model for it. When is a list l1 a prefix of a list l2? In case l1 is an empty list, then l1 is always a prefix, regardless of the value of the second list, so:

prefix [] _ = True

In case l1 is a list (i.e. (x:xs)), then it is not a prefix in two cases: (1) in case l2 is an empty list; and (2) in case the first item of l2 (y in (y:ys)) is not equal to x, so:

prefix _ [] = False
prefix (x:xs) (y:ys) | x /= y = False
                     | otherwise = ...

Now the question is what to do with prefix (x:xs) (y:ys) in case x == y. In that case we recurse on the two list, so the result of prefix (x:xs) (y:ys) == prefix xs ys (only in case x == y), so:

                     | otherwise = prefix xs ys

Or now in full:

prefix :: [Int] -> [Int] -> Bool
prefix [] _ = True
prefix _ [] = False
prefix (x:xs) (y:ys) | x /= y = False
                     | otherwise = prefix xs ys

We can further generalize the expression to Eq a => [a] -> [a] -> Bool such that it works with any type a that is an Eq instance (so there is a (==) instance defined over a):

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

We can also swap the conditions, since usually positive logic is easier to understand than negative logic:

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

now we can furthermore remove the guards, and use an (&&) :: Bool -> Bool -> Bool instead:

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

Answer 2

Just leaving my two cents here with a combination of functions from Prelude:

isPrefix :: Eq a => [a] -> [a] -> Bool
isPrefix l1 l2 = take (length l1) l2 == l1