🚀 go-pugleaf

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:

/* 
 * source and result are arrays of integers of length n.
 * For random permutations, source should be made up of a lot of
 * random numbers each between 0 and n-1.
 */

void randpermute(source, result, n)
int *source, *result, n;
{
	int i, tmp;
	
	for(i = 0; i < n; i++)
		result[i] = i;
	for(i = 0; i < n; i++) {
		tmp = result[i];
		result[i] = result[source[i]];
		result[source[i]] = tmp;
	}
}

The best solution so far take O(n log n) time and involves sorting.  I
believe that Haskell has a way of offering read-only arrays accessible in
O(1) time and that might go some way towards a solution (for example,
they solve composition pretty neatly).

Be warned that many of the notables of this department have found banana
peels here...
  __                                _____
\/ o\ Paul Crowley pdc@dcs.ed.ac.uk \\ //
/\__/ "I'm the boy without a soul."  \X/