digitalmars.D - D templates + IFTI + Tuples + delegate literals = holy bovine!
- Daniel Keep (393/393) Jan 08 2007 Reading an article on Google's MapReduce inspired me to take another
- Vassily Gavrilyak (16/16) Feb 26 2007 Cool stuff, almost what I searched for. filter works like a charm.
- Daniel Keep (18/37) Feb 26 2007 Wow; it's been a while :P I think this is the first reply I got to that
- Daniel Keep (15/56) Feb 28 2007 map should now be fixed to return the actual type, and I've uploaded the
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
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
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
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
Daniel Keep <daniel.keep.lists gmail.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
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