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

4

私の提案は、編集する文字列を処理するときに、多少異なる中間データ構造を使用することです。を使用するソリューションを次に示しますtry。

予選

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

トライ

以下は、試行の単純なデータ型です。

data Trie = Trie (Maybe String) (Map Char 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)

マッチング

試行を使用すると、一致は、試行をトラバースしながら入力文字列を再帰することになります。一致が見つかると、対応する置換値が入力文字列の残りの部分と一緒に返されます (さらに置換できるようにするため)。

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)

ご覧のとおり、「トリッキー」と呼ばれる部分は、2 つのリスト引数を「圧縮」することで簡単に実現できます。

例

以下は簡単な例です ( 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 に答える