[m-dev.] For review: additions to array.m

[Fergus Henderson]

> +	% array__sort(Array) returns a version of Array sorted
> +	% into ascending order.
> +	%
> +:- func array__sort(array(T)) = array(T).
> +:- mode array__sort(array_di) = array_uo is det.

You should document that this sort is not stable
(and explain what "stable" means in this context).

On 05-Feb-2001, Ralph Becket <rbeck at microsoft.com> wrote:
> +	% array__foldl(Fn, Array, X) is equivalent to
> +	% 	list__foldl(Fn, array__to_list(Array), X)
> +	% but much more efficient.

I suggest s/much more/more/

(Whether it is "much more" will depend on the implementation,
what optimizations are enabled, etc.)

> +	% array__foldr(Fn, Array, X) is equivalent to
> +	% 	list__foldr(Fn, array__to_list(Array), X)
> +	% but much more efficient.

Likewise.

> +:- func array__foldr(func(T1, T2) = T2, array(T1), T2) = T2.
> +:- mode array__foldr(func(in, in) = out is det, array_ui, in) = out is det.
> +:- mode array__foldr(func(in, in) = out is det, in, in) = out is det.
> +:- mode array__foldr(func(in, di) = uo is det, array_ui, di) = uo is det.
> +:- mode array__foldr(func(in, di) = uo is det, in, di) = uo is det.
> +
> +	% array__permutation(A0, A, RS0, RS) permutes the elements in
> +	% A0 given random seed RS0 and returns the permuted array in A
> +	% and the next random seed in RS.
> +	%
> +:- pred array__permutation(array(T), array(T), random__supply, random__supply).
> +:- mode array__permutation(array_di, array_uo, mdi, muo) is det.

I strongly suggest s/array__permutation/array__random_permutation/g

`array__permutation' should be reserved for a procedure which
(depending on the mode) generates all the possible permutations,
similar to `list__perm'.

> +:- pred permutation_2(int, int, int, int, array(T), array(T),
> +		random__supply, random__supply).
> +:- mode permutation_2(in, in, in, in, array_di, array_uo, mdi, muo) is det.
> +
> +permutation_2(I, Lo, Hi, Sz, A0, A, RS0, RS) :-
> +	( if I > Hi then
> +		A  = A0,
> +		RS = RS0
> +	  else
> +	  	random__random(R, RS0, RS1),
> +	  	J   = Lo + (R `rem` Sz),
> +		Tmp = A0 ^ elem(J),
> +		A1  = ((A0
> +				^ elem(J) := A0 ^ elem(I))
> +				^ elem(I) := Tmp),
> +		permutation_2(I + 1, Lo, Hi, Sz, A1, A, RS1, RS)
> +	).

It's worth extracting those into a separate subroutine

	swap_elem(A0, I, J) = A :-
		Tmp = A0 ^ elem(J),
		A1  = ((A0	^ elem(J) := A0 ^ elem(I))
				^ elem(I) := Tmp).

> +    % NOTE: I tried implementing the partial sort (i.e. into
> +    % a totally ordered sequence of unordered subranges of
> +    % e.g. 16 elements) and then applying insertion sort in
> +    % a single pass, but that was a performance disaster.
> +    % Anybody guess why?

Perhaps there was a bug in the partial sort?
If that happens, you can end up doing a full O(N*N) insertion sort.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------