[Haskell-cafe] Substring replacements

[Branimir Maksimovic]

>From: Daniel Fischer <daniel.is.fischer at web.de>
>To: Haskell-Cafe at haskell.org
>Subject: [Haskell-cafe] Substring replacements
>Date: Mon, 12 Dec 2005 01:14:37 +0100
>
>Okay, I have looked up KMP and implemented it.
>Seems to work -- my first use of QuickCheck, too.
>It's slower than Bulat's and Tomasz' for Branimir's test :-(,
>but really fast for my test.

Strange I got completelly different results:

maxa at MAXA ~/tutorial
$ time srchrep.exe
Working very long
True
Done

real    0m16.407s
user    0m0.015s
sys     0m0.015s

bmaxa at MAXA ~/tutorial
$ ghc -fglasgow-exts  -O2 srchrep.hs --make -o srchrep.exe
Chasing modules from: srchrep.hs
Compiling Main             ( srchrep.hs, srchrep.o )
Linking ...

bmaxa at MAXA ~/tutorial
$ time srchrep.exe
Working:seasearch replace  able seaseasearch baker seasearch charlie
True
Done


real    0m10.156s
user    0m0.015s
sys     0m0.015s

bmaxa at MAXA ~/tutorial
$ time replace1.exe
Working:seasearch replace  able seaseasearch baker seasearch charlie
True
Done


real    0m11.672s
user    0m0.015s
sys     0m0.015s

Now your version is fastest according to my machine, but it is not faster
with your test it's slower in compariton to replace1.

I've corrected my code so it is fastest with your test,still less then a 
second,
but slowest with mine.
Checked with your fail tests and compared results of these 2 tests.
Now should be ok.
I maintan now two lists one for successes and other for failures.
I also prettified code a bit .

searchReplace :: String->String->String -> String
searchReplace sr rp xs = searchr sr rp xs "" ""
   where
    searchr :: String->String->String->String->String -> String
    searchr [] _ xs _ _ =  xs
    searchr _ _ [] _ _  = []
    searchr sr rp xs retBack rollBack
                 | isFound $ fnd rollBack = rp
                                      ++ searchr sr rp (remaining $ fnd 
rollBack )
                                                       ( getRetBack $ fnd 
rollBack)
                                                       ( getRollBack $ fnd 
rollBack)
                 | otherwise = reverse ((processed $ fnd rollBack) ++ 
rollBack)
                               ++ searchr sr rp (remaining $ fnd rollBack)
                                                ( getRetBack $ fnd rollBack)
                                                ( getRollBack $ fnd 
rollBack)
                where fnd  = searchr' sr sr (reverse retBack ++ xs) ""

    isFound = fst . fst
    remaining = snd . snd . fst
    getRollBack = snd . snd
    getRetBack = fst . snd
    processed = fst . snd . fst

    searchr' :: String->String->String->String->String
                -> ((Bool,(String,String)),(String,String))
    searchr' srch@(sr:srs) srch'@(sr':srs') xs fndSoFar rollBack =
                           searchr'' (drop (length rollBack) srch) srch' xs 
fndSoFar
                                     (False,"","") sr

    searchr'' :: String->String->String->String->(Bool,String,String)->Char
             -> ((Bool,(String,String)),(String,String))
    searchr'' [] _ xs fnd _ _  = ((True,(fnd,xs)),("",""))
    searchr'' _ _ [] fnd (_,retBack,rollBack) _ = ((False,(retBack ++ 
rollBack ++ fnd,[])),("",""))
    searchr'' srch@(sr:srs) srch'@(sr':srs') xxs@(x:xs) fndSoFar 
(cnt,retBack,rollBack) s
      | sr == x = if cnt && sr' == x && isEmpty retBack
                     then searchr'' srs srs' xs fndSoFar 
(True,"",x:rollBack) s
                     else if not (isEmpty retBack)  || not (isEmpty 
rollBack)
                             then searchr'' srs srch' xs fndSoFar
                                             (True,(x:rollBack) ++ 
retBack,"") s
                             else searchr'' srs srch' xs (x:fndSoFar) 
(True,"","") s
      | otherwise = if isEmpty rollBack && isEmpty retBack
                       then if s == x
                               then ((False,(fndSoFar,xxs)),("",""))
                               else ((False,searchr''' s xs 
(x:fndSoFar)),("",""))
                       else if sr' == x && isEmpty retBack
                               then ((False,(fndSoFar, xs)), 
(retBack,x:rollBack))
                               else ((False,(fndSoFar, xxs)), 
(retBack,rollBack))


    searchr''' :: Char->String->String -> (String,String)
    searchr''' sr [] fndSoFar = (fndSoFar,[])
    searchr''' sr xxs@(x:xs) fndSoFar | sr/=x = searchr''' sr xs 
(x:fndSoFar)
                             | otherwise = (fndSoFar,xxs)
    isEmpty [] = True
    isEmpty (a:as) = False
-------------------------------------------------------------------------------



Greetings, Bane.

_________________________________________________________________
Express yourself instantly with MSN Messenger! Download today it's FREE! 
http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/