std.array suggestion

[Sean Kelly]

Oskar Linde wrote:
> Hello,
> 
> With the new IFTI support I have been looking at ways of upgrading the 
> standard library with new and more generic functions. What follows is my 
> suggestions for functions to be added to std.array. I have implemented 
> all of them and the current (0.149) limited IFTI-support is enough to 
> support them. That being said, I wish to hold off making a source code 
> submission until a) I get review comments on the suggested function 
> prototypes and b) it is more clear how far D is taking IFTI support 
> (meaning possibly neater implementation).

Just a few quick comments, as I've begun thinking about this for Ares as 
well.

> All functions are designed to be used both as free function and as 
> implicit array methods. Except for the inplace versions, no functions 
> modifies the array.
> 
> The prototype notation is my own. a|b means two alternative types. T is 
> the generic element type. T[] is the array.

To those who are unfamiliar with ITI, it's worth noting that any 
template parameters that cannot be determined implicitly should be 
placed at the beginning of the template parameter list.  Doing so should 
allow this to be possible:

	template func( Ret, Val )
	{
	    Ret func( Val val ) {}
	}
	
	int i;
	char c = func!(char)( i );

This isn't implemented yet, but I suspect it will be soon.

> -----------
> 
> T fold(T[] arr, T init, T delegate|function combiner(T,T));
> 
> Generic array recursion function. combiner is called recursively:
>     return combiner(init,fold(arr[1..$],arr[0],combiner));
> (The actual implementation will of course call the combiner iteratively)
> 
> 
> T max(T[] arr)
> 
> Returns the maximum element in arr as defined by the > operator.
> 
> 
> T min(T[] arr)
> 
> Returns the minimum element in arr as defined by the < operator.

min and max should probably allow a comparison predicate to be supplied 
as well.  Thus the declarations would be something like this:

T min(T[] arr, P pred = &less!(T));

I'm also hoping the above syntax will actually work, and that P will 
resolve to being a function pointer by default.

> T sum(T[] arr)
> 
> Returns the sum of the element in arr as defined by the + operator.
>
> ptrdiff_t find(T[] arr, T|delegate|function d);
> 
> Returns the index of the first occurence of d or the first true 
> predicate d applied to the elements in order. Returns -1 when no element 
> is found.

I suggest returning size_t instead and using size_t.max in place of -1. 
  The two are basically equivalent, but using size_t offers a bit more 
range in legal array sizes as the flag value occupies the least 
significant bit rather than the most significant.

I also almost suggested adding a "substring" find function, except that 
seems more appropriate for a std.string module.  Have you thought about 
how the two will overlap?  I'm not entirely certain how template 
overloading will work for functions defined in different modules.  In 
fact, if this is indeed a limitation them it might be prudent to put all 
such algorithms in std.array instead of splitting them between std.array 
and std.string (I just thought of this--I had been considering multiple 
modules for overloads in Ares, and I suspect this won't work).

> size_t indexOf(T[] arr, T|delegate|function d);
> 
> Like find, but throws on missing element.
> 
> 
> T[][] split(T[] arr, T|T[]|delegate|function d);
> 
> Split the array arr using a predicate/element/subarray d.
> (obsoletes std.string.split that only works for char[])
> 
> 
> T[] join(T[][] arr, T|T[]|delegate|function separator);
> 
> Join the elements array arr using separator.
> (obsoletes std.string.join that only works for char[])

How do you envision the delegate version being applied?  Is it expected 
to return an element/array for a separator?

> T[] join(T[][] arr);
> 
> Join the array T[][] without separator.
> 
> 
> U[] map(T[] arr, U delegate|function f(T));
> 
> Map the elements of arr over function f, returning an array of the results.
> 
> 
> T[] filter(T[] arr, delegate|function p(T));
> 
> Filters arr over the predicate p, returning array of elements of arr 
> where the predicate is true.
> 
> 
> Possible inplace version of map:
> 
> T[] doMap(T[], T delegate|function f(T));
> 
> ---------
> 
> I would also prefer those over the language built in .sort .reverse:
> 
> T[] sort(T[]);
> T[] stableSort(T[]);
> T[] sort(T[], delegate|function wrongOrder(T,T));
> T[] reverse(T[]);
> 
> 
> With the corresponding inplace versions:
> 
> T[] doSort(T[]);
> T[] doStableSort(T[]);
> T[] doSort(T[], delegate|function wrongOrder(T,T));
> T[] doReverse(T[]);
> 
> ---------
> 
> Is there in general even any interest in adding generic functions to the 
> standard library?

Heck yes.  Many of the functions you've mentioned above were ones I was 
planning to implement.  I also like that you're using delegates as 
predicates, as it makes them far more generic than some of the hardcoded 
versions in Phobos' std.string.  I don't suppose you'd like to submit 
them to Ares as well?  Or please don't object if I end up implementing 
something quite similar :-)


Sean