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