[m-dev.] for review: add a new pred to array.m

[Fergus Henderson]

On 30-Mar-1999, Thomas Charles Conway <conway at hydra.cs.mu.oz.au> wrote:
> 
> For anyone to review.
> As suggested by the comments, there may be a (tricky) more efficient
> implementation (same O(), better constant factors/better memory usage).
> If anyone wants to improve the implementation, I'm quite open to
> suggestions.
> --- NEWS	1999/03/24 05:32:17	1.140
> +++ NEWS	1999/03/30 05:38:06
> @@ -39,6 +39,10 @@
>  Changes to the Mercury standard library:
>  ****************************************
>  
> +* We've added a new higher order predicate the array module in the
> +  standard library:
> +	array__map/3.
> +
>  * We've added a new predicate to the Mercury standard library:
>  	bag__count_value/3.

How about just

	* We've added some new predicates to the Mercury standard library:
		bag__count_value/3,
		array__map/3.

?

> +	% array__map(Closure, OldArray, NewArray) applys `Closure' to
> +	% each of the elements of `OldArray' to create `NewArray'.
> +:- pred array__map(pred(T, U), array(T), array(U)).
> +:- mode array__map(pred(in, out) is det, array_di, array_uo) is det.

If you want short names for type variables, I much prefer T1, T2, ...
rather than T, U, ...

Any particular reason why this is a predicate, rather than a function?
The old rationale for using predicates was for debugging with Prolog, 
but that doesn't apply now.

> +	% The current implementation of array__map converts to a list,
> +	% invokes list__map, then converts back to an array representation.
> +	% It would be nicer to be able to do the map on each element
> +	% maintaining the same array skeleton. Unfortunately this is
> +	% tricky since the intermediate arrays have some elements of
> +	% one type, and some of the other.

Yes, that would be tricky -- particularly for the accurate garbage collector
and the debugger.  I don't think it would be worthwhile to try to make them
somehow cope with mixed arrays like this.

So a zero-copy implementation is tricky, in general.
However, it's certainly quite possible to do better than your two-copy
implementation.  A one-copy implementation should be straight-forward, no?

	array__map(Closure, OldArray, NewArray) :-
		( array__semidet_lookup(OldArray, 0, Elem) ->
			array__size(OldArray, Size),
			array__init(Size, Elem, NewArray0),
			array__map_2(0, Size, Closure, OldArray,
				NewArray0, NewArray)
		;
			array__make_empty_array(NewArray)
		).

	array__map_2(N, Size, Closure, OldArray, NewArray0, NewArray) :-
		( N >= Size ->
			NewArray = NewArray0
		;
			array__lookup(OldArray, N, OldElem),
			Closure(OldElem, NewElem),
			array__set(NewArray0, N, NewElem, NewArray1),
			array__map_2(N + 1, Size, Closure, OldArray,
				NewArray1, NewArray)
		).

If you want to get tricky, you could special-case this for the case
where the two types are the same, using a dynamic type test:

	array__map(Closure, OldArray, NewArray) :-
		( univ_to_type(univ(OldArray), NewArray0) ->
			array_size(NewArray0, Size),
			array__map_3(0, Size, Closure, NewArray0, NewArray)
		; array__semidet_lookup(OldArray, 0, Elem) ->
			array__size(OldArray, Size),
			array__init(Size, Elem, NewArray0),
			array__map_2(0, Size, Closure, OldArray,
				NewArray0, NewArray)
		;
			array__make_empty_array(NewArray)
		).

	% this is the same as before
	array__map_2(Closure, OldArray, N, Size, NewArray0, NewArray) :-
		( N = Size ->
			NewArray = NewArray0
		;
			array__lookup(OldArray, N, OldElem),
			Closure(OldElem, NewElem),
			array__set(NewArray0, N, NewElem, NewArray1),
			array__map_2(N + 1, Size, Closure, OldArray,
				NewArray1, NewArray)
		).

	% this is the same as array__map_2,
	% except it uses NewArray0 instead of OldArray
	array__map_3(Closure, N, Size, NewArray0, NewArray) :-
		( N = Size ->
			NewArray = NewArray0
		;
			array__lookup(NewArray0, N, OldElem),
			Closure(OldElem, NewElem),
			array__set(NewArray0, N, NewElem, NewArray1),
			array__map_3(N + 1, Size, Closure, NewArray1, NewArray)
		).

If you want to be *really* tricky, you could try using unsafe_promise_unique
to combine array__map_2 and array__map_3.  That is, replace the call
to array__map_3 with

			array__map_2(0, Size, Closure, NewArray0,
				promise_unique(NewArray0), NewArray)

and then you can delete the code for array__map_3.
The call to promise_unique is a lie, but it should be safe, because
each element of the old array won't be reused until after its last use.
However, this is probably being *too* tricky ;-)

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.