🚀 go-pugleaf

In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:

   Following a long and heated discussion on the topic in a local
   newsgroup in which the local ML experts have come up hands empty
   (surprising given this is Edinburgh), I'm looking for fully functional
   ways of solving certain permutation problems which imperative languages
   like C can solve in linear time.  In particular, I'd like to be able to
   compose and invert permutations and generate random ones in linear
   time.  If you don't like mixing "random" and "fully functional", you
   could always ask for a list of random numbers as input. For example, an
   equivalent of this C function would be the best part of a solution:

Use version arrays. They are an implementation of functional vectors,
and the kind of update that happens in an imperative algorithm can be
carried out in constant time. I think every functional language should
provide them, either as the default implementation of a vector, or,
at least, as another datatype. In SML, you can hack them yourself,
except that the type signature will include some weak types that
needn't be weak.

I doubt that you can do better than "n log n" if all you have is lists
and functional vectors with update by copying.

In general, you don't need special ideas ("do it by sorting") in order
to convert imperative algorithms to functional algorithms with a
logarithmic overhead. Instead, simply use a balanced tree to represent
arrays.  That will give you Theta(log n) time access and "update".

					Thomas.