4

我正在尝试编写一个函数，该函数需要一个搜索词列表、一个替换词列表和一个将使用它们的字符串。

listReplace :: [String] -> [String] -> String -> String

棘手的部分是，如果合适的搜索词是第 n 个，那么应该使用第 n 个替换词。此外，当使用了替换词时，如果它实际上是搜索词本身，则不应将其替换为不同的替换词。我已经为

replace :: String -> String -> String -> String:
replace x y [] = []
replace x y (z:zs) = if isPrefixOf x (z:zs) then y ++ replace x y (drop (length x) (z:zs)) else z: (replace x y zs)

和

replace' :: String -> [String] -> String -> String:
replace' x y [] = []
replace' x [] (z:zs) = []
replace' x y (z:zs) = if isPrefixOf x (z:zs) then concat (take 1 y) ++ replace' x  (drop 1 y) (drop (length x) (z:zs)) else z: (replace' x y zs)

我只是不知道如何从这个 replaceList 函数开始，到目前为止，我发现的唯一可能真正有用的是替换列表中第 n 个元素的函数。但我似乎无法弄清楚如何在这种情况下使用它：

replace :: Int -> a -> [a] -> [a]
replace n a  []  = []  
replace 0 a (x:xs) = a : xs
replace n a (x:xs) = x : replace (n-1) a xs

好吧，希望你们中的一个可以帮助我！提前致谢 ：）

4

2 回答 2

7

我会建议一种不同的类型

listReplace :: [String] -> [String] -> String -> String

如果有人打电话会发生什么

listReplace ["one", "two"] ["een"] "I have two problems"

将找到子字符串“two”，但没有提供替代品。

而是使用

listReplace :: [(String, String)] -> String -> String

这样您就可以保证总是有与您搜索的模式一样多的替换字符串。

然后可以使用一个简单的实现

find :: (a -> Bool) -> [a] -> Maybe a

fromData.List检查任何提供的模式是否是剩余输入的前缀，

listReplace _ "" = ""
listReplace replacements string@(c:cs)
    = case find ((`isPrefixOf` string) . fst) replacements of
        Just (pat,rep) -> rep ++ listReplace replacements (drop (length pat) string)
        Nothing -> c : listReplace replacements cs

这种简单的解决方案效率不高——这需要更复杂的算法——并且它不会检测要替换的模式之一是否是另一个模式的前缀，因此如果较短的模式出现在列表中较长的模式之前，即使应该使用较长的模式，也永远不会使用。这可以通过在调用替换函数之前对替换列表进行排序来处理，例如按字典顺序降序。

于 2013-05-07T09:54:03.460 回答
4

我的建议是在处理要编辑的字符串时使用稍微不同的中间数据结构。这是一个使用尝试的解决方案。

预赛

import Data.Map (Map)
import qualified Data.Map as M

尝试

这是一个简单的尝试数据类型：

data Trie = Trie (Maybe String) (Map Char Trie)

Tries 由空 trie 和用于将键/值绑定插入现有 trie 的函数构造：

empty :: Trie
empty =  Trie Nothing M.empty

insert :: String -> String -> Trie               -> Trie
insert    []        val       (Trie _ tries)     =  Trie (Just val) tries
insert    (c : cs)  val       (Trie mbVal tries) =  case M.lookup c tries of
  Nothing   -> Trie mbVal (M.insert c (insert cs val empty) tries)
  Just trie -> Trie mbVal (M.insert c (insert cs val trie)  tries)

匹配

通过尝试，匹配减少为在遍历 trie 时对输入字符串进行递归。当找到匹配项时，将相应的替换值与输入字符串的剩余部分一起返回（以便对其进行进一步的替换）：

match :: Trie ->                 String   -> Maybe (String, String)
match    (Trie (Just val) _    ) s        =  Just (val, s)
match    (Trie Nothing    _    ) []       =  Nothing
match    (Trie Nothing    tries) (c : cs) =  case M.lookup c tries of
  Nothing   -> Nothing
  Just trie -> match trie cs

请注意，这个函数是贪婪的，因为如果可能有多个匹配，它会优先选择最短匹配。调整它以便它选择最长的匹配（并因此实现“最大咀嚼”原则）并不太难。

替代品

可以通过在输入字符串中查找匹配来实现将出现的搜索词替换为相应的替换：如果找到匹配，则将替换放入输出字符串中，然后我们继续处理字符串中未匹配的部分。如果没有找到匹配项，我们保留输入字符串的头部并继续处理尾部。

replace :: Trie -> String -> String
replace    trie =  go
  where
    go []         = []
    go s@(c : cs) = case match trie s of
      Nothing        -> c : go cs
      Just (s', s'') -> s' ++ go s''

把这一切放在一起

您所需的功能listReplace现在几乎是微不足道的：

listReplace :: [String] -> [String] -> String -> String
listReplace    keys        vals     =  replace trie
  where
    trie = foldr ($) empty (zipWith insert keys vals)

如您所见，您称为“棘手”的部分很容易通过“压缩”两个列表参数来实现。

例子

这是一个简单的示例（受L. Peter Deutsch启发）：

> let s = "to err is human; to forgive, divine"
> listReplace ["err", "forgive"] ["iterate", "recurse"] s

"to iterate is human; to recurse, divine"
于 2013-05-07T10:35:01.163 回答