[Haskell-cafe] Newbie: Replacing substring?

[Dmitri O.Kondratiev]

Ronald,
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
replaced.
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
gmail.com<haskell-cafe%40haskell.org?Subject=%5BHaskell-cafe%5D%20Newbie%3A%20Replacing%20substring%3F&In-Reply-To=53396d9e0807220921o74630a51ub435420f37f21bf9%40mail.gmail.com>wrote:
*
*

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
  where
    loop [] = []
    loop str =
      let (prefix, rest) = splitAt n str
      in
        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>
wrote:

> 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
> language.
>
> 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'
> substring
> --}
> 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 []
>     where
>       -- 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])
>           where
>             (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>
> wrote:
>
>> 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
>> "abc58def58gh58ikl58"
>>
>> (Note the extra 58 at the end.)
>>
>> Other common pitfalls:
>>
>> *Main> replStr "abc1123def" "123" "58"
>> "abc1158def58"
>>
>> (extra 1 ?)
>>
>> *Main> replStr "abc12123def" "123" "58"
>> "abc121258def58"
>>
>> (extra 12 ?)
>>
>> A useful function from Data.List: stripPrefix
>>
>> (Of course, there are more efficient string match algorithms)
>>
>> Regards,
>> Zun.
>>
>
>
>
> --
> Dmitri O. Kondratiev
> dokondr at gmail.com
> http://www.geocities.com/dkondr
>



-- 
Dmitri O. Kondratiev
dokondr at gmail.com
http://www.geocities.com/dkondr
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080723/d85887e6/attachment-0001.htm