challenge: implement the max function

[Andrei Alexandrescu (See Website For Email)]

Andrei Alexandrescu (See Website For Email) wrote:
> Here's a simple challenge: implement the max function. Requirements:
> 
> a) generic
> b) efficient
> c) preserve lvalueness when possible such that one can write e.g.
> 
> max(arr[0], arr[1]) *= 0.9;
> 
> d) should accept two or more arguments
> e) should return the "smartest" type, e.g. max of an unsigned int and 
> unsigned long should return unsigned long
> f) short and easy to understand
> 
> I don't think it's possible to implement the function to the spec in 
> current D, so designs are allowed to invent new features, as long as 
> they define them thoroughly.

Thanks to all for the great replies. I am glad there is consensus that 
max is a good exercise to test a language's expressive power.

Below is an implementation of max that uses some in-design language 
features.

template max
{
private:
   template maxtype(storageof(T1) T1, storageof(T2) T2)
   {
     static if (storageof(T1) T1 == storageof(T2) T2)
       alias storageof(T1) T1 maxtype;
     else
       static if (std.is_num!(T1) && std.is_num!(T2))
         static if (T2.max > T1.max)
           alias T2 maxtype;
         else
           alias T1 maxtype;
       else
         alias typeof(true ? T1 : T2) maxtype;
   }
   maxtype(storageof(T1) T1, storageof(T2) T2)
   max2(T1, T2)(storageof(T1) T1 lhs, storageof(T2) T2 rhs)
   {
     if (rhs > lhs) return rhs;
     return lhs;
   }
public:
   alias std.vararg_reduce!(max2) max;
}

A good amount of explanations is in order.

* First off, specifying storageof(T) T as the type of a function 
argument means that the compiler will deduce the storage class of the 
actual argument: if the argument is an lvalue, inout will be deduced.

* The maxtype template calculates the "best" type for maximum of two 
numbers in the obvious manner. It is clear how the code can be adapted 
for min. Given that the storage classes are being passed to maxtype, 
they will "stick".

(Aside: the "storageof(T) T" notation is Walter's. My preference was "S 
T" where S is bound to an independent symbol. I couldn't manage to 
convince Walter. One other idea that Walter had was the notation "$T", 
thus restoring some face for the wasted symbol "$".)

* A minor point is that the code assumes a future feature of D: if a 
template only defines a public member and that member is homonym with 
the template name, that member gets automatically promoted as a synonim 
for the template name. (This is a relaxation of the existing rule.)

* The weirdest part is that max never deals with varargs. That is the 
job of the std.varargs_reduce metafunction. std.varargs_reduce is so 
useful, it will be part of the standard library. It takes a function of 
two arguments and defines a vararg function that applies the 
two-argument function repeatedly to accommodate multiple arguments. For 
example, std.varargs_reduce!(max2) defines a vararg template function 
that, when applied to three arguments, will apply max2(max2(a, b), c).

std.varargs_reduce is a static version of the well-known reduce 
primitive found in functional languages. For background on functional 
reduce, see e.g.:

http://www.joelonsoftware.com/items/2006/08/01.html

There is little surprise what the next challenge will be :o). But I will 
confine that to a distinct post.


Andrei