www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - challenge: implement the max function

reply "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
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.

Looking forward to any takers!


Andrei
Jan 21 2007
next sibling parent reply Xinok <xnknet gmail.com> writes:
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.
 
 Looking forward to any takers!
 
 
 Andrei



template max(T1, T2){
	typeof(T1+T2) max(T1 a, T2 b){ return a > b ? a : b; }
}
Jan 21 2007
parent Deewiant <deewiant.doesnotlike.spam gmail.com> writes:
Xinok wrote:

 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




<snip>

 
 template max(T1, T2){
 	typeof(T1+T2) max(T1 a, T2 b){ return a > b ? a : b; }
 }


Doesn't satisfy requirement C, nor, if I understood it correctly (that the
function should accept any number of parameters >= 2), does it satisfy D. Not
sure about E.

-- 
Remove ".doesnotlike.spam" from the mail address.
Jan 21 2007
prev sibling next sibling parent reply "Lionello Lunesu" <lionello lunesu.remove.com> writes:
"Andrei Alexandrescu (See Website For Email)" 
<SeeWebsiteForEmail erdani.org> wrote in message 
news:45B3B243.2010103 erdani.org...

 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;


...when would that be useful? And, what happens if arr[0]==arr[1] ?

L.
Jan 21 2007
next sibling parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Lionello Lunesu wrote:

 "Andrei Alexandrescu (See Website For Email)" 
 <SeeWebsiteForEmail erdani.org> wrote in message 
 news:45B3B243.2010103 erdani.org...

 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;


 
 ...when would that be useful? And, what happens if arr[0]==arr[1] ?


Can't immediately think up an example of usefulness, but what presumably 
happens if they're equal is that one of them gets reduced by 10% (and 
rounded to the accuracy of typeof(arr[0])).
Jan 21 2007
parent reply "Lionello Lunesu" <lionello lunesu.remove.com> writes:
"Frits van Bommel" <fvbommel REMwOVExCAPSs.nl> wrote in message 
news:ep0j0a$1av2$1 digitaldaemon.com...

 Lionello Lunesu wrote:

 "Andrei Alexandrescu (See Website For Email)" 
 <SeeWebsiteForEmail erdani.org> wrote in message 
 news:45B3B243.2010103 erdani.org...

 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;


 ...when would that be useful? And, what happens if arr[0]==arr[1] ?


 Can't immediately think up an example of usefulness, but what presumably 
 happens if they're equal is that one of them gets reduced by 10% (and 
 rounded to the accuracy of typeof(arr[0])).


Which one? :)
Jan 21 2007
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Lionello Lunesu wrote:

 "Frits van Bommel" <fvbommel REMwOVExCAPSs.nl> wrote in message 
 news:ep0j0a$1av2$1 digitaldaemon.com...

 Lionello Lunesu wrote:

 "Andrei Alexandrescu (See Website For Email)" 
 <SeeWebsiteForEmail erdani.org> wrote in message 
 news:45B3B243.2010103 erdani.org...

 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;


 ...when would that be useful? And, what happens if arr[0]==arr[1] ?


 Can't immediately think up an example of usefulness, but what presumably 
 happens if they're equal is that one of them gets reduced by 10% (and 
 rounded to the accuracy of typeof(arr[0])).


 
 Which one? :)


That would be implementation-dependent.
If you need it to be a specific one, that's an additional requirement. 
So implement the function yourself ;).
But perhaps it doesn't matter?
Or maybe the caller knows it just can't happen?
Jan 21 2007
parent "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
Frits van Bommel wrote:

 Lionello Lunesu wrote:

 "Frits van Bommel" <fvbommel REMwOVExCAPSs.nl> wrote in message 
 news:ep0j0a$1av2$1 digitaldaemon.com...

 Lionello Lunesu wrote:

 "Andrei Alexandrescu (See Website For Email)" 
 <SeeWebsiteForEmail erdani.org> wrote in message 
 news:45B3B243.2010103 erdani.org...

 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;


 ...when would that be useful? And, what happens if arr[0]==arr[1] ?


 Can't immediately think up an example of usefulness, but what 
 presumably happens if they're equal is that one of them gets reduced 
 by 10% (and rounded to the accuracy of typeof(arr[0])).


 Which one? :)


 
 That would be implementation-dependent.
 If you need it to be a specific one, that's an additional requirement. 
 So implement the function yourself ;).
 But perhaps it doesn't matter?
 Or maybe the caller knows it just can't happen?


For conformity purposes, let's just say that in case the two are equal, 
the first should be picked.

Andrei
Jan 21 2007
prev sibling parent "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
Lionello Lunesu wrote:

 "Andrei Alexandrescu (See Website For Email)" 
 <SeeWebsiteForEmail erdani.org> wrote in message 
 news:45B3B243.2010103 erdani.org...

 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;


 
 ...when would that be useful? And, what happens if arr[0]==arr[1] ?


It's useful to implement specs like "amortize the largest of a and b by 
0.9". If they are equal, an arbitrary one of them will be amortized.

More to the point, preserving lvalueness is important for functions with 
different semantics than max; max is a simple enough problem to work on 
the types aspect without getting distracted by its logic.


Andrei
Jan 21 2007
prev sibling next sibling parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
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.



Some first thoughts:

Presumably, (b) is only required when using full optimization options?


I was going to ask "What is the 'smartest type' for the max of long and 
ulong?" but then I thought of the answer: ulong. Since the ulong is 
non-negative, the max of a long an an ulong will always be non-negative 
itself.


(c) & (e) are exclude each other in current D since return values are 
always rvalues, and a forwarding struct goes against requirement (e).

C++-like references won't work even if added, since the return type 
needs to be determined at compile time. This means you can't return an 
ulong& for max(uint, ulong) since if the uint happens to be larger you 
can't create the ulong& return value from the uint parameter.

Adding implicit casts and bending requirement (e) a little to return a 
forwarding struct that implicitly converts to the wanted type is another 
option.
This will probably breaks requirement (f) because of too much required 
operator overloading.
Also, you'll need to perform runtime checks for each operation if there 
were multiple types and you want to preserve lvalue-ness. This will 
likely break requirement (b).
That last objection could perhaps be mitigated by using a forwarding 
class instead of a struct though; runtime checks could then be replaced 
by virtual function calls. If that's efficient enough (b) is preserved.


Overall, I don't think this is possible in any statically typed 
programming language I know. I don't think even a C preprocessor macro 
can fulfill both (c) and (e) unless that "when possible" in (c) means 
"when possible in the language" instead of "when passed lvalues".
Jan 21 2007
parent reply "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
Frits van Bommel wrote:

 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.


 
 
 Some first thoughts:
 
 Presumably, (b) is only required when using full optimization options?


That is correct.


 I was going to ask "What is the 'smartest type' for the max of long and 
 ulong?" but then I thought of the answer: ulong. Since the ulong is 
 non-negative, the max of a long an an ulong will always be non-negative 
 itself.


Exactly right. max makes for a great example in type manipulation 
abilities because it's simple yet gives the type system a good workout.


 (c) & (e) are exclude each other in current D since return values are 
 always rvalues, and a forwarding struct goes against requirement (e).


That's why you are kindly invited to invent the feature(s) that you find 
fit to comply to the spec.


 C++-like references won't work even if added, since the return type 
 needs to be determined at compile time. This means you can't return an 
 ulong& for max(uint, ulong) since if the uint happens to be larger you 
 can't create the ulong& return value from the uint parameter.


True. But read (c) again: there is a "where possible". When the types 
are different, you always return an rvalue. It's not possible to return 
an lvalue, because you don't know statically which argument is larger.


 Adding implicit casts and bending requirement (e) a little to return a 
 forwarding struct that implicitly converts to the wanted type is another 
 option.
 This will probably breaks requirement (f) because of too much required 
 operator overloading.
 Also, you'll need to perform runtime checks for each operation if there 
 were multiple types and you want to preserve lvalue-ness. This will 
 likely break requirement (b).
 That last objection could perhaps be mitigated by using a forwarding 
 class instead of a struct though; runtime checks could then be replaced 
 by virtual function calls. If that's efficient enough (b) is preserved.


This reasoning strays a bit away from the spec because it wants to do 
(c) too often.


 Overall, I don't think this is possible in any statically typed 
 programming language I know. I don't think even a C preprocessor macro 
 can fulfill both (c) and (e) unless that "when possible" in (c) means 
 "when possible in the language" instead of "when passed lvalues".


Heck, I did it in C++. It takes some hundred plus lines of code though 
:o). The obvious purpose of my challenge is to find what it takes to 
make it a trivial few-liner in D.


Andrei
Jan 21 2007
parent reply Kevin Bealer <kevinbealer gmail.com> writes:
Andrei Alexandrescu (See Website For Email) wrote:

 Frits van Bommel wrote:

 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.






...

 Heck, I did it in C++. It takes some hundred plus lines of code though 
 :o). The obvious purpose of my challenge is to find what it takes to 
 make it a trivial few-liner in D.
 
 
 Andrei


Here's my late entry:

alias max_type(T, U) {
   static if (T.max > U.max) {
     alias T max_type;
   } else {
     alias U max_type;
   }
}

max_type(T, U) ALIAS max(T, U)(inout T x, inout U y)
{
     alias max_type(T,U) MT;
     MT x1 = x, y1 = y;

     if (x1 >= y1) {
         static if (is (MT == T)) {
             return alias x;
         } else {
             return x1;
         }
     } else {
         static if (is (MT == U)) {
             return alias y;
         } else {
             return y1;
         }
     }
}

The new feature is "return alias x", which is just syntax for saying 
that you are returning a reference to the input parameter.

Note that "ALIAS" should be replaced by some keyword -- or maybe remvoed 
entirely, since it can be deduced easily as described below.  It should 
be safe to remove it entirely since we can deduce it from the I was 
going to use "alias" but it looks too much like If D ever gets a keyword 
to indicate the opposite of C++'s "strict" keyword, I would think it 
could be used here.

A. Generic

As long as "U + T" is legal, I think this could work.  A better choice 
of the return value could be made if you expect "char[]" to be used, but 
otherwise, I think it's a pretty generic solution.  If constants are 
passed into the function, the "static if" needs to fail somehow.

B. Efficient

Consider this simple saltshaker...

One way this could work from a stack packing point of view, is to 
imagine that the code actually returns this object:

struct real_return_t {
     max_type(T,U) * _proxy;
     max_type(T,U)   _data;
}

Then, plain old "return XYZ" does this:

  real_return_t rv;
  rv._data  = XYZ;
  rv._proxy = & rv._data;

But the "return alias XYZ" does this:

  real_return_t rv;
  rv._proxy = & x; // input arg

In the calling code, the return value of max() is the dereference of 
rv._proxy, so that  max(a, b)  becomes  *(max(a, b).proxy), thus 
allowing the assignment.

Optimization:

1. If T == U, then both returns end up being "return alias", which means 
that the caller never uses the 'rv._data' member; it can be eliminated 
and the function becomes T * max(...), with automagic dereferencing of 
the return value.

2. If typeof(T + U) is neither T nor U (think byte + uint -> int), then 
the rv.data field is always used, which means the return value is always 
equivalent to "*& rv._data".  This means that the member rv._proxy can 
be optimized away.  Thus, it could becomes normal int max(...).

3. If T == MT but T != U, or vice versa, then the real_return_t object 
cannot be removed, but we essentially have a variant return type, and a 
hand-written implementation would normally use the same technique to 
return either the input primitive or another one.

So, in cases 1-3, I think it is as efficient as we could expect from a 
hand-written job.

C. Lvalueness

I think so.  This preserves it when possible, gets rid of it when not, 
and does so in a way that is highly readable.  NOTE that this solution 
preserves lvalue-ness above-and-beyond because for (int x, long y), it 
preserves it for y even though it can't preserve it for x.


D. Two or More arguments

I didn't code up this part but my gut reaction solution is to use a 
static foreach (do those exist yet?) in the max() function and some kind 
of recursive template dance in the max_type template.

E. I think using "+" is enough for this if classes are not involved.  If 
they are then I don't think deducing the max of two classes is possible 
without cooperation from them.  However, one could try to assign in both 
directions and see which assignment "hurts less" with something like SFINAE.

F. As long as you don't count this post... but the code looks tidy.

------

Solution Two

NOTE: This is not a C++ "&", see below.

template max(T, U) {
   static if (T == U) {
     T & max(T & x, U & y)
     {
       if (*x >= *y) {
         return x;
       } else {
         return y;
       }
     }
   } else {
     max_type(T, U) max(T, U)(T x, U y)
     {
       alias max_type(T,U) MT;

       if (x >= y) {
         return x;
       } else {
         return y;
       }
     }
   }
}

The "&" here is kind of like C++'s "&" type, but you can't use it except 
in function interfaces.  In the context of a function argument, it means 
that the caller of the function is actually passing "& x" when they say 
"x", and in the case of a return value, the caller thinks they get 
something like "T x", but it they actually get a "T * x", and when they 
use it, the "x" turns into "*x".

Inside the function body, no magic translations are done, the writer of 
the function use actual pointers to do the work to make it harder to 
accidentally return addresses of local variables.

I think this satisfies A B C E F, though not as heroicly with C as the 
Solution One (which may be a good thing.)

Kevin
Jan 24 2007
parent "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
Kevin Bealer wrote:

 Here's my late entry:
 
 alias max_type(T, U) {
   static if (T.max > U.max) {
     alias T max_type;
   } else {
     alias U max_type;
   }
 }


So far so good.


 max_type(T, U) ALIAS max(T, U)(inout T x, inout U y)
 {
     alias max_type(T,U) MT;
     MT x1 = x, y1 = y;
 
     if (x1 >= y1) {
         static if (is (MT == T)) {
             return alias x;
         } else {
             return x1;
         }
     } else {
         static if (is (MT == U)) {
             return alias y;
         } else {
             return y1;
         }
     }
 }


This will not work when passed lvalues, a la:

auto b = max(a + 1, a - 1);


 The new feature is "return alias x", which is just syntax for saying 
 that you are returning a reference to the input parameter.


The reference thing must be reflected in function's return type, not in 
the function's return statement(s). This is for a number of reasons, 
including separate compilation and ease of parsing.


 Note that "ALIAS" should be replaced by some keyword -- or maybe remvoed 
 entirely, since it can be deduced easily as described below.  It should 
 be safe to remove it entirely since we can deduce it from the I was 
 going to use "alias" but it looks too much like If D ever gets a keyword 
 to indicate the opposite of C++'s "strict" keyword, I would think it 
 could be used here.


I'm not sure what the purpose of ALIAS is. Was it to indicate that max 
returns, or may return, a reference?

In any case, the entry needs some rework because of the reason above: 
it's not sound to deduce storage from the function's return value, 
without actually reflecting that storage in the statically-known return 
type.

Moving on to the second entry...


 Solution Two
 
 NOTE: This is not a C++ "&", see below.
 
 template max(T, U) {
   static if (T == U) {
     T & max(T & x, U & y)
     {
       if (*x >= *y) {
         return x;
       } else {
         return y;
       }
     }
   } else {
     max_type(T, U) max(T, U)(T x, U y)
     {
       alias max_type(T,U) MT;
 
       if (x >= y) {
         return x;
       } else {
         return y;
       }
     }
   }
 }

 The "&" here is kind of like C++'s "&" type, but you can't use it except 
 in function interfaces.  In the context of a function argument, it means 
 that the caller of the function is actually passing "& x" when they say 
 "x", and in the case of a return value, the caller thinks they get 
 something like "T x", but it they actually get a "T * x", and when they 
 use it, the "x" turns into "*x".


What if I call max with two rvalues of the same type?

auto b = max(a + 1, a + 1);


 Inside the function body, no magic translations are done, the writer of 
 the function use actual pointers to do the work to make it harder to 
 accidentally return addresses of local variables.
 
 I think this satisfies A B C E F, though not as heroicly with C as the 
 Solution One (which may be a good thing.)


But rvalue handling is not satisfactory, and besides there is the scary 
code duplication. I'm afraid this candidate needs some rework too :o).


Andrei
Jan 26 2007
prev sibling next sibling parent reply Xinok <xnknet gmail.com> writes:
Take Two :)

template maxtype(T...){
	static if(T.length == 0) static assert(false);
	static if(T.length > 2) alias maxtype!(typeof(T[0]+T[1]), T[2..length])
maxtype;
	static if(T.length == 2) alias typeof(T[0]+T[1]) maxtype;
	static if(T.length == 1) alias typeof(T[0]) maxtype;
}

maxtype!(T) max(T...)(T arg){
	static assert(arg.length > 0);
	static if(arg.length > 2) return max(arg[0] >= arg[1] ? arg[0] : arg[1],
arg[2..length]);
	static if(arg.length == 2) return arg[0] >= arg[1] ? arg[0] : arg[1];
	static if(arg.length == 1) return arg[0];
}

void main(){
	writefln(max(15, 30, 45.5, 60.4));
}


a) generic
Not sure 100% what you mean, but the function accepts arguments of any type.

b) efficient
Function recursion. Not the most efficient, perhaps using a static foreach
would be best?

c) preserve lvalueness
This is impossible when using a mix of types. When using the same type though,
you could rewrite the function to make use of pointers.

d) should accept two or more arguments
check

e) should return the "smartest" type
This is what the 'maxtype' template is for. All that matters now is how smart
the D compiler is.
I already tested it, it automatically prefers unsigned types over signed types.
For a 'min' function though, the template would require a bit of conditioning
to prioritize signed types.

f) short and easy to understand
Not sure about this, but the function is surely easy to use. Just give it the
arguments, and it returns the greatest value.
Jan 21 2007
next sibling parent reply donth ave <d onth.ave> writes:
Xinok Wrote:


 T[0]+T[1]


To have addition is an additional(sic!) requirement not present in the
challenge.
--
Anonymity is not a Crime
Jan 21 2007
parent reply Lionello Lunesu <lio lunesu.remove.com> writes:
donth ave wrote:

 Xinok Wrote:
 

 T[0]+T[1]


 To have addition is an additional(sic!) requirement not present in the
 challenge.


Would typeof(T[0]>T[1]?T[0]:T[1]) work? I'd have to test it, I guess :)
Jan 22 2007
next sibling parent reply Don Clugston <dac nospam.com.au> writes:
Lionello Lunesu wrote:

 donth ave wrote:

 Xinok Wrote:


 T[0]+T[1]


 To have addition is an additional(sic!) requirement not present in the
 challenge.


 
 Would typeof(T[0]>T[1]?T[0]:T[1]) work? I'd have to test it, I guess :)


No, it doesn't work. But this does:
(starting to fail the simplicity requirement though...)
------
template maxtype(T...){
     static if(T.length == 0) static assert(false);
     static if(T.length == 1) alias typeof(T[0]) maxtype;
     static if(T.length == 2 && is( typeof( (T[0] x, T[1] y){ return y < 
x ? y : x;}) Q == return)) {
         alias Q maxtype;
     }
     static if(T.length > 2) {
         alias maxtype!(maxtype!(T[0..1]), T[2..$]) maxtype;
     }
}

maxtype!(T) max(T...)(T arg){
     static assert(arg.length > 0);
     static if(arg.length == 1) return arg[0];
     static if(arg.length == 2)
       return arg[0] >= arg[1] ? arg[0] : arg[1];
     static if(arg.length > 2)
       return max(arg[0] >= arg[1] ? arg[0] : arg[1], arg[2..length]);
}

void main(){
     writefln(max(15, 30, 45.5, 60.4));
}
----------
Jan 22 2007
next sibling parent reply =?ISO-8859-1?Q?Jari-Matti_M=E4kel=E4?= <jmjmak utu.fi.invalid> writes:
Don Clugston kirjoitti:

 Lionello Lunesu wrote:

 donth ave wrote:

 Xinok Wrote:


 T[0]+T[1]


 To have addition is an additional(sic!) requirement not present in the
 challenge.


 Would typeof(T[0]>T[1]?T[0]:T[1]) work? I'd have to test it, I guess :)


 
 No, it doesn't work. But this does:
 (starting to fail the simplicity requirement though...)


Squeezing a bit might help f) a minor bit more:

template maxtype(T...){
    static if(T.length == 0) static assert(false);
    static if(T.length == 1) alias typeof(T[0]) maxtype;
    static if(T.length == 2 && is( typeof( (T[0] x, T[1] y){ return y <
x ? y : x;}) Q == return)) {
        alias Q maxtype;
    }
    static if(T.length > 2) {
        alias maxtype!(maxtype!(T[0..1]), T[2..$]) maxtype;
    }
}

maxtype!(T) max(T...)(T arg){
    static if(arg.length == 1) return arg[0];
    static if(arg.length > 1) return arg[0] >= arg[1] ? arg[0] :
max(arg[1..$]);
}


Doesn't it work as an lvalue for classes now?
Jan 22 2007
parent reply Don Clugston <dac nospam.com.au> writes:
Jari-Matti Mäkelä wrote:

 Don Clugston kirjoitti:

 Lionello Lunesu wrote:

 donth ave wrote:

 Xinok Wrote:


 T[0]+T[1]


 To have addition is an additional(sic!) requirement not present in the
 challenge.


 Would typeof(T[0]>T[1]?T[0]:T[1]) work? I'd have to test it, I guess :)


 No, it doesn't work. But this does:
 (starting to fail the simplicity requirement though...)


 
 Squeezing a bit might help f) a minor bit more:
 
 template maxtype(T...){
     static if(T.length == 0) static assert(false);
     static if(T.length == 1) alias typeof(T[0]) maxtype;
     static if(T.length == 2 && is( typeof( (T[0] x, T[1] y){ return y <
 x ? y : x;}) Q == return)) {
         alias Q maxtype;
     }
     static if(T.length > 2) {
         alias maxtype!(maxtype!(T[0..1]), T[2..$]) maxtype;
     }
 }
 
 maxtype!(T) max(T...)(T arg){
     static if(arg.length == 1) return arg[0];
     static if(arg.length > 1) return arg[0] >= arg[1] ? arg[0] :
 max(arg[1..$]);
 }
 
 
 Doesn't it work as an lvalue for classes now?


Maybe. (does ? : preserve lvalues for classes?)
Pared down to the minimum, it is now:

template maxtype(T...){
   static if(T.length == 1) alias typeof(T[0]) maxtype;
   else static if(T.length > 2)
         alias maxtype!(maxtype!(T[0..1]), T[2..$]) maxtype;
   else static if(is( typeof( (T[0] x, T[1] y){ return y > x ? y : x;})
   Q == return))
         alias Q maxtype;
}

maxtype!(T) max(T...)(T arg){
     static if(arg.length == 1) return arg[0];
     else return arg[0] >= arg[1] ? arg[0] : max(arg[1..$]);
}

mintype!(T) min(T...)(T arg){
     static if(arg.length == 1) return arg[0];
     else return arg[0] <= arg[1] ? arg[0] : min(arg[1..$]);
}

Not too terrible.
Jan 22 2007
next sibling parent reply Donth Ave <d onth.ave> writes:
Don Clugston Wrote:

 Not too terrible.


But what if classes are allowed?
--
Anonymity is not a Crime
Jan 22 2007
parent Don Clugston <dac nospam.com.au> writes:
Donth Ave wrote:

 Don Clugston Wrote:

 Not too terrible.


 But what if classes are allowed?
 --
 Anonymity is not a Crime


Actually, it satisfies *all* of the requirements if classes are allowed.

eg
A a = new A;
A b = new B;
max(a, b)*=0.6; // compiles OK.
Jan 22 2007
prev sibling parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Don Clugston wrote:

 Pared down to the minimum, it is now:
 
 template maxtype(T...){
   static if(T.length == 1) alias typeof(T[0]) maxtype;
   else static if(T.length > 2)
         alias maxtype!(maxtype!(T[0..1]), T[2..$]) maxtype;
   else static if(is( typeof( (T[0] x, T[1] y){ return y > x ? y : x;})
   Q == return))
         alias Q maxtype;
 }
 
 maxtype!(T) max(T...)(T arg){
     static if(arg.length == 1) return arg[0];
     else return arg[0] >= arg[1] ? arg[0] : max(arg[1..$]);
 }
 


[snip min]

 
 Not too terrible.


Except you broke it ;)
-----
urxae urxae:~/tmp$ cat test.d
template maxtype(T...){
   static if(T.length == 1) alias typeof(T[0]) maxtype;
   else static if(T.length > 2)
         alias maxtype!(maxtype!(T[0..1]), T[2..$]) maxtype;
   else static if(is( typeof( (T[0] x, T[1] y){ return y > x ? y : x;})
   Q == return))
         alias Q maxtype;
}

maxtype!(T) max(T...)(T arg){
     static if(arg.length == 1) return arg[0];
     else return arg[0] >= arg[1] ? arg[0] : max(arg[1..$]);
}


import std.stdio;

void main(){
     auto x = max(5, 1, 100);
     writefln(x);
}
urxae urxae:~/tmp$ dmd -run test.d
5
-----

'max' should be this:
-----
maxtype!(T) max(T...)(T arg){
     static if(arg.length == 1) return arg[0];
     else return max(arg[0] >= arg[1] ? arg[0] : arg[1], arg[2..$]);
}
-----
Jan 23 2007
parent reply =?ISO-8859-1?Q?Jari-Matti_M=E4kel=E4?= <jmjmak utu.fi.invalid> writes:
Frits van Bommel kirjoitti:

 Don Clugston wrote:

 Pared down to the minimum, it is now:

 template maxtype(T...){
   static if(T.length == 1) alias typeof(T[0]) maxtype;
   else static if(T.length > 2)
         alias maxtype!(maxtype!(T[0..1]), T[2..$]) maxtype;
   else static if(is( typeof( (T[0] x, T[1] y){ return y > x ? y : x;})
   Q == return))
         alias Q maxtype;
 }

 maxtype!(T) max(T...)(T arg){
     static if(arg.length == 1) return arg[0];
     else return arg[0] >= arg[1] ? arg[0] : max(arg[1..$]);
 }


 [snip min]

 Not too terrible.


 
 Except you broke it ;)


In fact I broke it first and mislead Don :(


 'max' should be this:
 -----
 maxtype!(T) max(T...)(T arg){
     static if(arg.length == 1) return arg[0];
     else return max(arg[0] >= arg[1] ? arg[0] : arg[1], arg[2..$]);
 }


Just out of curiosity, what is happening here? If I write

  else return arg[0] >= arg[1] ? max(arg[0]) : max(arg[1], arg[2..$]);

it does not work, but

  else return max(arg[0] >= arg[1] ? arg[0] : arg[1], arg[2..$]);

works.
Jan 23 2007
next sibling parent =?ISO-8859-1?Q?Jari-Matti_M=E4kel=E4?= <jmjmak utu.fi.invalid> writes:
Jari-Matti Mäkelä wrote:

 Just out of curiosity, what is happening here? If I write
 
   else return arg[0] >= arg[1] ? max(arg[0]) : max(arg[1], arg[2..$]);
 
 it does not work, but
 
   else return max(arg[0] >= arg[1] ? arg[0] : arg[1], arg[2..$]);
 
 works.


Ok, now I got it. Got a bit distracted by other languages.
Jan 23 2007
prev sibling parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Jari-Matti Mäkelä wrote:

 Frits van Bommel kirjoitti:

 Don Clugston wrote:

 Not too terrible.


 Except you broke it ;)


 
 In fact I broke it first and mislead Don :(


Oh, sorry. I only noticed it when I looked at Don's post, and didn't 
notice your version between his...
Jan 23 2007
prev sibling parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Don Clugston wrote:

     }
     static if(T.length > 2) {
         alias maxtype!(maxtype!(T[0..1]), T[2..$]) maxtype;
     }
 


Shouldn't that be:
   alias maxtype!(maxtype!(T[0..2]), T[2..$]) maxtype;
(not really a relevant nitpick)

-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Jan 22 2007
prev sibling parent reply Donth Ave <d onth.ave> writes:
== Quote from Lionello Lunesu (lio lunesu.remove.com)'s article

 T[0]>T[1]


To have a total ordering is also an additional requirement not present
in the challenge.
--
Anonymity is not a Crime
Jan 22 2007
next sibling parent Lionello Lunesu <lio lunesu.remove.com> writes:
Donth Ave wrote:

 == Quote from Lionello Lunesu (lio lunesu.remove.com)'s article

 T[0]>T[1]


 To have a total ordering is also an additional requirement not present
 in the challenge.
 --
 Anonymity is not a Crime
 


typeof(0?T[0]:T[1]) seems to work fine though. The compiler picks the 
"smartest" type.
Jan 22 2007
prev sibling parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Donth Ave wrote:

 == Quote from Lionello Lunesu (lio lunesu.remove.com)'s article

 T[0]>T[1]


 To have a total ordering is also an additional requirement not present
 in the challenge.


That's a joke, right?

If not: how would you implement an efficient, generic max() function 
without using a total ordering?
You _have_ to use > [1] for that.


[1]: well, technically <, <= or >= will work as well, but it's all opCmp 
or built-in anyway, so it doesn't matter[2].
[2]: except for floating-point NaNs, those are always trouble :(.
Jan 23 2007
prev sibling parent "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
Xinok wrote:

 Take Two :)
 
 template maxtype(T...){
 	static if(T.length == 0) static assert(false);
 	static if(T.length > 2) alias maxtype!(typeof(T[0]+T[1]), T[2..length])
maxtype;
 	static if(T.length == 2) alias typeof(T[0]+T[1]) maxtype;
 	static if(T.length == 1) alias typeof(T[0]) maxtype;
 }
 
 maxtype!(T) max(T...)(T arg){
 	static assert(arg.length > 0);
 	static if(arg.length > 2) return max(arg[0] >= arg[1] ? arg[0] : arg[1],
arg[2..length]);
 	static if(arg.length == 2) return arg[0] >= arg[1] ? arg[0] : arg[1];
 	static if(arg.length == 1) return arg[0];
 }
 
 void main(){
 	writefln(max(15, 30, 45.5, 60.4));
 }
 
 
 a) generic
 Not sure 100% what you mean, but the function accepts arguments of any type.


That's what I meant. Any types that accept ">". You require the types to 
accept "+" too, so you need to fix that.


 b) efficient
 Function recursion. Not the most efficient, perhaps using a static foreach
would be best?


No worries. It's compile-time recursion.


 c) preserve lvalueness
 This is impossible when using a mix of types. When using the same type though,
you could rewrite the function to make use of pointers.


That's why you are invited to implement your own feature(s) that would 
make your max fit the requirement.


 d) should accept two or more arguments
 check
 
 e) should return the "smartest" type
 This is what the 'maxtype' template is for. All that matters now is how smart
the D compiler is.
 I already tested it, it automatically prefers unsigned types over signed types.
 For a 'min' function though, the template would require a bit of conditioning
to prioritize signed types.


Ah, I should have chosen "min" as a challenge :o).


 f) short and easy to understand
 Not sure about this, but the function is surely easy to use. Just give it the
arguments, and it returns the greatest value.


I think it fails at the "short" test, but it's a good start.


Andrei
Jan 21 2007
prev sibling next sibling parent reply Don Clugston <dac nospam.com.au> writes:
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.
 
 Looking forward to any takers!
 
 
 Andrei


----
Here's an implementation I put into Tango a few days ago. Unlike some 
other ones which have been posted, it does *not* require the types to 
support operator '+'. This was only for two arguments, but I believe it 
satisfies the other requirements. Should be easy to generalise.

----

private {
     // Implicitly convert to the smallest type which can store both T 
and U; acts like an 'auto' template return type.
template SharedComparisonType(T, U) {
     static if (is( typeof( (T x, U y){ return y<x? y: x;}) Q == return))
         alias Q SharedComparisonType;
}
}


/** Return the minimum of x and y.
  *
  * Note: If x and y are floating-point numbers, and either is a NaN,
  * x will be returned.
  */
SharedComparisonType!(T, U) min(T, U)(T x, U y) {
     return y<x? y : x;
}

/** Return the maximum of x and y.
  *
  * Note: If x and y are floating-point numbers, and either is a NaN,
  * x will be returned.
  */
SharedComparisonType!(T,U) max(T, U)(T x, U y) {
     return y>x? y : x;
}
Jan 21 2007
next sibling parent reply Alain <alainpoint yahoo.fr> writes:
Don Clugston Wrote:


 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.
 
 Looking forward to any takers!
 
 
 Andrei


 
 ----
 Here's an implementation I put into Tango a few days ago. Unlike some 
 other ones which have been posted, it does *not* require the types to 
 support operator '+'. This was only for two arguments, but I believe it 
 satisfies the other requirements. Should be easy to generalise.
 
 ----
 
 private {
      // Implicitly convert to the smallest type which can store both T 
 and U; acts like an 'auto' template return type.
 template SharedComparisonType(T, U) {
      static if (is( typeof( (T x, U y){ return y<x? y: x;}) Q == return))
          alias Q SharedComparisonType;
 }
 }
 
 
 /** Return the minimum of x and y.
   *
   * Note: If x and y are floating-point numbers, and either is a NaN,
   * x will be returned.
   */
 SharedComparisonType!(T, U) min(T, U)(T x, U y) {
      return y<x? y : x;
 }
 
 /** Return the maximum of x and y.
   *
   * Note: If x and y are floating-point numbers, and either is a NaN,
   * x will be returned.
   */
 SharedComparisonType!(T,U) max(T, U)(T x, U y) {
      return y>x? y : x;
 }


Fine !
but it doesn't work for the following common use case:
int[] mylist=[1,2,3,4,5];
int mymax=max(mylist);

Alain
Jan 22 2007
parent reply Don Clugston <dac nospam.com.au> writes:
Alain wrote:

 Don Clugston Wrote:
 

 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.

 Looking forward to any takers!


 Andrei


 ----
 Here's an implementation I put into Tango a few days ago. Unlike some 
 other ones which have been posted, it does *not* require the types to 
 support operator '+'. This was only for two arguments, but I believe it 
 satisfies the other requirements. Should be easy to generalise.

 ----

 private {
      // Implicitly convert to the smallest type which can store both T 
 and U; acts like an 'auto' template return type.
 template SharedComparisonType(T, U) {
      static if (is( typeof( (T x, U y){ return y<x? y: x;}) Q == return))
          alias Q SharedComparisonType;
 }
 }


 /** Return the minimum of x and y.
   *
   * Note: If x and y are floating-point numbers, and either is a NaN,
   * x will be returned.
   */
 SharedComparisonType!(T, U) min(T, U)(T x, U y) {
      return y<x? y : x;
 }

 /** Return the maximum of x and y.
   *
   * Note: If x and y are floating-point numbers, and either is a NaN,
   * x will be returned.
   */
 SharedComparisonType!(T,U) max(T, U)(T x, U y) {
      return y>x? y : x;
 }


 
 Fine !
 but it doesn't work for the following common use case:
 int[] mylist=[1,2,3,4,5];
 int mymax=max(mylist);
 
 Alain


Yes, as I said, it only works for the two-argument case.
It was intended as a direct replacement for C's
#define max(a, b) ((a)>(b)?(a):(b))

Just (for example) use Xinok's code, and replace typeof(X+Y) with 
SharedComparisonType!(X, Y).

Still doesn't solve (c) though; that's a really interesting challenge.

But since ?: doesn't preserve lvalues (ie, the following doesn't compile):

     real a = 5.2;
     real b = 3.1;
     (a> b? a : b) *= 0.7;

it seems to me that it's not really a template issue, but rather 
something even more fundamental.
(Interestingly,  auto c = (a> b? a : b).max; does compile; but if b is 
an int, and a is a real, it always returns real.max, even if b<a).
Jan 22 2007
parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Don Clugston wrote:

 Alain wrote:

 Don Clugston Wrote:


 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.

 Looking forward to any takers!


 Andrei


 ----
 Here's an implementation I put into Tango a few days ago. Unlike some 
 other ones which have been posted, it does *not* require the types to 
 support operator '+'. This was only for two arguments, but I believe 
 it satisfies the other requirements. Should be easy to generalise.

 ----

 private {
      // Implicitly convert to the smallest type which can store both 
 T and U; acts like an 'auto' template return type.
 template SharedComparisonType(T, U) {
      static if (is( typeof( (T x, U y){ return y<x? y: x;}) Q == 
 return))
          alias Q SharedComparisonType;
 }
 }


 /** Return the minimum of x and y.
   *
   * Note: If x and y are floating-point numbers, and either is a NaN,
   * x will be returned.
   */
 SharedComparisonType!(T, U) min(T, U)(T x, U y) {
      return y<x? y : x;
 }

 /** Return the maximum of x and y.
   *
   * Note: If x and y are floating-point numbers, and either is a NaN,
   * x will be returned.
   */
 SharedComparisonType!(T,U) max(T, U)(T x, U y) {
      return y>x? y : x;
 }


 Fine !
 but it doesn't work for the following common use case:
 int[] mylist=[1,2,3,4,5];
 int mymax=max(mylist);

 Alain


 
 Yes, as I said, it only works for the two-argument case.
 It was intended as a direct replacement for C's
 #define max(a, b) ((a)>(b)?(a):(b))
 
 Just (for example) use Xinok's code, and replace typeof(X+Y) with 
 SharedComparisonType!(X, Y).
 
 Still doesn't solve (c) though; that's a really interesting challenge.
 


Yes, requirement (c) is the crux of the challenge. Like the ident 
function Alexei mentioned, to be solved it will require the introduction 
of some kind of reference mechanism into the type system, something that 
would has wide repercussions and is complex to design.

-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Jan 22 2007
prev sibling parent Sean Kelly <sean f4.ca> writes:
Don Clugston wrote:

     // Implicitly convert to the smallest type which can store both T 
 and U; acts like an 'auto' template return type.
 template SharedComparisonType(T, U) {
     static if (is( typeof( (T x, U y){ return y<x? y: x;}) Q == return))
         alias Q SharedComparisonType;
 }


Clever :-)  I suppose one parameter of this challenge should be some 
criteria for flexibility though.  For example, the above code doesn't 
work for this case:

     class B {}
     class C : B {}
     class D : B {}

     min( new C, new D );

And it perhaps should, since Object.opCmp(Object) exists.  Worse, if B 
is redefined as:

     class B { int opCmp( B val ) {} }

Then the overload mechanism can't determine whether to use Object.opCmp 
or B.opCmp for comparing C and D.

An added challenge would be to support:

     class B { int opCmp( int val ) {} }

     min( new B, 2 );

But perhaps all of this is going too far?  Your example is simple and 
handles the majority of realistic situations.


Sean
Jan 22 2007
prev sibling next sibling parent reply BLS <Killing_Zoe web.de> writes:
I am a D newbie, so do not expect a strike from a genius....
Ahem,
what if we have a builtin (numeric!) variant datatype incl. variant[]?

Bjoern

Andrei Alexandrescu (See Website For Email) schrieb:

 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.
 
 Looking forward to any takers!
 
 
 Andrei
Jan 22 2007
parent reply "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
BLS wrote:

 I am a D newbie, so do not expect a strike from a genius....
 Ahem,
 what if we have a builtin (numeric!) variant datatype incl. variant[]?


Welcome to the club :o). That would work, but it would likely fail the 
efficiency test.

Andrei
Jan 22 2007
parent BLS <Killing_Zoe web.de> writes:
Andrei Alexandrescu (See Website For Email) schrieb:

 BLS wrote:
 

 I am a D newbie, so do not expect a strike from a genius....
 Ahem,
 what if we have a builtin (numeric!) variant datatype incl. variant[]?


 
 
 Welcome to the club :o). That would work, but it would likely fail the 
 efficiency test.
 
 Andrei


Thanks Andrei,
my german/english dictionary says : likely means ->similar to or 
prospective.
So probabely it is worth to investigate : How much optimized assembler 
code can do ?

Sure this solution has anyway a bad taste because it is a little bit 
like : Can anybody else do that for me :-)
Bjoern
Jan 22 2007
prev sibling next sibling parent Sean Kelly <sean f4.ca> writes:
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;


This is the largest stumbling block.  The rest could be handled with 
template code, though it may be a fairly verbose.


 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.


Reference return types notwithstanding, I took an initial stab at this a 
few months ago, as outlined in D.learn "max() in phobos?" (11/6/2006) on 
digitalmars.D.learn:

http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=digitalmars.D.learn&artnum=5152

I got distracted and never finished with it, but at the time I was 
experimenting with reducing the template code by using typeof( a + b ) 
as the return type when a and b are concrete values.  However, this 
wouldn't work if a reference type must be returned because of D's 
integer promotion rules (typeof( a + b ) == int where a and b are 
smaller than int).  Some problems with the code:

* It doesn't handle comparison of a UDT and a concrete type.  This could
   be done by adding more template code, but I didn't bother with it at
   the time--I was hoping for something simple and the code is already
   somewhat complex.

* The casts in min/max are required to support UDT comparison because
   the overload resolution mechanism can't handle complex situations.  An
   alternative might be to require the user to explicitly cast one of the
   parameters for min/max, but to me that kind of defeats the point of
   the min/max functions as a macro look-alike.

Most of the template code really belongs in a Traits module, but as it's 
required for the min/max implementation I think it should be counted 
when evaluating complexity :-)

--------------------------------------------------------------------------------

template isSignedIntegerType( T )
{
     const bool isSignedIntegerType = is( T == byte )  ||
                                      is( T == short ) ||
                                      is( T == int )   ||
                                      is( T == long )/+||
                                      is( T == cent )+/;
}

template isUnsignedIntegerType( T )
{
     const bool isUnsignedIntegerType = is( T == ubyte )  ||
                                        is( T == ushort ) ||
                                        is( T == uint )   ||
                                        is( T == ulong )/+||
                                        is( T == ucent )+/;
}

template isIntegerType( T )
{
     const bool isIntegerType = isSignedIntegerType!(T) ||
                                isUnsignedIntegerType!(T);
}

template commonBaseTypeOf( T, U )
{
     static assert( ( is( T == class )     && is( U == class ) ) ||
                    ( is( T == interface ) && is( U == interface ) ),
                    "Supplied types are not siblings." );

     static if( is( T : U ) )
         alias U commonBaseTypeOf;
     else static if( is( U : T ) )
         alias T commonBaseTypeOf;
     else static if( is( T == class ) )
         alias Object commonBaseTypeOf;
     else
         static assert( false, "Interfaces have no generic parent." );
}

template bestCommonTypeOf( T, U )
{
     static if( is( T == class )     || is( U == class ) ||
                is( T == interface ) || is( U == interface ) )
     {
         alias commonBaseTypeOf!( T, U ) bestCommonTypeOf;
     }
     else static if( is( T : U ) && is( U : T ) )
     {
         static if( T.sizeof > U.sizeof )
             alias T bestCommonTypeOf;
         else static if( T.sizeof < U.sizeof )
             alias U bestCommonTypeOf;
         else static if( isUnsignedIntegerType!(T) )
             alias T bestCommonTypeOf;
         else
             alias U bestCommonTypeOf;
     }
     else static if( is( U : T ) )
         alias T bestCommonTypeOf;
     else static if( is( T : U ) )
         alias U bestCommonTypeOf;
     else
         static assert( false, "Unable to find common type." );
}

template min( T, U )
{
     bestCommonTypeOf!(T, U) min( T t, U u )
     {
         alias bestCommonTypeOf!(T, U) rt;
         if( cast(rt) t < cast(rt) u )
             return t;
         return u;
     }
}

template max( T, U )
{
     bestCommonTypeOf!(T, U) max( T t, U u )
     {
         alias bestCommonTypeOf!(T, U) rt;
         if( cast(rt) t > cast(rt) u )
             return t;
         return u;
     }
}

void main()
{
     class B
     {
         this( int v )
         {
             value = v;
         }

         int opCmp( B rhs )
         {
             return value - rhs.value;
         }

         int opCmp( Object rhs )
         {
             return opCmp( cast(B) rhs );
         }

         private int value;
     }

     class C : B
     {
         this( int v )
         {
             super( v );
         }
     }

     class D : B
     {
         this( int v )
         {
             super( v );
         }
     }

     static assert( is( bestCommonTypeOf!( int, uint ) == uint ) );
     static assert( is( bestCommonTypeOf!( uint, int ) == uint ) );

     static assert( is( bestCommonTypeOf!( long, uint ) == long ) );
     static assert( is( bestCommonTypeOf!( uint, long ) == long ) );

     static assert( is( bestCommonTypeOf!( char, byte ) == byte ) );
     static assert( is( bestCommonTypeOf!( byte, char ) == char ) );


     static assert( is( bestCommonTypeOf!( byte, long ) == long ) );
     static assert( is( bestCommonTypeOf!( long, byte ) == long ) );
     static assert( is( bestCommonTypeOf!( long, float ) == float ) );
     static assert( is( bestCommonTypeOf!( float, long ) == float ) );
     static assert( is( bestCommonTypeOf!( float, real ) == real ) );
     static assert( is( bestCommonTypeOf!( cfloat, creal ) == creal ) );
     static assert( is( bestCommonTypeOf!( creal, cfloat ) == creal ) );

     static assert( is( bestCommonTypeOf!( B, C ) == B ) );
     static assert( is( bestCommonTypeOf!( C, B ) == B ) );
     static assert( is( bestCommonTypeOf!( C, D ) == Object ) );
     static assert( is( bestCommonTypeOf!( D, C ) == Object ) );

     int     ismall = 1, ibig = 2;
     byte    bsmall = 1, bbig = 2;
     float   fsmall = 1, fbig = 2;
     double  dsmall = 1, dbig = 2;

     assert( max( ibig, ismall )==ibig );
     assert( max( ismall, ibig )==ibig);
     assert( min( ibig, ismall )==ismall );
     assert( min( ismall, ibig )==ismall );

     assert( max( fbig, fsmall )==fbig );
     assert( max( fsmall, fbig )==fbig );
     assert( min( fbig, fsmall )==fsmall );
     assert( min( fsmall, fbig )==fsmall );

     assert( min( dsmall, fbig )==dsmall );
     assert( max( dsmall, fbig )==fbig );
     assert( min( dbig, fsmall )==fsmall );
     assert( max( dbig, fsmall )==dbig );

     assert( is( typeof( min( dsmall, fbig ) ) == double ) );
     assert( is( typeof( max( dsmall, fbig ) ) == double ) );
     assert( is( typeof( min( dbig, fsmall ) ) == double ) );
     assert( is( typeof( max( dbig, fsmall ) ) == double ) );

     assert( is( typeof( min( bsmall, ibig ) ) == int ) );
     assert( is( typeof( max( bsmall, ibig ) ) == int ) );
     assert( is( typeof( min( bbig, ismall ) ) == int ) );
     assert( is( typeof( max( bbig, ismall ) ) == int ) );

     B b = new B( 1 );
     C c = new C( 2 );
     D d = new D( 3 );

     assert( min( b, c ) == b );
     assert( max( b, c ) == c );
     assert( min( c, d ) == c );
     assert( max( c, d ) == d );

     assert( b < cast(B) c );
     assert( cast(B) c > b );

/*
     char  a;
     byte b;
     struct S {} struct T {}

     static assert( is( typeof( a + b ) == char ) );
     auto c = a + b;

     static assert( is( typeof( ubyte.init + ushort.init ) == bool ) );
*/
}
Jan 22 2007
prev sibling next sibling parent reply S. <S s.com> writes:
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.
 
 Looking forward to any takers!
 
 
 Andrei


Requirements C and E are mutually exclusive.
Jan 22 2007
parent "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
S. wrote:

 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.

 Looking forward to any takers!


 Andrei


 
 Requirements C and E are mutually exclusive.


They are not. "When possible" says it all.

Andrei
Jan 22 2007
prev sibling next sibling parent reply =?ISO-8859-1?Q?Lu=EDs_Marques?= <luismarques+spam gmail.com> writes:
Andrei Alexandrescu (See Website For Email) wrote:

 Here's a simple challenge: implement the max function. Requirements:


This is a very good challenge. I'm glad you started this thread.

Also, let's have some more of them down the line. It would be great if 
the conclusions were noted, to serve as a kind of language benchmark. 
Something to remind people of how much some simple things could still be 
better.

Luís
Jan 22 2007
parent reply John Reimer <terminal.node gmail.com> writes:
On Mon, 22 Jan 2007 22:53:39 +0000, Luís Marques wrote:


 Andrei Alexandrescu (See Website For Email) wrote:

 Here's a simple challenge: implement the max function. Requirements:


 
 This is a very good challenge. I'm glad you started this thread.
 
 Also, let's have some more of them down the line. It would be great if 
 the conclusions were noted, to serve as a kind of language benchmark. 
 Something to remind people of how much some simple things could still be 
 better.
 
 Luís



Oh?  Is D now mature enough to initiate the GotW system?  That didn't take
long. ;D

-JJR
Jan 22 2007
parent reply "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
John Reimer wrote:

 On Mon, 22 Jan 2007 22:53:39 +0000, Luís Marques wrote:
 

 Andrei Alexandrescu (See Website For Email) wrote:

 Here's a simple challenge: implement the max function. Requirements:


 This is a very good challenge. I'm glad you started this thread.

 Also, let's have some more of them down the line. It would be great if 
 the conclusions were noted, to serve as a kind of language benchmark. 
 Something to remind people of how much some simple things could still be 
 better.

 Luís


 
 
 Oh?  Is D now mature enough to initiate the GotW system?  That didn't take
 long. ;D


I think that's a great idea, so everybody feel free to post more challenges.

I think today's D lack of expressiveness in expressing max is a telling 
sign of its clumsiness at dealing with more advanced stuff. While I was 
implementing max for C++, for every single roadblock in the way, I could 
find many more places that were harmed.


Andrei
Jan 22 2007
parent John Reimer <terminal.node gmail.com> writes:
On Mon, 22 Jan 2007 15:28:48 -0800, Andrei Alexandrescu (See Website For
Email) wrote:


 John Reimer wrote:

 On Mon, 22 Jan 2007 22:53:39 +0000, Luís Marques wrote:
 

 Andrei Alexandrescu (See Website For Email) wrote:

 Here's a simple challenge: implement the max function. Requirements:


 This is a very good challenge. I'm glad you started this thread.

 Also, let's have some more of them down the line. It would be great if 
 the conclusions were noted, to serve as a kind of language benchmark. 
 Something to remind people of how much some simple things could still be 
 better.

 Luís


 
 
 Oh?  Is D now mature enough to initiate the GotW system?  That didn't take
 long. ;D


 
 I think that's a great idea, so everybody feel free to post more challenges.
 



I agree, but D's version of GotW definitely should get it's own name.
Something like NotW might work for D "Ninja of the Week" :D 

(for those that don't recall, the early D template stress-testers/pioneers
were affectionately referred to as Template Ninjas.) :)

-JJR
Jan 22 2007
prev sibling parent reply "Andrei Alexandrescu (See Website for Email)" <SeeWebsiteForEmail erdani.org> writes:
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
Jan 23 2007
next sibling parent reply "Andrey Khropov" <andkhropov_nosp m_mtu-net.ru> writes:
Andrei Alexandrescu (See Website for Email) wrote:


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


Ok, but now D doesn't allow to return lvalues from functions, so this won't
satisfy (c) for any type except classes that define opMulAssign.

-- 
AKhropov
Jan 23 2007
parent "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
Andrey Khropov wrote:

 Andrei Alexandrescu (See Website for Email) wrote:
 

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


 
 Ok, but now D doesn't allow to return lvalues from functions, so this won't
 satisfy (c) for any type except classes that define opMulAssign.


Future D will allow returning inout values. As you see, the maxreturn 
type might specify a storage. Sorry I forgot to mention that.

Andrei
Jan 23 2007
prev sibling next sibling parent reply Donth Ave <d onth.ave> writes:
== Quote from Andrei Alexandrescu:


 T2.max > T1.max
 true ? T1 : T2
      if (rhs > lhs) return rhs;


According to the generality of the challenge you have to admit at least
one of the following:
1) On posting the challenge some of the available properties of the
possible operands where silently dropped
2) The sample solution does not solve the challenge.

This is because in the challenge it is not required that
a1) all involved types have a maximum at all
a2) all involved types have the .max-property
b) all involved types are implicitely convertible to each other
c1) all involved values are totally ordered
c2) none of the storageclasses is "lazy"

Reason:
Violations of a1) or a2) might break "T2.max > T1.max"
Violations of b) might break "true ? T1 : T2"
Violations of c1) might break "rhs > lhs"
Violations of c2) might break "if (rhs > lhs) return rhs;" because this implies
one more evaluation.


Furthermore the implicite requirement of the max-function is also
violated, which is to be usable as an rvalue.

This is because in the challenge it is not required that
d) none of the involved types is a class.

Reason:
If the types include classes as well as basic types, then it is not clear which
one will be returned, but classes will need their opCast to be called, which
might
break "return rhs"
--
Anonymity is not a Crime
Jan 23 2007
parent reply "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
Donth Ave wrote:

 == Quote from Andrei Alexandrescu:
 

 T2.max > T1.max
 true ? T1 : T2
      if (rhs > lhs) return rhs;


 
 According to the generality of the challenge you have to admit at least
 one of the following:
 1) On posting the challenge some of the available properties of the
 possible operands where silently dropped
 2) The sample solution does not solve the challenge.


It does not fail in any way that you mention (see below).


 This is because in the challenge it is not required that
 a1) all involved types have a maximum at all
 a2) all involved types have the .max-property


Notice that the .max tests are guarded by if (std.is_num!(T1) && 
std.is_num(T2)). So that code is only executed for numerical types. I've 
omitted the implementation of std.is_num because it is trivial.


 b) all involved types are implicitely convertible to each other


This is a good point. In the general case (non-numeric), we can't do 
much but assume conservatively that the two types convert implicitly to 
one another.

In the numeric case, things are more interesting. With max it turns out 
that today's implicit numeric conversions do exactly as needed. (They 
will change in D 2.0, btw.) In the min case, they don't: for example, 
min(int, uint) should return int. So the body of min2 looks like:

if (rhs < lhs) return cast(ret_type) rhs;
return cast(ret_type) lhs;

Thanks for making this valuable point.


 c1) all involved values are totally ordered


Maximum implies some kind of ordering. To me using > versus <= is more 
of an academic point than a practical one. Once you have one, you can 
reasonably define all others.


 c2) none of the storageclasses is "lazy"


Lazy is never deduced, and it was not part of the requirement.


 Reason:
 Violations of a1) or a2) might break "T2.max > T1.max"
 Violations of b) might break "true ? T1 : T2"
 Violations of c1) might break "rhs > lhs"
 Violations of c2) might break "if (rhs > lhs) return rhs;" because this implies
 one more evaluation.


I refute all these on basis of what I explained above.


 Furthermore the implicite requirement of the max-function is also
 violated, which is to be usable as an rvalue.


An lvalue can always be used as an rvalue.


 This is because in the challenge it is not required that
 d) none of the involved types is a class.
 
 Reason:
 If the types include classes as well as basic types, then it is not clear which
 one will be returned, but classes will need their opCast to be called, which
might
 break "return rhs"


This is a good point. If both lhs and rhs are classes, the code works 
properly (barring a few corner cases). But the case max(obj, 4) could be 
handled better. In that case, the built-in should be explicitly 
converted to the object type.


Andrei
Jan 23 2007
next sibling parent Carlos Santander <csantander619 gmail.com> writes:
Andrei Alexandrescu (See Website For Email) escribió:

 Donth Ave wrote:
 

 c1) all involved values are totally ordered


 
 Maximum implies some kind of ordering. To me using > versus <= is more 
 of an academic point than a practical one. Once you have one, you can 
 reasonably define all others.
 


This is in fact a non-issue, as in D you only have to define opCmp and you get 
all of those.

-- 
Carlos Santander Bernal
Jan 24 2007
prev sibling parent reply Donth Ave <d onth.ave> writes:
Andrei Alexandrescu wrote: 


 Notice that the .max tests are guarded by if (std.is_num!(T1) && 
 std.is_num(T2)). So that code is only executed for numerical
 types. I've omitted the implementation of std.is_num because it is
 trivial. 


If it is trivial to implement, then I do not understand how. Please explain how
std.is_num is able to determine whether some class represents a number type.
The only way I can think of is the requirement to have some predicate isNum
defined in every class.

But even if std.is_num is implemented: you haven't restricted the challenge to
types who repesent sets of numbers which have a maximum. The easiest set of
numbers, the natural numbers, does not have a maximum. So how will someone
define a maximum on this type?

Although you might want to say "pure academic" one can implement such an
infinite type by storing a concrete value on an unbounded sequence of
BlueRays/DVDs/CDs and work on the values by using three ore more burners and
readers.    


 In the numeric case, things are more interesting. With max it
 turns out that today's implicit numeric conversions do exactly as
 needed.


I doubt that. How can two different numerical classes be implicitely converted
to each other?


 Maximum implies some kind of ordering. To me using > versus <= is
 more of an academic point than a practical one. Once you have one,
 you can reasonably define all others.


Please check to know the differences between "monotonic ordering" and "strict
monotonic ordering" of which you are writing and "total ordering" or "partial
ordering" which I am writing of. To compute a maximum only a "partial ordering"
is required.

A set of arguments that is only partially ordered may not have a maximum---and
because in the challenge there is no specification for this case, it would be
okay to raise an exception as the sample solution does.

But if there is a maximum the sample solution will fail to return it.

To see that look at a type which has three elements LEFT, RIGHT and TOP. Where
LEFT and RIGHT are not ordered but both are less than TOP.

Calling "max( LEFT, RIGHT, TOP)" with your implementation will result in an
exception raised on comparing LEFT with RIGHT, although the return value should
be TOP.



 Lazy is never deduced, and it was not part of the requirement.


It was not excluded.


 But the case max(obj,4) could be handled better. In that case, the
 built-in should be explicitly converted to the object type.


... and it will fail if obj does not have such converter. The same holds for a
call min( o1, o2), where o1 and o2 are from different classes. And to have such
converters was not given in the challenge.

Sorrily you failed to see the main point: if one puts a conversion into the
template that conversion will destroy the otherwise possible lvalueness. If one
does not put a conversion into the template one and in case of mixed types one
has to prefix every access to the value returned from max with a cast. But
according to the challenge that is okay, because there is no requirement for
not casting.
--
Anonymity is not a Crime
Jan 24 2007
parent reply "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
Donth Ave wrote:

 Andrei Alexandrescu wrote:
 

 Notice that the .max tests are guarded by if (std.is_num!(T1) && 
 std.is_num(T2)). So that code is only executed for numerical types.
 I've omitted the implementation of std.is_num because it is 
 trivial.


 If it is trivial to implement, then I do not understand how. Please
 explain how std.is_num is able to determine whether some class
 represents a number type. The only way I can think of is the
 requirement to have some predicate isNum defined in every class.


I didn't mean to be more Catholic than the Pope. std.is_num determines 
whether a type is a _built-in_ numeric type. If not, my solution will 
not make heroic efforts to detect various conventions that user-defined 
types might have implemented. It will conservatively deduce the type to 
be typeof(true ? T : U).


 But even if std.is_num is implemented: you haven't restricted the
 challenge to types who repesent sets of numbers which have a maximum.
 The easiest set of numbers, the natural numbers, does not have a
 maximum. So how will someone define a maximum on this type?

 Although you might want to say "pure academic" one can implement such
 an infinite type by storing a concrete value on an unbounded sequence
 of BlueRays/DVDs/CDs and work on the values by using three ore more
 burners and readers.


This reminds me of a novel by Dostoevsky: a guy makes a remark at a 
party and another guy goes on and lives his life by it. If my 
requirements did not restrict implementation in certain ways, that 
doesn't mean mind should feverishly work on finding stretches and corner 
cases.


 In the numeric case, things are more interesting. With max it turns
 out that today's implicit numeric conversions do exactly as needed.
 


 I doubt that. How can two different numerical classes be implicitely
 converted to each other?


float -> double among others?


 Maximum implies some kind of ordering. To me using > versus <= is 
 more of an academic point than a practical one. Once you have one, 
 you can reasonably define all others.


 Please check to know the differences between "monotonic ordering" and
 "strict monotonic ordering" of which you are writing and "total
 ordering" or "partial ordering" which I am writing of. To compute a
 maximum only a "partial ordering" is required.
 
 A set of arguments that is only partially ordered may not have a
 maximum---and because in the challenge there is no specification for
 this case, it would be okay to raise an exception as the sample
 solution does.
 
 But if there is a maximum the sample solution will fail to return it.
 
 
 To see that look at a type which has three elements LEFT, RIGHT and
 TOP. Where LEFT and RIGHT are not ordered but both are less than TOP.
 
 
 Calling "max( LEFT, RIGHT, TOP)" with your implementation will result
 in an exception raised on comparing LEFT with RIGHT, although the
 return value should be TOP.


I understand. So basically you want max to find the top of a lattice. I 
personally find that funny, but let me also attempt an explanation.

In a lattice you could define > to throw an exception or to return 
false. The latter is the convention used by STL functions. So if a and b 
are unordered, both a > b and b > a return false. In that case the 
sample solution will work properly.


 Lazy is never deduced, and it was not part of the requirement.


 It was not excluded.


You don't understand. I don't need to exclude everything that's not 
possible or highly unlikely, otherwise please send me your meteor tax :o).


 But the case max(obj,4) could be handled better. In that case, the 
 built-in should be explicitly converted to the object type.


 
 ... and it will fail if obj does not have such converter. The same
 holds for a call min( o1, o2), where o1 and o2 are from different
 classes. And to have such converters was not given in the challenge.


So sue me. :oD


 Sorrily you failed to see the main point: if one puts a conversion
 into the template that conversion will destroy the otherwise possible
 lvalueness.


Of course I was aware of that point, and my solution was simple: 
lvalueness disappears as soon as the types are not identical, storage 
class included. I'm not sure how one could be much more aggressive than 
this.


 If one does not put a conversion into the template one
 and in case of mixed types one has to prefix every access to the
 value returned from max with a cast. But according to the challenge
 that is okay, because there is no requirement for not casting.


The current sample solution assumes that implicit conversion among 
different types is possible. This is more restrictive than it could, but 
I didn't put much emphasis on that because D's built-in implicit 
conversions will soon change (to the better). You are of course free to 
provide a better solution.

Speaking of which, sometimes more than one comparison is necessary. 
Consider:

int a = -1;
uint b = 3000000000; // three billion
auto x = max(a, b);

What this code wants is unambiguous: max between an int and a uint is 
always computable and returns a uint. But notice that converting either 
of a or b to the other's type will yield the wrong result: cast(uint)a 
is greater than b, and cast(int)b is smaller than a. The right solution 
for mixed-sign max is (nontemplated):

uint max(int a, uint b)
{
   if (a <= 0) return b;
   auto c = cast(uint) a;
   return c > a ? c : a;
}


Andrei
Jan 24 2007
next sibling parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Andrei Alexandrescu (See Website For Email) wrote:

 Speaking of which, sometimes more than one comparison is necessary. 
 Consider:
 
 int a = -1;
 uint b = 3000000000; // three billion
 auto x = max(a, b);
 
 What this code wants is unambiguous: max between an int and a uint is 
 always computable and returns a uint. But notice that converting either 
 of a or b to the other's type will yield the wrong result: cast(uint)a 
 is greater than b, and cast(int)b is smaller than a. The right solution 
 for mixed-sign max is (nontemplated):
 
 uint max(int a, uint b)
 {
   if (a <= 0) return b;
   auto c = cast(uint) a;
   return c > a ? c : a;
 }


In the above case, of course, you can also get away with casting both to 
long ;).

Signed-unsigned comparisons are one of those little annoyances. It has 
been proposed in the past that such comparisons should always return the 
correct result, by automatically expanding them to something similar to 
what you have done manually in above code (unless the compiler can 
determine it's not necessary, of course).
Jan 25 2007
prev sibling parent reply Donth Ave <d onth.ave> writes:
Andrei Alexandrescu (See Website For Email) Wrote:

 that doesn't mean mind should feverishly work on finding stretches and
 corner cases.


I wonder how Goedel would have reacted to such a remark.
--
Anonymity is not a Crime
Jan 25 2007
parent "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
Donth Ave wrote:

 Andrei Alexandrescu (See Website For Email) Wrote:

 that doesn't mean mind should feverishly work on finding stretches and
 corner cases.


 I wonder how Goedel would have reacted to such a remark.


Goedel dealt with axiomatic set theory. We're talking about max for D. 
Pick your fights. Please.

Andrei
Jan 25 2007
prev sibling parent reply Don Clugston <dac nospam.com.au> writes:
Andrei Alexandrescu (See Website for Email) wrote:

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


Surely this should be:

    else
      static if (std.is_num!(T1) && std.is_num!(T2))
         static if (T2.max > T1.max)
           alias storageof(T2) T2 maxtype;
         else
           alias storageof(T1) T1 maxtype;

       else
         alias storageof(true ? T1 : T2) typeof(true ? T1 : T2) maxtype;

Seems as though "storageof(X) X" will be an extremely common idiom -- 
far more common than "storageof(Y) X".

In fact, if there was a way to copy storage from one type to another, 
and check if two types have identical storage, a simpler syntax might be 
possible (just as a special syntax for the sign of a number is not 
required).


 * 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.)


This has been proposed many times. It would greatly simplify a lot of 
complex code.
Jan 24 2007
parent "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
Don Clugston wrote:

 Andrei Alexandrescu (See Website for Email) wrote:

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


 
 Surely this should be:
 
    else
      static if (std.is_num!(T1) && std.is_num!(T2))
         static if (T2.max > T1.max)
           alias storageof(T2) T2 maxtype;
         else
           alias storageof(T1) T1 maxtype;
 
       else
         alias storageof(true ? T1 : T2) typeof(true ? T1 : T2) maxtype;


Au contraire, your code will not compile. We are already past type 
equality, so we don't want to preserve the lvalueness anymore. For 
example, T1 may be unsigned and T2 unsigned long. You can't then return 
an inout value, even though both were inout.


 Seems as though "storageof(X) X" will be an extremely common idiom -- 
 far more common than "storageof(Y) X".


Yah. Walter thinks $T could be used as storageof(T) T.


 In fact, if there was a way to copy storage from one type to another, 
 and check if two types have identical storage, a simpler syntax might be 
 possible (just as a special syntax for the sign of a number is not 
 required).


This will definitely be possible.


 * 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.)


 
 This has been proposed many times. It would greatly simplify a lot of 
 complex code.


Well it saves an extra symbol, which is a good thing.


Andrei
Jan 24 2007