Haskell：Data.List.isInfixOf 函数是如何工作的？

Question

我一直试图理解 Data.List 模块中的 isInfixOf 函数，但没有成功。这是代码：

     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 returns 如果列表中至少有一项满足条件则为真。它的类型是 (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",""]

我读过柯里化函数和部分应用函数，但我还不能理解，我也不能理解这个特定函数是如何工作的。如果 any 将列表而不是列表的列表作为参数，它如何工作？

Answer 1

我们可以将 isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack) 读作： return True if needle isPrefixOf any [=] 的细分26=] 去掉它的第一个元素（即取 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"。或者，换句话说，函数 begin 传递给 any，类型为 (a -> Bool)，实际上是 (String -> Bool)，或者，如果您愿意，也可以是 ([Char] -> Bool)。知道了？它是关于部分应用程序函数的：isPrefixOf 最初（在我们的示例中）是

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

然而，我作为函数传递，isPrefixOf "Haskell"，所以它被固定为isPrefixOf "Haskell" :: "Haskell" -> [Char] -> Bool，一个你能想象的不存在的符号。让我们"real"？把看起来奇怪的东西拿走：

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." 的前缀很容易。

希望我解释清楚了。 :)

Haskell：Data.List.isInfixOf 函数是如何工作的？

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

haskell

functional-programming