need help optimizing a function

Zdenek Dvorak
Tue, 08 Oct 2002 17:29:56 +0000


> > p.s., I sense your next question is going to be something like "why
> > can't the compiler detect that the array can be updated in place
> > instead of copied" and the answer, from what i can tell, is simply
> > that it doesn't try.
>And one might argue that it should not try

and the other answer is that the result would not be worth the effort
usually. The idea seems nice, but the laziness is where I see the problem;
see the following code:

do_something::Array Int Int->(Array Int Int, Result)
do_something a = (a'',res)
  a' = a // [(summon_index, summon_int)]
  w = a' ! 4
  res = do_some_work w
  a'' = a' // [(summon_other_index, summon_other_int)]

Seems like nice candidate for update-in-place? But the problem is, that
in general you cannot say when w will be evaluated -- so you simply cannot
destroy a' before then.

This is also reason why DiffArray (from hslibs) does not have to be very 
unless you have a good control on when things are evaluated -- it may (and 
also happened to me) have quadratic behavior in cases like this.

To solve this, '!' would have to produce a new array too; but then you must
pass it everywhere and effectively you are doing the work monads would do
for you.

So in general you must choose -- either your programs will be nice and 
but you will have to use structures with (some kind of) logarithmic slowdown
(FiniteMap, Trie), or some of their parts will be embedded in monads.

Zdenek Dvorak

MSN Photos is the easiest way to share and print your photos: