Haskell:Data.List.isInfixOf函数如何工作？

Question

我一直试图isInfixOf从Data.List模块中理解功能,但无济于事.这是代码:

     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

该any如果列表中的至少一个项目满足条件,则返回true.它的类型是(a -> Bool) -> [a] -> Bool

该isPrefixOf和tails功能的代码是这些:

    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",""]

我已经读过关于curried函数和部分应用函数但我还不能理解它,我也无法理解这个特定函数是如何工作的.如果any将列表而不是列表列表作为参数,它如何工作？

Answer 1

我们可以读isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)为:返回True如果needle isPrefixOf any细分haystack带走的第一要素(即取tails)它.

不清楚吗？让我们尝试另一种方法,使用您的示例.

isInfixOf "Haskell" "I really like Haskell."

给予它String相同[Char],我们为您的示例提供以下签名:

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

到目前为止一切都那么好,对吧？我们来看看any？不,让我们看看isPrefixOf,因为它实际上是先调用并填充类型空白any.

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

那isPrefixOf干嘛呢？据进行比较,Char通过Char,如果第一String(或阵列Char或多个)是在所述第二的开头String.现在,让我们回到any:any :: (a -> Bool) -> [a] -> Bool.但是any,在该示例中传递给的函数是isPrefixOf needle,即isPrefixOf "Haskell".或者,换句话说,函数开始传递给any类型(a -> Bool),实际上(String -> Bool)或者,如果您愿意,([Char] -> Bool).得到它了？它是关于部分应用程序功能:isPrefixOf原来(在我们的例子中),

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

但是,作为一个函数,我正在传递,isPrefixOf "Haskell"所以它被修复为isPrefixOf "Haskell" :: "Haskell" -> [Char] -> Bool,一个不存在的符号,你可以想象.让我们"真实"？带走看似奇怪的东西:

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

要么

isPrefixOf "Haskell" :: String -> Bool

又回来了any.你可以想象any,现在,是

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

要么

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

好吧,我认为现在这个想法tails对你来说是完全清楚的.

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

要么

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

最后,执行是:

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.",
    ".",
    ""]

嗯,这很容易"Haskell"就是前缀"Haskell.".

我希望我已经清楚地解释了它.:)