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

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?

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/

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/