[Haskell-cafe] Text search

Scott Turner p.turner at computer.org
Tue May 17 17:23:20 EDT 2005


On 2005 May 17 Tuesday 11:44, Donn Cave wrote:
> > You can get efficiency, the desired data, and deal with infinite strings.
> >    reversed_inits = scanl (flip (:)) ""
> >    find (isPrefixOf (reverse "needle")) (reversed_inits "haystack")

With "get efficiency", I was comparing this program which is linear time and 
constant space in the amount of the haystack searched, to an earlier 
suggestion which was quadratic time and linear space.
>
> Is it practical to process a serious volume of data as [Char]?

As for your question, GHC _can_ handle a serious volume of [Char]. I don't 
know how competitive the efficiency is.


More information about the Haskell-Cafe mailing list