[Haskell-cafe] Re: Substring replacements (was: Differences inoptimisiation

[Daniel Fischer]

Unfortunately:
Prelude SearchRep> searchReplace "aabaabba" "iii" "aabaabaabbaa"
"aabaabaabb"
Prelude SearchRep> searchReplace "abaaba" "-" "abaaabaaba"
"abaaabaab"

Seemingly, your algorithm assumes that the last component of the 
result of search'' is the beginning of the searched for pattern reversed -- 
which needn't be.
One comment on style (I like it in general):
IMHO, the use of nested pairs and combinations of fst, snd is not very 
readable, using triples/quadruples and providing your own accessor-functions 
(e.g. fst3, thd4) would improve that -- it might have an impact on 
performance, though, that would require a test or an answer from somebody 
more knowledgeable. And -- I'm not sure whether that is indeed so -- if you 
have an argument pattern (x:xs) which may be directly returned, as in

fun (x:xs) | even x     = ([x],xs)
               | otherwise = ([],x:xs)

the list would have to be reconstructed from its head and tail, which could be 
avoided by using an as-pattern

fun xxs@(x:xs)
    | even x      = ([x],xs)
    | otherwise  = ([],xxs),
however, that wouldn't be significant unless it happens really often and the 
compiler might optimise it away anyway.

And on my test, yesterday, Tomasz' version took 40s, my first 45s, Henning's 
77s and yours 170s, Bulat's beat them all with 29s, your version from below 
took less than 1s, but if we took a search pattern like above, it wouldn't do 
the correct replacements.

Cheers,
Daniel

Am Sonntag, 11. Dezember 2005 10:08 schrieben Sie:
> From: "Branimir Maksimovic" <bmaxa at hotmail.com>
>
> >To: bmaxa at hotmail.com, daniel.is.fischer at web.de
> >CC: Haskell-Cafe at haskell.org
> >Subject: RE: [Haskell-cafe] RE: Substring replacements (was: Differences
> >inoptimisiation Date: Sun, 11 Dec 2005 07:29:46 +0000
> >
> >
> >I've found one remaining bug, and this is corrected version.
>
> Ah, I've forgot to include important optimisation, and patched around
> something
> else :)
> No wonder it was slow with normal test:
> ---------------------------------------------------------------------------
>---- searchReplace :: String->String->String -> String
> searchReplace sr rp xs = searchr sr rp xs ""
>    where
>     searchr :: String->String->String->String -> String
>     searchr [] _ xs _  = xs
>     searchr _ _ [] _  = []
>     searchr sr rp xs rollBack
>
>                  | fst $ fst $ fnd rollBack = rp
>
>                                       ++ searchr sr rp (snd $ snd $ fst $
> fnd rollBack )
>                                                        ( snd $ fnd
> rollBack)
>
>                  | otherwise = reverse ((fst $ snd $ fst $ fnd rollBack) ++
>
> rollBack)
>                                ++ searchr sr rp (snd $ snd $ fst $ fnd
> rollBack)
>                                                 ( snd $ fnd rollBack)
>                 where fnd  = searchr' sr xs ""
>
>     searchr' :: String->String->String->String ->
> ((Bool,(String,String)),String)
>     searchr' (sr:srs) xs fndSoFar rollBack =
>                            searchr'' (drop (length rollBack) (sr:srs)) xs
> fndSoFar
>                                      (False,False,"") sr
>
>     searchr'' :: String->String->String->(Bool,Bool,String)->Char
>              -> ((Bool,(String,String)),String)
>     searchr'' [] xs fnd _ _  = ((True,(fnd,xs)),"")
>     searchr'' _ [] fnd (_,_,rollBack) _ = ((False,(fnd,[])),rollBack)
>     searchr'' (sr:srs) (x:xs) fndSoFar (cnt,f,rollBack) s
>
>       | sr == x = if cnt && (f || s == x)
>
>                      then searchr'' srs xs fndSoFar (True,True,x:rollBack)
> s else searchr'' srs xs (x:fndSoFar) (True,False,"") s
>
>       | otherwise = if not f
>
>                        then if s == x
>                                then ((False,(fndSoFar,x:xs)),"")
>                                else ((False,searchr''' s xs
> (x:fndSoFar)),"")
>                        else ((False,(fndSoFar, x:xs)),rollBack)
>
>     searchr''' :: Char->String->String -> (String,String)
>     searchr''' sr [] fndSoFar = (fndSoFar,[])
>     searchr''' sr (x:xs) fndSoFar | sr/=x = searchr''' sr xs (x:fndSoFar)
>
>                              | otherwise = (fndSoFar,x:xs)
>
> ---------------------------------------------------------------------------
>----
>
> _________________________________________________________________
> Don't just search. Find. Check out the new MSN Search!
> http://search.msn.com/