www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - D templates + IFTI + Tuples + delegate literals = holy bovine!

reply Daniel Keep <daniel.keep+lists gmail.com> writes:
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);
         }
     }
Jan 08 2007
parent reply Vassily Gavrilyak <gavrilyak gmail.com> writes:
Cool stuff, almost what I searched for. filter works like a charm.
However not so for map and reduce. The return type of map and reduce is
different
from the type of item in collection.
I'm just started to look at D, so don't know the right way to write those
functions.
Declaration in Nemerle looks like this
public Map['a, 'b] (l : list ['a], f : 'a -> 'b) : list ['b] {
      $[ f(x) | x in l ]
}
So we have 2 types here, type of collection and type of result
And reduce(fold) has 2 types too.
So basically the following code:

struct Person{   int id;  char[] name;}
static Person[] people= [{1, "Joe"}, {2, "Bill"}];
int[] ids = map(persons, delegate int(Person p){return p.id;});

should produce [1,2]

Is that possible in D?
Feb 26 2007
parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Vassily Gavrilyak wrote:
 Cool stuff, almost what I searched for. filter works like a charm.
 However not so for map and reduce. The return type of map and reduce is
different
 from the type of item in collection.
 I'm just started to look at D, so don't know the right way to write those
functions.
 Declaration in Nemerle looks like this
 public Map['a, 'b] (l : list ['a], f : 'a -> 'b) : list ['b] {
       $[ f(x) | x in l ]
 }
 So we have 2 types here, type of collection and type of result
 And reduce(fold) has 2 types too.
 So basically the following code:
 
 struct Person{   int id;  char[] name;}
 static Person[] people= [{1, "Joe"}, {2, "Bill"}];
 int[] ids = map(persons, delegate int(Person p){return p.id;});
 
 should produce [1,2]
 
 Is that possible in D?

Wow; it's been a while :P I think this is the first reply I got to that post. Having a quick squizz at the code; you're right. The way I've derived the return type of map is completely wrong. I'll put that on my list of things to fix :P So in answer to your question, yes it should be entirely possible. The trick, in this case, is the following: static if( is( tOp tReturnType == return ) ) Which will derive the return type of the function. -- Daniel Incidentally, Nemerle is looking less and less like C# every time I see it :P -- Unlike Knuth, I have neither proven or tried the above; it may not even make sense. v2sw5+8Yhw5ln4+5pr6OFPma8u6+7Lw4Tm6+7l6+7D i28a2Xs3MSr2e4/6+7t4TNSMb6HTOp5en5g6RAHCP http://hackerkey.com/
Feb 26 2007
parent Daniel Keep <daniel.keep.lists gmail.com> writes:
map should now be fixed to return the actual type, and I've uploaded the
file to Wiki4D.  I actually couldn't find the source for this, so when I
downloaded it off the DM news archive (Thunderbird doesn't have my
original message :P) I had to go rebuild all the indenting.  Fun, fun, fun!

http://www.prowiki.org/wiki4d/wiki.cgi?DanielKeep/functools

Your original example should look like this:

    auto ids = map(persons, (Person p) { return p.id; });

Have fun, and hope it's all actually working this time :P

	-- Daniel

Daniel Keep wrote:
 
 Vassily Gavrilyak wrote:
 Cool stuff, almost what I searched for. filter works like a charm.
 However not so for map and reduce. The return type of map and reduce is
different
 from the type of item in collection.
 I'm just started to look at D, so don't know the right way to write those
functions.
 Declaration in Nemerle looks like this
 public Map['a, 'b] (l : list ['a], f : 'a -> 'b) : list ['b] {
       $[ f(x) | x in l ]
 }
 So we have 2 types here, type of collection and type of result
 And reduce(fold) has 2 types too.
 So basically the following code:

 struct Person{   int id;  char[] name;}
 static Person[] people= [{1, "Joe"}, {2, "Bill"}];
 int[] ids = map(persons, delegate int(Person p){return p.id;});

 should produce [1,2]

 Is that possible in D?

Wow; it's been a while :P I think this is the first reply I got to that post. Having a quick squizz at the code; you're right. The way I've derived the return type of map is completely wrong. I'll put that on my list of things to fix :P So in answer to your question, yes it should be entirely possible. The trick, in this case, is the following: static if( is( tOp tReturnType == return ) ) Which will derive the return type of the function. -- Daniel Incidentally, Nemerle is looking less and less like C# every time I see it :P

-- Unlike Knuth, I have neither proven or tried the above; it may not even make sense. v2sw5+8Yhw5ln4+5pr6OFPma8u6+7Lw4Tm6+7l6+7D i28a2Xs3MSr2e4/6+7t4TNSMb6HTOp5en5g6RAHCP http://hackerkey.com/
Feb 28 2007