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

[Fergus Henderson]

On 31-Jan-2001, Ralph Becket <rbeck at microsoft.com> wrote:
> Assuming this is accepted, I plan to change list__sort and
> list__sort_and_remove_dups to use array__sort rather than
> list__merge_sort.
> 
> Array based quicksorting is substantially less costly in
> terms of space(O(n) vs O(n log n)) and informal testing 
> shows it to be about 10 times faster in practice.

That sounds very good.

How do they compare when sorting already-sorted lists?

> Added sort and fold functionality to array.m
> 
> library/array.m:
> 	Added array__sort/1, implemented using quicksort.
> 	Added array__fold[lr]/3.
> 	Changed array__to_list/1 to use foldr_0/3 (the core of
> 	array__foldr) since this is shorter and tail recursive.

It would be nice to also provide versions which are
parameterized on an ordering predicate, like list__sort/3.

> Index: array.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/library/array.m,v
> retrieving revision 1.82
> diff -u -r1.82 array.m
> --- array.m	2001/01/12 14:08:46	1.82
> +++ array.m	2001/01/31 09:55:57
> @@ -287,6 +287,31 @@
>  :- func array_compare(array(T), array(T)) = comparison_result.
>  :- mode array_compare(in, in) = out is det.
>  
> +	% 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.
> +
> +:- pragma type_spec(array__sort/1, T = int).
> +:- pragma type_spec(array__sort/1, T = string).

Those are implementation details, really;
I don't think they should go in the interface.

Why did you choose to specialize those types?
You should document the reason.

> +	% array__foldl(Fn, Array, X) is equivalent to
> +	% 	list__foldl(Fn, array__to_list(Array), X)
> +	% but much more efficient.
> +	%
> +:- func array__foldl(func(T1, T2) = T2, array(T1), T2) = T2.
> +:- mode array__foldl(func(in, in) = out is det, array_ui, in) = out is det.
> +:- mode array__foldl(func(in, in) = out is det, in, in) = out is det.

Hmm, it might be nice to also provide

	:- mode array__foldl(func(in, di) = uo is det, in, di) = uo is det.

or something like that.  Likewise for foldr.

Apart from that, this looks good.

-- 
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
--------------------------------------------------------------------------