On Tue, 8 Oct 2002 09:14:26 -0400
David Roundy
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.