CODEWITHSUNDEEP
haskellcomparesequence
Zero
Zero

Reputation: 21

Haskell: compare sequences and count the length of the prefix that is common

Im new to haskell and Im writing a function that compares two sequences and reports the length of the prefix they have in common. This is what I have so far but it doesn't work for all cases.

commonLen :: Eq a => [a] -> [a] -> Int
commonLen (x:xs) [] = 0
commonLen (x:xs) (y:ys) | x==y = 1+(commonLen xs ys)
                        | otherwise = commonLen xs ys

Any ideas where im going wrong? Any help would be appreciated

Upvotes: 1

Views: 247

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477065

You should not recurse in case x is different from y. In that case we return 0:

commonLen :: Eq a => [a] -> [a] -> Int
commonLen [] _ = 0
commonLen _ [] = 0
commonLen (x:xs) (y:ys) | x == y = 1 + commonLen xs ys
                        | otherwise = 0  -- ← return 0

You also can avoid the explicit recursion, and work with:

commonLen :: Eq a => [a] -> [a] -> Int
commonLen xs ys = length (takeWhile id (zipWith (==) xs ys))

here we iterate over both lists concurrently, and compare the elements. We thus make a list of Bools that is True if the elements of the two lists match. Then we use takeWhile to take elements as long as the item is True, and we use length to determine the number of elements in that list. Due to Haskell's laziness, we will never evaluate the entire list if one of the elements differs from the corresponding element in the other list.

Upvotes: 4

Related Questions