Function that checks if a substring is within another string in Haskell

user_14403537 0
Viewed 408

I need to write a function that check if a substring is within another string by using list comprehensions.

I'm using drop create a list of strings from a string to use isPrefixOf to compare the list of strings created to the substring.

Here is my code:

contains :: String -> String -> Bool
contains str substr = isPrefixOf substr (check str)
    where
    check :: String -> [String]
    check str
        |str==[]   = []
        |otherwise = [drop x str | x <- [0..length(str)-1]]

However, I get this error:

Tutorial2.hs:163:42: error:
    * Couldn't match type `[Char]' with `Char'
      Expected type: [Char]
        Actual type: [String]
    * In the second argument of `isPrefixOf', namely `(check str)'
      In the expression: isPrefixOf substr (check str)
      In an equation for `contains':
          contains str substr
            = isPrefixOf substr (check str)
            where
                check :: String -> [String]
                check str
                  | str == [] = []
                  | otherwise = [drop x str | x <- [0 .. length (str) - 1]]
    |
163 | contains str substr = isPrefixOf substr (check str)

I want to understand why I am getting this error and how do I fix it. I'm assuming it's because I'm giving isPrefixOf a list of a list [[a]] with my function check str and it doesn't take that?

haskell string
2 Answers

IsPrefixOf :: Eq a => [a] -> [a] -> Bool expects two lists of the same type (and that type should be a member of the Eq typeclass), so two Strings for example, since a String is a list of Chars.

You however provide a String (the substr), and a list of Strings (the check str has as type [String]). This thus will not typecheck. Furthermore using drop multiple times will make check str run in O(n2) which is not efficient.

You can make use of any :: Foldable f => (a -> Bool) -> f a -> Bool to check if a predicate is satisfied for any element in a foldable, for example a list. We can furthermore make use of tails :: [a] -> [[a]] to obtain all the tails of a list (including the full list) in a more efficient manner:

import Data.List(isPrefixOf, tails)

contains :: String -> String -> Bool
contains str substr = any (isPrefixOf substr) (tails str)

we can further generalize this to work with a list of any type a that is a member of the Eq typeclass:

import Data.List(isPrefixOf, tails)

contains :: Eq a => [a] -> [a] -> Bool
contains str substr = any (isPrefixOf substr) (tails str)

We can also make the function point-free by making use of flip :: (a -> b -> c) -> b -> a -> c and (.) :: (b -> c) -> (a -> b) -> a -> c:

import Data.List(isPrefixOf, tails)

contains :: Eq a => [a] -> [a] -> Bool
contains = flip (any . isPrefixOf) . tails
user_675790

The issue is that isPrefixOf expects one String, but your check returns a list of strings ([String]).

The fix is to wrap the isPrefixOf in any, which maps the function over the whole list:

contains :: String -> String -> Bool
contains str substr = any (isPrefixOf substr) (check str)
    where
    check :: String -> [String]
    -- ...

Note that check is equivalent to the built-in tails (technically it should be length str, not length str - 1, but that doesn't matter in this case), so if we make that substitution we arrive at Willem's solution:

contains :: String -> String -> Bool
contains str substr = any (isPrefixOf substr) (tails str)
user_6171590
Related