D templates + IFTI + Tuples + delegate literals = holy bovine!

[Daniel Keep]

Reading an article on Google's MapReduce inspired me to take another 
crack at the old functional tools module I've re-written several times 
over the last... I dunno, year or two.

First version of it was rather ungainly to use; you have to pre-alias 
the functions because there was no IFTI, and I couldn't work out how to 
derive various things...

This latest incarnation is somewhat more elegant.  It implements map, 
filter and reduce.  map and filter work with arrays, hashes (both 
op(value) and op(key, value) versions) and any object that has a single 
output opApply (haven't tested with *multiple* opApplys, tho...). 
Reduce works with arrays and objects.

Best of all, D's templates and IFTI are now powerful enough that the 
only place I still need to specify types is in the delegate literal's 
argument list :P

The module actually has one or two new tricks in it (such as having 
templated default arguments AND IFTI), and could serve as a nice 
demonstration of templates in D.

If you want to see it in action, compile the source file with 
-version=functools_test to produce an executable (code at the bottom of 
the module).

I think D should really strive to add some functional stuff to its' 
standard library: should serve as a few extra nails in C++'s coffin :3

Enjoy :)

	-- Daniel

"functools.d":
/**
  * functools -- Functional programming tools.
  * Written by Daniel Keep.
  * Released under the BSDv2 license.
  */
/*
Copyright © 2007, Daniel Keep
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

     * Redistributions of source code must retain the above copyright
       notice, this list of conditions and the following disclaimer.
     * Redistributions in binary form must reproduce the above copyright
       notice, this list of conditions and the following disclaimer in the
       documentation and/or other materials provided with the distribution.
     * The names of the contributors may be used to endorse or promote
       products derived from this software without specific prior written
       permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.
*/
module functools;

template tIsArray(tType)
{
     static if( is( tType T : T[] ) )
         const bool tIsArray = true;
     else
         const bool tIsArray = false;
}

template tIsHash(tType)
{
     static if( tType.mangleof[0..1] == "H" )
         const bool tIsHash = true;
     else
         const bool tIsHash = false;
}

template tHashTypes(tType)
{
     static assert( tIsHash!(tType) );
     private tType h;

     static if( is( typeof(h.keys) tK : tK[] ) )
         alias tK tKey;
     else
         static assert(false, "Could not derive hash key type!");

     static if( is( typeof(h.values) tV : tV[] ) )
         alias tV tValue;
     else
         static assert(false, "Could not derive hash value type!");
}

template tHasOpApply(tType)
{
     alias tiHasOpApply!(tType).result tHasOpApply;
}

template tiHasOpApply(tType)
{
     tType inst;
     static if( is( typeof(&inst.opApply) tF ) )
         const result = true;
     else
         const result = false;
}

template tHasOpApplyReverse(tType)
{
     alias tiHasOpApplyReverse!(tType).result tHasOpApplyReverse;
}

template tiHasOpApplyReverse(tType)
{
     tType inst;
     static if( is( typeof(&inst.opApplyReverse) tF ) )
         const result = true;
     else
         const result = false;
}

template tIteratorType(tFn)
{
     static if( is( tFn tDg == delegate ) )
         alias tIteratorType!(tDg) tIteratorType;
     else static if( is( tFn tArgs == function ) )
         static if( is( tArgs[0] tDg == delegate ) )
             static if( is( tDg tDgArgs == function ) )
                 alias tDgArgs[0] tIteratorType;
}

template tMapResult(tType)
{
     static if( tIsArray!(tType) )
     {
         alias tType tMapResult;
     }
     else static if( tIsHash!(tType) )
     {
         alias tType tMapResult;
     }
     else static if( tHasOpApply!(tType) )
     {
         alias tIteratorType!(tIteratorClass!(tType))[] tMapResult;
     }
     /+else static if( tHasOpApplyReverse!(tType) )
     {
         alias tIteratorType!(tType)[] tMapResult;
     }+/
     else static if( tIsIteratorFunction!(tType) )
     {
         alias tIteratorType!(tType)[] tMapResult;
     }
     else
     {
         static assert(false, "Unsupported type: "~tType.mangleof);
     }
}

template tIteratorClass(tType)
{
     alias tiIteratorClass!(tType).result tIteratorClass;
}

template tiIteratorClass(tType)
{
     private tType inst;
     alias typeof(&inst.opApply) result;
}

template tReduceResult(tOp)
{
     static if( is( tOp tFn == delegate ) )
         alias tReduceResult!(tFn) tReduceResult;
     else static if( is( tOp tResult == return ) )
         alias tResult tReduceResult;
}

typedef int ReduceDefault;

tMapResult!(tType) map(tType, tOp)(tType coll, tOp op)
{
     static if( tIsArray!(tType) )
     {
         tMapResult!(tType) result;
         result.length = coll.length;

         foreach( i, v ; coll )
             result[i] = op(v);

         return result;
     }
     else static if( tIsHash!(tType) )
     {
         tMapResult!(tType) result;

         foreach( k, v ; coll )
         {
             static if( is( typeof(op(k,v)) ) )
             {
                 result[k] = op(k, v);
             }
             else
             {
                 result[k] = op(v);
             }
         }

         return result;
     }
     else static if( tHasOpApply!(tType) )
     {
         tMapResult!(tType) result;

         foreach( v ; coll )
         {
             result.length = result.length + 1;
             result[$-1] = op(v);
         }

         return result;
     }
     /+else static if( tIsIteratorFunction!(tType) )
     {
         tMapResult!(tType) result;

         int ifr = 0;
         tMapResult!(tType) temp;
         temp.length = 1;
         scope(exit) temp.length = 0;

         do
         {
             ifr = coll((typeof(temp[0]) v){temp[0] = v});
             if( result )
                 break;
             else
             {
                 result.length = result.length + 1;
                 result[$-1] = op(temp[0]);
             }
         }
         while( true );

         return result;
     }+/
     else
     {
         static assert(false, "Unsupported type: "~tType.mangleof);
     }
}

tMapResult!(tType) filter(tType, tOp)(tType coll, tOp op)
{
     static if( tIsArray!(tType) )
     {
         tMapResult!(tType) result;
         result.length = coll.length;
         uint l = 0;

         foreach( v ; coll )
         {
             if( op(v) )
                 result[l++] = v;
         }

         return result[0..l];
     }
     else static if( tIsHash!(tType) )
     {
         tMapResult!(tType) result;

         foreach( k,v ; coll )
         {
             bool use;
             static if( is( typeof(op(k,v)) ) )
                 use = op(k, v);
             else
                 use = op(v);
             if( use )
                 result[k] = v;
         }

         return result;
     }
     else static if( tHasOpApply!(tType) )
     {
         tMapResult!(tType) result;

         foreach( v ; coll )
         {
             if( op(v) )
             {
                 result.length = result.length + 1;
                 result[$-1] = v;
             }
         }

         return result;
     }
     else
     {
         static assert(false, "Unsupported type: "~tType.mangleof);
     }
}

tReduceResult!(tOp) reduce(tType, tOp, tInit = ReduceDefault)(
         tType seq, tOp op,
         tInit init = ReduceDefault.init)
{
     static if( tIsArray!(tType) || tHasOpApply!(tType) )
     {
         tReduceResult!(tOp) result;
         static if( !is( tInit == ReduceDefault ) )
             result = init;

         foreach( v ; seq )
             result = op(result, v);

         return result;
     }
     else
     {
         static assert(false, "Unsupported type: "~tType.mangleof);
     }
}

version( functools_test ):

     import std.stdio;

     class Naturals(int tpMax)
     {
         int opApply(int delegate(inout int) dg)
         {
             int result = 0;

             for( int i=1; i<=tpMax; i++ )
             {
                 result = dg(i);
                 if( result )
                     break;
             }

             return result;
         }
     }

     void main()
     {
         //
         // map
         //

         writefln("Testing map(seq, op)...");

         // Arrays
         {
             int[] naturals = [1,2,3,4,5,6,7,8,9];
             auto squares = map(naturals, (int v) { return v*v; });

             writefln("squares: %s", squares);
         }

         // Hashes
         {
             char[int] table;
             table[1] = char.init;
             table[2] = char.init;
             table[3] = char.init;

             auto new_table = map(table,
                     (int k, char v) { return '0'+k; });

             writef("new_table: [");
             bool first = true;
             foreach( k,v ; new_table )
             {
                 if( !first )
                     writef(", ");
                 writef("%d -> '%s'", k, v);
                 first = false;
             }
             writefln("]");
         }

         // Objects
         {
             scope naturals = new Naturals!(9);
             auto cubes = map(naturals, (int v) { return v*v*v; });

             writefln("cubes: %s", cubes);
         }

         //
         // filter
         //

         writefln("\nTesting filter(seq, op)...");

         // Arrays
         {
             int[] naturals = [1,2,3,4,5,6,7,8,9];
             auto evens = filter(naturals, (int v) { return v%2==0; });

             writefln("evens: %s", evens);
         }

         // Hashes
         {
             dchar[int] table;
             table[1] = 'a';
             table[2] = 'b';
             table[3] = 'c';

             auto new_table = filter(table,
                     (int k, char v) { return k%2!=0; });

             writef("new_table: [");
             bool first = true;
             foreach( k,v ; new_table )
             {
                 if( !first )
                     writef(", ");
                 writef("%d -> '%s'", k, v);
                 first = false;
             }
             writefln("]");
         }

         // Objects
         {
             scope naturals = new Naturals!(9);
             auto odds = filter(naturals, (int v) { return v%2!=0; });

             writefln("odds: %s", odds);
         }

         //
         // reduce
         //

         writefln("\nTesting reduce(seq, op)...");

         // Arrays
         {
             int[] naturals = [1,2,3,4,5,6,7,8,9];
             int sum = reduce(naturals, (int a, int b) { return a+b; });

             writefln("sum: %s", sum);
         }

         // Objects
         {
             scope naturals = new Naturals!(9);
             int product = reduce(naturals,
                     (int a, int b) { return a*b; }, 1);

             writefln("product: %s", product);
         }
     }