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

Question

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?

isPrefixOf expects two strings, not a string and a list of strings. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Oct 6, 2020 at 21:59

Franky · Accepted Answer · 2020-10-07 08:15:03Z

3

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(n²) 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

edited Oct 7, 2020 at 8:15

Franky

2,4212 gold badges19 silver badges33 bronze badges

answered Oct 6, 2020 at 22:07

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

straw6erry Over a year ago

Although I really appreciate your answer and expalanations, I'm afraid they're a bit lost on me since I am still a beginner in Haskell. However I do understand that I am giving isPrefixOf a wrong type with check str, so I'm wondering how I can go about giving it the correct type while retaining most of my code (at the very least one list comprehension)

MathematicalOrchid Over a year ago

@straw6erry He's saying that tails str does the same thing as your check str, but more efficiently. Also isPrefixOf substr ...list... won't work, but any (isPrefixOf substr) ...list... will work.

straw6erry Over a year ago

@MathematicalOrchid Ahhhh I see, thank you for explaining further. Thanks all for helping!

Lambda Fairy · Accepted Answer · 2020-10-07 01:40:07Z

2

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)

answered Oct 7, 2020 at 1:40

Lambda Fairy

14.9k7 gold badges45 silver badges72 bronze badges

Comments

Peter Bergman · Accepted Answer · 2022-10-31 00:45:10Z

2

There is a much simpler way (compared to the answers posted so far) to check if a string is a substring of another. You can use the isInfixOf function in Data.List.

Here is the signature:

isInfixOf :: Eq a => [a] -> [a] -> Bool

The first argument is the substring, and the second argument is the larger string in which you want to check for the substring.

Here is the documentation :)

answered Oct 31, 2022 at 0:45

Peter Bergman

7071 gold badge6 silver badges22 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related