Replacing strings with strings from a list

Question

I am trying to write a function that accepts a list of search words, a list of replacement words, and a string in which they will be used.

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

The tricky part is that if the appropriate search query is n'th, then the nth replacement word should be used. In addition, when a replacement word was used, it should not be replaced by another replacement word if it is in fact the search word itself. I already wrote such functions for

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

and

 replace' :: String -> [String] -> String -> String: replace' xy [] = [] replace' x [] (z:zs) = [] replace' xy (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' xy zs) 

I just don’t know how to start with this replaceList tho function, the only thing that may be useful that I have found so far is a function that replaces the nth element in the list. But I can’t figure out how to use it in this case:

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

Ok, hope one of you can help me! Thanks in advance:)

Answer 1

I would suggest a different type than

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

What happens if you call

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

the substring "two" will be found, but there is no replacement for it.

Use more likely

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

so that you guarantee that there are always as many replacement strings as there are patterns you are looking for.

A simple implementation can then use

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

from Data.List to check if any of the provided templates is a prefix of the remaining input,

 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 

This simple solution is not very efficient - it will require a more complex algorithm - and it does not detect whether one of the patterns to be replaced is the prefix of the other, so if a shorter pattern precedes a longer one in the list, the longer pattern never will be used even if it will. This can be solved by sorting the list of substitutions, for example, descending in lexicographic order before calling the replace function.

Answer 2

My suggestion would be to use a slightly different intermediate data structure when processing the string you want to edit. Here is the solution that uses trying .

Qualifiers

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

Is trying

Here is a simple type of attempt:

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

Traffic jams are built from an empty trie and a function to insert key / value bindings into an existing 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) 

Conformity

When trying to match, it comes down to recursion along the input string when passing a trie. When a match is found, the corresponding return value is returned along with the rest of the input string (so that it can be further replaced):

 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 

Note that this function is greedy in the sense that it gives preference to the shortest match if multiple matches are possible. Adapting it so that it selects the longest match (and therefore implements the maximal-munch principle) is not too difficult.

Replacement

Replacing the appearance of search words with their corresponding substitutions can be implemented by searching for a match in the input line: if a match is found, the replacement is placed in the output line, and we continue processing with the unsurpassed part of the line. If no match is found, we save the initial input line and start from the tail .

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

Putting it all together

Your required listReplace function listReplace now almost trivial:

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

As you can see, the part that you call “complex” is easily implemented by “zipping” two list arguments.

Example

Here is a simple example (inspired by 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"