Tony wrote:
> Hello All,
> I'm stumped by a problem that seems to me to be hard to
> do efficiently in Haskell or any 'pure' functional language. That is,
> making an inverse index.
>
> The particular problem stems from a particularly efficient method of
> string searching (at least it's efficient as an imperative algorithm)
> which involves analysing the pattern string to find out the last
> position in the pattern where each letter of the 'alphabet' appears and
> make an array of such positions indexed on the letters of the alphabet.
> I just cannot see an efficient way of writing this which doesn't create
> more than one version of the array. It appears to need to update the
> array for each occurrence of the letters.
>
> Can anyone think of an efficient method. Monads?
accumArray?
Whic, admittedly, is hard to implement efficiently in a purely functional way.
--
-- Lennart
