string - 检查子字符串是否在 Haskell 中的另一个字符串中的函数

Question

我需要编写一个函数，通过使用列表推导来检查子字符串是否在另一个字符串中。
我正在使用 drop从要使用的字符串创建字符串列表 isPrefixOf将创建的字符串列表与子字符串进行比较。
这是我的代码:

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

但是，我收到此错误:

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)

我想了解为什么我会收到此错误以及如何修复它。我假设这是因为我给 isPrefixOf 一个列表 [[a]] 和我的函数检查 str 并且它不接受？

Answer 1

IsPrefixOf :: Eq a => [a] -> [a] -> Bool 期望两个相同类型的列表(并且该类型应该是 Eq 类型类的成员)，所以两个 String例如，由于 String是 Char 的列表s。
但是，您提供了 String ( substr )，以及 String 的列表s( check str 的类型为 [String] )。因此，这不会进行类型检查。此外使用 drop多次会使 check str在 O(n2) 中运行，效率不高。
您可以使用 any :: Foldable f => (a -> Bool) -> f a -> Bool 检查可折叠中的任何元素是否满足谓词，例如列表。我们还可以利用 tails :: [a] -> [[a]] 以更有效的方式获取列表的所有尾部(包括完整列表):

import Data.List(isPrefixOf, tails)

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

我们可以进一步推广它以处理任何类型的列表 a那是 Eq 的成员类型类:

import Data.List(isPrefixOf, tails)

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

我们也可以利用 flip :: (a -> b -> c) -> b -> a -> c 使函数无点。和 (.) :: (b -> c) -> (a -> b) -> a -> c :

import Data.List(isPrefixOf, tails)

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