时间戳

首页 > 解决方案 > 有没有更好的方法来编写 indexof 函数？

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

问题描述

我在haskell中写了一个indexOf函数。有没有更好的写法？我的第二个问题是在我的函数中，tails 函数是否被懒惰地评估？

以下是我的 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

这按预期工作。

标签： haskell

解决方案

使用 ern 作为第一个参数看起来更习惯patt，通常失败不是用-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 算法[wiki]可能会更好，因为这将导致在O(m + n)中搜索，其中m是模式的长度，n是字符串的长度。当前的方法需要O(m×n)。

我的第二个问题是在我的函数中是tails懒惰地评估函数吗？

tails确实是懒惰评价。然而，瓶颈可能并不tails :: [a] -> [[a]]存在，因为在评估列表上以O(n)tails运行，并且还需要O(n)内存，因为指针是共享的。因此，它并没有真正为每个项目构建一个新列表，它只是每次都指向前一个元素的尾部。tail

推荐阅读