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"
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/