[Haskell-cafe] String search algorithms

[Henning Thielemann]

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