challenge #2: implement the varargs_reduce metafunction

[Bruno Medeiros]

Andrei Alexandrescu (See Website for Email) wrote:
> My previous post defines max by availing itself of a metafunction called
> varargs_reduce. Your challenge is to define it. varargs_reduce takes an
> alias which it assumes is a function of two arguments, and it defines a
> vararg function that applies that alias repeatedly, similarly to the
> reduce primitive that is present in functional languages. Again, for
> background on functional reduce, see e.g.:
> 
> http://www.joelonsoftware.com/items/2006/08/01.html
> 
> Define varargs_reduce to deduce the result type properly, and to 
> generate code as efficient as possible.
> 
> 
> Andrei

Here is my try. I assume the reduce type must be exactly the same in all 
arguments. Should that not be the case?
As for efficiency, I'm not sure what the requirements are. Is there to 
be any parallelization/vectorization considerations? This one, instead 
of linear iteration, uses binary recursion to calculate the result, but 
for *no particular reason* since its not actually any faster than linear 
recursion.

This one seems much more easy that the fist challenge, so I suspect I'm 
missing something.


-----------------------------------
//import stdext.stdio;
import std.stdio : writeln = writefln;

static import meta.Util;

// Gets the typeof if not a type already.
template TypeOf(alias ALIAS) {
     static if(is(ALIAS)) {
         alias ALIAS TypeOf;
     } else {
         alias typeof(ALIAS) TypeOf;
     }
}

// See if the types are the same
template TypeEquals(alias A1, alias A2) {
     static if(is(TypeOf!(A1) == TypeOf!(A2)))
         const bool TypeEquals = true;
     else
         const bool TypeEquals = false;
}

// Duplicated template because primitive types do not match aliases :(
template TypeEquals(T1, T2) {
     static if(is(T1 == T2))
         const bool TypeEquals = true;
     else
         const bool TypeEquals = false;
}

/*****************  varargsReduce  ***************/


// Template implicit property workaround
template varargsReduce(alias FN) {
     alias varargsReduce_Impl!(FN).varargsReduce_Impl varargsReduce;
}

template varargsReduce_Impl(alias FN) {
     static import std.traits;

     static assert(is(typeof(FN) == function) || is(typeof(FN) == 
delegate));
     alias std.traits.ParameterTypeTuple!(FN) Params;
     alias std.traits.ReturnType!(FN) ReduceType;

     static assert(Params.length == 2);
     //static assert(typeof(FNarg1) == typeof(FNarg2));
     static assert(TypeEquals!(Params[0], Params[1]));
     //static assert(typeof(FNarg1) == ReduceType);
     static assert(TypeEquals!(Params[0], ReduceType));

     ReduceType varargsReduce_Impl(ARGS...) (ARGS args) {
         pragma(msg, "varargsReduce_Impl! length:" ~ 
meta.Util.itoa!(ARGS.length));
         //static assert(ARGS.length != 0, "Error: no args");
         static if(ARGS.length == 1) {
             static assert(TypeEquals!(typeof(args[0]), ReduceType));
             return args[0];
         } else
         static if(ARGS.length == 2) {
             static assert(TypeEquals!(typeof(args[0]), ReduceType));
             static assert(TypeEquals!(typeof(args[1]), ReduceType));
             return FN(args[0], args[1]);
         } else
         static if(ARGS.length >= 3) {
             ReduceType val1 = varargsReduce_Impl(args[0 .. ARGS.length/2]);
             ReduceType val2 = varargsReduce_Impl(args[ARGS.length/2 .. 
ARGS.length]);
             return FN(val1, val2);
         } else {
             static assert(false, "Error: no args");
         }
     }
}

/*****************  Usage  ***************/

int sum(int a, int b) {
     return a + b;
}

char[] cat(char[] a, char[] b) {
     return a ~ b;
}


void main(char[][] args) {

     auto result = varargsReduce!(sum)(1, 3, 3, 7);
     writeln(result);

     auto result2 = varargsReduce!(cat)("H"[], "e"[], "l"[], "l"[], "o"[]);
     writeln(result2);

}

-----------------  itoa: toStrings an int --------------------
module meta.Util;

template itoa(int i) {
     static if (i < 0) {
         static const char[] itoa = "-" ~ itoa!(-i);
     }
     else {
         static if (i / 10 > 0) {
             static const char[] itoa = itoa(i / 10) ~ "0123456789"[i % 10];
         } else {
             static const char[] itoa = "0123456789"[i % 10 .. i % 10 + 1];
         }
     }
}

-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D