[Haskell-cafe] String search algorithms

Henning Thielemann lemming at henning-thielemann.de
Mon Apr 25 06:35:31 EDT 2005

On Mon, 25 Apr 2005, Henning Thielemann wrote:

> On Mon, 25 Apr 2005, Bayley, Alistair wrote:
>> I'm a bit puzzled to find no sub-string search in the Haskell libraries
>> (unless there's some neat composition of the existing Data.List functions
>> that I've missed). Google doesn't help much either. I've found a KMP
>> implementation:
>>  http://haskell.org/hawiki/RunTimeCompilation
>> I'm after something that'll report the position of the first occurrence,
>> like Java's String.indexOf().
> List.findIndex (List.isPrefixOf "bla") (List.tails "dfvbdbblaesre")

But I'm curious if you really need the index. Working with indexes on 
lists is quite inefficient. E.g. if you want to replace substrings you 
may want to use this implementation:

replace :: forall a. (Eq a) => [a] -> [a] -> [a] -> [a]
replace src dst =
    foldr (\x xs -> let y=x:xs
                    in  if isPrefixOf src y
                          then dst ++ drop (length src) y
                          else y) []

Prelude Data.List> replace "ocu" "orcu" "hocuspocus"

More information about the Haskell-Cafe mailing list