[Haskell-cafe] Text search

Scott Turner p.turner at computer.org
Mon May 16 10:12:21 EDT 2005

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 

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_inits = scanl (flip (:)) ""
   find (isPrefixOf (reverse "needle")) (reversed_inits "haystack")

More information about the Haskell-Cafe mailing list