need help optimizing a function

[Pedro Vasconcelos]

On Tue, 8 Oct 2002 09:14:26 -0400
David Roundy <droundy@jdj5.mit.edu> wrote:

> 
> My only guess is that for some reason it is making an entirely new copy of
> the array each time it recurses, but that doesn't make any sense, 
...

> >>hunt_one_char :: String -> [Int] -> Array Int (Threshold String) ->
> >>                 Array Int (Threshold String)
> >>hunt_one_char c [] th = th
> >>hunt_one_char c (j:js) th =
> >>    case my_bs (Thresh j [c]) th of
> >>    Nothing -> hunt_one_char c js th
> >>    Just k ->
> >>        case th!(k-1) of
> >>        Thresh _ rest ->
> >>            hunt_one_char c js th//[(k,Thresh j (c:rest))]

Yes, I think you're actually copying the array at each recursive invocation when you do the update "th//[..]". The compiler can't guess that the array can be updated in-place.

You could use state-thread arrays rather than ordinary Haskell arrays. State-thread are an extension to H98 standard that is supported by ghc and hugs (at least). The basic idea is to use a monad to encapsulate the code that manipulates memory references/updates in place and guaranties that the references are actually used in a single-threaded way.

Look up the paper entitled "Lazy Functional State Threads" by John Lauchbury and Simon Peyton Jones (it's available for download). Section 3 contains examples with array updates in-place.

Hope this helps,

Pedro Vasconcelos.