[Haskell-cafe] Re: Differences in optimisiation with interactive and compiled mo

[Daniel Fischer]

Am Donnerstag, 8. Dezember 2005 19:17 schrieb Branimir Maksimovic:
> From: Henning Thielemann <lemming at henning-thielemann.de>
>
> >To: Branimir Maksimovic <bmaxa at hotmail.com>
> >CC: haskell-cafe at haskell.org
> >Subject: Re: [Haskell-cafe] Differences in optimisiation with interactive
> >and compiled mode
> >Date: Thu, 8 Dec 2005 18:38:45 +0100 (MET)
> >
> >On Thu, 8 Dec 2005, Branimir Maksimovic wrote:
> > > program performs search replace on a String
> >
> >http://www.haskell.org/pipermail/haskell-cafe/2005-April/009692.html
>
> This is nice and ellegant but example search replace program runs more
> then 50% faster with my implementation.
>
> Greetings, Bane.
>
That's probably because Lemmih's is polymorphic.
Yesterday evening, I cooked up my own version

srchrep :: String -> String -> String -> String
srchrep "" rp st = st -- or should it rather be cycle rp ?
srchrep sr rp st | sr == rp = st
srchrep sr@(c:cs) rep inp
    = process inp
      where
        process str
	    = case start "" str of
	        Nothing          -> str
		Just (pre, post) -> reverse pre ++ rep ++ process post
	start _ "" = Nothing
	start pre (s:st)
	    | s == c    = cont pre [s] cs st
	    | otherwise = start (s:pre) st
	cont pre _ "" st = Just (pre, st)
	cont _   _ _  "" = Nothing
	cont pre fnd (p:pat) (s:st)
	    | s == p && s == c = abort pre (p:fnd) pat st
	                          `mplus` cont (fnd ++ pre) [s] cs st
	    | s == p           = cont pre (p:fnd) pat st
	    | s == c           = cont (fnd ++ pre) [s] cs st
	    | otherwise        = start (s:fnd ++ pre) st
	abort pre _ "" st      = Just (pre, st)
	abort pre fnd (p:pat) (s:st)
	    | s == p           = abort pre (s:fnd) pat st
	abort _ _ _ _          = Nothing

and today I compared the versions, with Lemmih's type specialized to
String -> ... -> String.

Then Lemmih's is a bit faster than mine (a bit slower, if compiled for 
profiling) which is still a bit faster than yours (and, profiling, yours is 
significantly slower than the others.

Cheers, Daniel