[Haskell-cafe] Text search

[Scott Turner]

On 2005 May 16 Monday 08:00, Gracjan Polak wrote:
> Ketil Malde wrote:
>  > While the result isn't exactly the same, I suspect
>  > using isPrefixOf and tails would be more efficient.
>
> I need the data before and including my needle.

When the haystack gets large, the beautiful
   find (isSuffixOf "needle") (inits "haystack")
is quite inefficient where it uses isSuffixOf searching longer and longer 
strings.

You can get efficiency, the desired data, and deal with infinite strings by 
using a function that is like 'inits' but which returns the initial strings 
reversed.

   reversed_inits = scanl (flip (:)) ""
   find (isPrefixOf (reverse "needle")) (reversed_inits "haystack")