<div dir="ltr">Ronald,<br>Your algoritm is more simple and so it is better, I agree.<br>My algorithm is different and consists of two steps: <br>1) Split source string into a list of chunks not containing substring to be replaced.<br>
2) Concatenate chunks inserting new substring in between chuncks.<br><br>With this approach I get a &#39;bonus&#39; function of spliting string into chunks :)<br><i><br><br>Tue Jul 22 16:38:53 EDT 2008 </i><b>Ronald Guida</b> 
    <a href="mailto:haskell-cafe%40haskell.org?Subject=%5BHaskell-cafe%5D%20Newbie%3A%20Replacing%20substring%3F&amp;In-Reply-To=53396d9e0807220921o74630a51ub435420f37f21bf9%40mail.gmail.com" title="[Haskell-cafe] Newbie: Replacing substring?">oddron at gmail.com</a> wrote:<br>

    <i><br></i><pre>If I want to replace a substring in a string, then I would search my<br>string left to right, looking for any occurrence of the substring.  If<br>I find such an occurrence, I would replace it and continue searching<br>
from immediately after the replacement.  This algorithm can be<br>directly expressed in Haskell.  More efficient algorithms do exist.<br><br>replaceStr :: String -&gt; String -&gt; String -&gt; String<br>replaceStr [] old new = []<br>
replaceStr str old new = loop str<br>  where<br>    loop [] = []<br>    loop str =<br>      let (prefix, rest) = splitAt n str<br>      in<br>        if old == prefix                -- found an occurrence?<br>        then new ++ loop rest           -- yes: replace it<br>
        else head str : loop (tail str) -- no: keep looking<br>    n = length old<br></pre><br><br><div class="gmail_quote">On Tue, Jul 22, 2008 at 8:21 PM, Dmitri O.Kondratiev &lt;<a href="mailto:dokondr@gmail.com">dokondr@gmail.com</a>&gt; wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div dir="ltr">Roberto thanks!<br>Shame on me, to post code without enough testing :(<br>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. <br>

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.<br>Incomplete substitution in case of duplicate elements in the pattern was a bug in my &#39;takeOut&#39; function that I have also fixed.<br>

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.<br>

<br>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.<br><br>Corrected code:<div class="Ih2E3d"><br><br>-- replace all occurances of &quot;123&quot; with &quot;58&quot; in a string:<br>

test = replStr &quot;abc123def123gh123ikl&quot; &quot;123&quot; &quot;58&quot;<br><br></div><div class="Ih2E3d">{--<br>In a string replace all occurances of an &#39;old&#39; substring with a &#39;new&#39; substring<br>--}<br>
</div>replStr str old new = foldl ((\newSub before after -&gt; before ++ newSub ++ after) new) firstChunk otherChunks<div class="Ih2E3d"><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; where chunks = splitStr str old<br></div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; firstChunk = head chunks<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; otherChunks = tail chunks<div class="Ih2E3d"><br>{--<br>Split string into a list of chunks. <br>
Chunks are substrings located in a string between &#39;sub&#39; substrings <br>
--}<br>splitStr str sub = mkChunkLst str sub []<br>&nbsp;&nbsp;&nbsp; where<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; -- mkChunkLst &#39;src string&#39; &#39;substr-to-extract&#39; &#39;list of chunks&#39;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; -- makes list of chunks located between &#39;substr-to-extract&#39; pieces in src string <br>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; mkChunkLst [] _ chunkLst = chunkLst<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; mkChunkLst str sub chunkLst = mkChunkLst after sub (chunkLst ++ [chunk])<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; where <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (chunk, _, after) = takeOut str sub [] []<br><br>{--<br>Take out substring from a string.<br>

String is divided into:<br>&quot;before substr&quot; ++ &quot;match&quot; ++ &quot;after substr&quot;<br>where &#39;match&#39; is substring to split out&nbsp; <br>--}<br><br>takeOut after [] before match = (before, match, after)<br>

takeOut [] _ before match = (before, match, [])<br>takeOut (x:xs) (y:ys) before match<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | x == y = takeOut xs ys before (match ++ [x])<br></div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | otherwise = takeOut xs (y:ys) (before ++ [x]) []<div><div></div>
<div class="Wj3C7c"><br><br><br><br><div class="gmail_quote">
On Tue, Jul 22, 2008 at 7:39 PM, Roberto Zunino &lt;<a href="mailto:zunino@di.unipi.it" target="_blank">zunino@di.unipi.it</a>&gt; wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

<div>Dmitri O.Kondratiev wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I wrote my own version, &nbsp;please criticize:<br>
<br>
-- replace all occurances of &quot;123&quot; with &quot;58&quot; in a string:<br>
test = replStr &quot;abc123def123gh123ikl&quot; &quot;123&quot; &quot;58&quot;<br>
</blockquote>
<br></div>
This is a tricky problem: first of all, you fail your own test! ;-)<br>
<br>
*Main&gt; test<br>
&quot;abc58def58gh58ikl58&quot;<br>
<br>
(Note the extra 58 at the end.)<br>
<br>
Other common pitfalls:<br>
<br>
*Main&gt; replStr &quot;abc1123def&quot; &quot;123&quot; &quot;58&quot;<br>
&quot;abc1158def58&quot;<br>
<br>
(extra 1 ?)<br>
<br>
*Main&gt; replStr &quot;abc12123def&quot; &quot;123&quot; &quot;58&quot;<br>
&quot;abc121258def58&quot;<br>
<br>
(extra 12 ?)<br>
<br>
A useful function from Data.List: stripPrefix<br>
<br>
(Of course, there are more efficient string match algorithms)<br>
<br>
Regards,<br>
Zun.<br>
</blockquote></div><br><br clear="all"><br></div></div><div class="Ih2E3d">-- <br>Dmitri O. Kondratiev<br><a href="mailto:dokondr@gmail.com" target="_blank">dokondr@gmail.com</a><br><a href="http://www.geocities.com/dkondr" target="_blank">http://www.geocities.com/dkondr</a>
</div></div>
</blockquote></div><br><br clear="all"><br>-- <br>Dmitri O. Kondratiev<br><a href="mailto:dokondr@gmail.com">dokondr@gmail.com</a><br><a href="http://www.geocities.com/dkondr">http://www.geocities.com/dkondr</a>
</div>