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

11 Dec 2005

...
From: "Branimir Maksimovic" 
To: bmaxa@hotmail.com, daniel.is.fischer@web.de
CC: Haskell-Cafe@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/