haskell - 有没有更好的方法来编写indexof函数？

Question

我在haskell中写了一个indexOf函数。有没有更好的写法呢？我的第二个问题是在我的函数中，尾部函数是否被延迟求值？

以下是我的indexof函数

import Data.List
indexof :: String -> String -> Int
indexof lat patt = helper (tails lat) 0
        where helper [] _  = -1
              helper (x:xs) a = if prefix x patt then a else helper xs (a + 1)

prefix :: String -> String -> Bool
prefix _ [] = True
prefix [] _ = False
prefix (x:xs) (y:ys)  = if x == y then prefix xs ys else False

这按预期工作。

Answer 1

使用pattern作为第一个参数看起来更惯用，通常失败不是通过-1或其他值解决的，而是通过使用Nothing来解决，因此使用Maybe Int 作为返回类型。

我们可以在这里使用 foldr 模式，这使它更加优雅，并且 Data.List 有一个 isPrefixOf :: Eq a => [a] -> [a] -> Bool :

import Data.List(isPrefixOf, tails)

indexof :: Eq a => [a] -> [a] -> Maybe Int
indexof patt = foldr helper Nothing . tails
    where helper cur rec | isPrefixOf patt cur = Just 0
                         | otherwise = fmap (1+) rec

但是，最好实现 Knuth-Morris-Pratt algorithm [wiki]因为这将导致搜索 O(m + n)，其中 m 是模式的长度，n 是字符串的长度。当前的方法需要O(m×n)。

My second question is In my function is the tails function lazily evaluated?

tails 确实是延迟评估的。瓶颈可能不在 tails :: [a] -> [[a]]但是，由于 tails 在计算列表上的运行时间为 O(n)，并且也需要 O(n) 内存，因为 >tail 指针是共享的。因此，它并没有真正为每个项目构建一个新列表，它只是每次都指向前一个元素的尾部。