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

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.

Hello Gracjan, Monday, May 16, 2005, 4:00:33 PM, you wrote: GP> > Unless you have very repetitive data and/or tiny alphabet, it is GP> > actually quite efficient, as the expected length of prefixes that need GP> > to be checked before a mismatch can be determined is small. GP> > GP> > At least, I was unable to beat it with my (feeble attempts at) BM or GP> > KMP implementations. if you really need KMP, you can find it at http://haskell.org/hawiki/RunTimeCompilation

find (isSuffixOf "needle") (inits "haystack")

find (isPrefixOf "needle") (tails "haystack") if you need an index - add it with zip: find (isPrefixOf "needle".snd) (zip [0..] (tails "haystack")) -- Best regards, Bulat mailto:bulatz@HotPOP.com