[Haskell-cafe] Newbie: Replacing substring?
dokondr at gmail.com
Wed Jul 23 09:33:20 EDT 2008
Your algoritm is more simple and so it is better, I agree.
My algorithm is different and consists of two steps:
1) Split source string into a list of chunks not containing substring to be
2) Concatenate chunks inserting new substring in between chuncks.
With this approach I get a 'bonus' function of spliting string into chunks
Tue Jul 22 16:38:53 EDT 2008 **Ronald Guida* oddron at
If I want to replace a substring in a string, then I would search my
string left to right, looking for any occurrence of the substring. If
I find such an occurrence, I would replace it and continue searching
from immediately after the replacement. This algorithm can be
directly expressed in Haskell. More efficient algorithms do exist.
replaceStr :: String -> String -> String -> String
replaceStr  old new = 
replaceStr str old new = loop str
loop  = 
loop str =
let (prefix, rest) = splitAt n str
if old == prefix -- found an occurrence?
then new ++ loop rest -- yes: replace it
else head str : loop (tail str) -- no: keep looking
n = length old
On Tue, Jul 22, 2008 at 8:21 PM, Dmitri O.Kondratiev <dokondr at gmail.com>
> Roberto thanks!
> Shame on me, to post code without enough testing :(
> Yet, thanks to your comments *I think* I have found the bugs you wrote
> about and now my code works, please see corrected version below.
> Extra substring at the end was a result of using foldr with initial element
> of . I fixed this with foldl and first chunk as its initial element.
> Incomplete substitution in case of duplicate elements in the pattern was a
> bug in my 'takeOut' function that I have also fixed.
> Stiil the problem that I have not yet designed solution for is when a
> substring to replace extends from the end of a string to the next string. In
> other words - first part of substring ends the first string and second part
> of substring starts the second string. My algorithm currently does not
> account for such a case.
> On the side: The more I use Haskell - the more I like it ! It helps me
> think about the problem I solve much more clearly then when I use imperative
> Corrected code:
> -- replace all occurances of "123" with "58" in a string:
> test = replStr "abc123def123gh123ikl" "123" "58"
> In a string replace all occurances of an 'old' substring with a 'new'
> replStr str old new = foldl ((\newSub before after -> before ++ newSub ++
> after) new) firstChunk otherChunks
> where chunks = splitStr str old
> firstChunk = head chunks
> otherChunks = tail chunks
> Split string into a list of chunks.
> Chunks are substrings located in a string between 'sub' substrings
> splitStr str sub = mkChunkLst str sub 
> -- mkChunkLst 'src string' 'substr-to-extract' 'list of chunks'
> -- makes list of chunks located between 'substr-to-extract' pieces in
> src string
> mkChunkLst  _ chunkLst = chunkLst
> mkChunkLst str sub chunkLst = mkChunkLst after sub (chunkLst ++
> (chunk, _, after) = takeOut str sub  
> Take out substring from a string.
> String is divided into:
> "before substr" ++ "match" ++ "after substr"
> where 'match' is substring to split out
> takeOut after  before match = (before, match, after)
> takeOut  _ before match = (before, match, )
> takeOut (x:xs) (y:ys) before match
> | x == y = takeOut xs ys before (match ++ [x])
> | otherwise = takeOut xs (y:ys) (before ++ [x]) 
> On Tue, Jul 22, 2008 at 7:39 PM, Roberto Zunino <zunino at di.unipi.it>
>> Dmitri O.Kondratiev wrote:
>>> I wrote my own version, please criticize:
>>> -- replace all occurances of "123" with "58" in a string:
>>> test = replStr "abc123def123gh123ikl" "123" "58"
>> This is a tricky problem: first of all, you fail your own test! ;-)
>> *Main> test
>> (Note the extra 58 at the end.)
>> Other common pitfalls:
>> *Main> replStr "abc1123def" "123" "58"
>> (extra 1 ?)
>> *Main> replStr "abc12123def" "123" "58"
>> (extra 12 ?)
>> A useful function from Data.List: stripPrefix
>> (Of course, there are more efficient string match algorithms)
> Dmitri O. Kondratiev
> dokondr at gmail.com
Dmitri O. Kondratiev
dokondr at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe