CODEWITHSUNDEEP
haskellfunctional-programming
Marcus Vinícius Monteiro
Marcus Vinícius Monteiro

Reputation: 8079

Haskell: How does the Data.List.isInfixOf function work?

I've been trying to understand the isInfixOf function from the Data.List module, to no avail. Here's the code:

     isInfixOf               :: (Eq a) => [a] -> [a] -> Bool
     isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)

     -- Example:
     --
     -- >isInfixOf "Haskell" "I really like Haskell." -> True
     -- >isInfixOf "Ial" "I really like Haskell." -> False

The any returns True if at least one item in the list fulfills the condition. It's type is (a -> Bool) -> [a] -> Bool

The isPrefixOf and the tails functions codes are these:

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

    tails :: [a] -> [[a]]
    tails xs = xs : case xs of 
                    [] -> [] 
                    _  : xs' -> tails xs'

    -- Example: 
    -- tails "abc" == ["abc", "bc", "c",""]

I've read about curried functions and partial applied functions but I couldn't understand it yet, neither could I understand how this particular function works. How can it work if any takes lists, not a list of lists, as a parameter?

Upvotes: 1

Views: 4132

Answers (1)

Guiraldelli
Guiraldelli

Reputation: 532

We could read isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack) as: return True if needle isPrefixOf any subdivision of haystack taking away the first elements (i.e., taking the tails) of it.

Isn't it clear yet? Let's try another approach, using your example.

isInfixOf "Haskell" "I really like Haskell."

Giving that String is the same as [Char], we have the following signature for your example:

isInfixOf :: (Eq [Char]) => [Char] -> [Char] -> Bool

So far so good, huh? Let's see any? No. Let's see isPrefixOf, because it is actually called first and fill the type blanks of any.

isPrefixOf :: (Eq Char) -> [Char] -> [Char] -> Bool

So what isPrefixOf doing? It is comparing, Char by Char, if the first String (or array of Chars) is in the begining of the second String. Now, let's get back to any: any :: (a -> Bool) -> [a] -> Bool. But the function being passed to any, in the example, is isPrefixOf needle, i.e., isPrefixOf "Haskell". Or, in other words, the function begin passed to any, of the type (a -> Bool), is actually (String -> Bool) or, if you prefer, ([Char] -> Bool). Got it? It is about the partial application functions: isPrefixOf is, originally (in our example), 

isPrefixOf :: (Eq Char) -> [Char] -> [Char] -> Bool

However, I am passing, as a function, isPrefixOf "Haskell", so it is fixed as isPrefixOf "Haskell" :: "Haskell" -> [Char] -> Bool, a notation that doesn't exist as you can imagine. Let's make it "real"? Just take away what seems strange: 

isPrefixOf "Haskell" :: [Char] -> Bool

or

isPrefixOf "Haskell" :: String -> Bool

Back, again, to any. As you can imagine, any, now, is 

any :: (String -> Bool) -> [String] -> Bool

or

any :: ([Char] -> Bool) -> [[Char]] -> Bool

Well, I think that now the idea of tails is totally clear for you.

tails "I really like Haskell." :: String -> [String]

or

tails "I really like Haskell." :: [Char] -> [[Char]]

At the end, the execution is:

isInfixOf "Haskell" "I really like Haskell." = 
any (isPrefixOf "Haskell") (tails "I really like Haskell.") = 
any (isPrefixOf "Haskell") [
    "I really like Haskell.",
    " really like Haskell.",
    "really like Haskell.",
    "eallylike Haskell.",
    "ally like Haskell.",
    "lly like Haskell.",
    "ly like Haskell.",
    "y like Haskell.",
    " like Haskell.",
    "like Haskell.",
    "ike Haskell.",
    "ke Haskell.",
    "e Haskell.",
    "Haskell.",
    "Haskell.",
    "askell.",
    "skell.",
    "kell.",
    "ell.",
    "ll.",
    "l.",
    ".",
    ""]

Well, it is easy to very that "Haskell" is prefix of "Haskell.".

I hope I have explained it clearly. :)

Upvotes: 6

Related Questions