View mode: basic / threaded / horizontal-split · Log in · Help
May 21, 2008
std.algorithm issue
Hi,

I send Andrei a suggestion a while back for improving the map! template in
std.algorithm. The change was, when map! is supplied a function alias, its
return type should be a range of the return type of the function. This is much
like Python's map statement and lets you do things like this:

string[] string_list = //integer strings from somewhere
auto intrange = map!(atoi)(split(string_list, ","));

That has worked out well. This time I have a question about both the reduce!
and map! templates. I would like to do something like this:

reduce!(Merge)(/*string[] list of files*/);

but where Merge is a member function of a class. When I try this I get:

c:\dmd\bin\..\src\phobos\std\algorithm.d(185): Error: need 'this' to access
member Merge

When I try

reduce!(this.Merge)(/*same string[]*/);

I get:

d_dedup.d(153): template std.algorithm.reduce(F...) cannot deduce template
function from argument types !(this.Merge)(i
variant(char)[],invariant(char)[][])

Is it possible to map! or reduce! a member function or delegate against a
range? If so how would I do that?

Thanx,

Brian
May 21, 2008
Re: std.algorithm issue
Reply to Brian,


> Is it possible to map! or reduce! a member function or delegate
> against a range? If so how would I do that?
> 

I think not because the context pointer "this" must be carried somehow at 
runtime. It might, however, be possible to make a version of map! that takes 
a delegate and uses that.
May 21, 2008
Re: std.algorithm issue
Brian Myers:
> Is it possible to map! or reduce! a member function or delegate against a
> range? If so how would I do that?

Do you mean something like this?

import d.func: map, xrange, putr;

class Foo {
   int sqr(int x) { return x * x; }
}

class Baz {
   float div2(int x) { return x / 2; }
}

void main() {
   auto f1 = new Foo;
   putr( map(&f1.sqr, xrange(10)) );

   auto b1 = new Baz;
   putr( map(&b1.div2, xrange(10)) );
}

Output:
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
[0.0, 0.0, 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 4.0, 4.0]

Bye,
bearophile
May 22, 2008
Re: std.algorithm issue
bearophile Wrote:

> Brian Myers:
> > Is it possible to map! or reduce! a member function or delegate against a
> > range? If so how would I do that?
> 
> Do you mean something like this?
> 
> import d.func: map, xrange, putr;
> 
> class Foo {
>     int sqr(int x) { return x * x; }
> }
> 
> class Baz {
>     float div2(int x) { return x / 2; }
> }
> 
> void main() {
>     auto f1 = new Foo;
>     putr( map(&f1.sqr, xrange(10)) );
> 
>     auto b1 = new Baz;
>     putr( map(&b1.div2, xrange(10)) );
> }
> 
> Output:
> [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
> [0.0, 0.0, 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 4.0, 4.0]
> 
> Bye,
> bearophile

import std.algorithm;

struct A
{
   int Merge(int) { return 0; }
}

void main(string[] args)
{
   A a;
   map!((int x) { return a.Merge(x); })([1, 2, 3]);
}

I did not install bearophile library. It would be interesting to see what the speed is of std.algorithm and d.func. Dee Girl
May 22, 2008
Re: std.algorithm issue
I think this is exactly what I wanted. I needed to use the address of operator along with the instance reference.

Wow some of the things you can do in D (like Dee Girl's post) are almost as esoteric and obscure as Felix!

Thanx everyone,

Brian

bearophile Wrote:

> Brian Myers:
> > Is it possible to map! or reduce! a member function or delegate against a
> > range? If so how would I do that?
> 
> Do you mean something like this?
> 
> import d.func: map, xrange, putr;
> 
> class Foo {
>     int sqr(int x) { return x * x; }
> }
> 
> class Baz {
>     float div2(int x) { return x / 2; }
> }
> 
> void main() {
>     auto f1 = new Foo;
>     putr( map(&f1.sqr, xrange(10)) );
> 
>     auto b1 = new Baz;
>     putr( map(&b1.div2, xrange(10)) );
> }
> 
> Output:
> [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
> [0.0, 0.0, 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 4.0, 4.0]
> 
> Bye,
> bearophile
May 22, 2008
Re: std.algorithm issue
Brian Myers Wrote:

> I think this is exactly what I wanted. I needed to use the address of operator along with the instance reference.
> 
> Wow some of the things you can do in D (like Dee Girl's post) are almost as esoteric and obscure as Felix!

In fact it is simpler. It is just bug in dmd. The following code works.

import std.algorithm;

struct A
{
   int Merge(int) { return 0; }
}

void main(string[] args)
{
   A a;
   auto fun = &a.Merge;
   map!(fun)([1, 2, 3]);
}

It is a problem that compiler can work with fun but not direct with &a.Merge. It is good idea to report bug to Walter. Such bug limits power of higher order functions. Thank you, Dee Girl
May 22, 2008
Re: std.algorithm issue
Hmmm, for some reason this is still not working. It must be because the reduce statement is itself within a method of the same class as Merge. Here's what I've got.

class ExternalSorter : Sorter {
.
.
.

   string Merge(string f1, string f2) {
   .
   .
   .
   }

   override void Sort() {
   .
   .
   .
       auto mrg = &Merge;
       retfile = (chunk_list.length == 1 ? chunk_list[0] :
                  reduce!(mrg)(chunk_list[0], chunk_list[1..$]));
   .
   .
   .
   }

And here's the error message:
c:\dmd\bin\..\src\phobos\std\algorithm.d(283): template std.algorithm.reduce(F...) is not a function template
d_dedup.d(191): template std.algorithm.reduce(F...) cannot deduce template function from argument types !(&this.Merge)(i
nvariant(char)[],invariant(char)[][])
d_dedup.d(191): Error: incompatible types for ((this.chunk_list[cast(uint)0]) ? ((reduce(F...))((this.chunk_list[cast(ui
nt)0]),this.chunk_list[cast(uint)1..__dollar]))): 'invariant(char)[]' and 'int'

This is the closest I've gotten yet. I've tried a number of other ways with the address of operator, etc...

Brian



Dee Girl Wrote:

> Brian Myers Wrote:
> 
> > I think this is exactly what I wanted. I needed to use the address of operator along with the instance reference.
> > 
> > Wow some of the things you can do in D (like Dee Girl's post) are almost as esoteric and obscure as Felix!
> 
> In fact it is simpler. It is just bug in dmd. The following code works.
> 
> import std.algorithm;
> 
> struct A
> {
>     int Merge(int) { return 0; }
> }
> 
> void main(string[] args)
> {
>     A a;
>     auto fun = &a.Merge;
>     map!(fun)([1, 2, 3]);
> }
> 
> It is a problem that compiler can work with fun but not direct with &a.Merge. It is good idea to report bug to Walter. Such bug limits power of higher order functions. Thank you, Dee Girl
>
May 22, 2008
Re: std.algorithm issue
Brian Myers Wrote:

> Hmmm, for some reason this is still not working. It must be because the reduce statement is itself within a method of the same class as Merge. Here's what I've got.

This code does not work:

#!/home/yasuko/bin/rdmd -O -release
import std.algorithm;

class Sorter {}

class ExternalSorter : Sorter {
   string Merge(string f1, string f2) {
       return f1 ~ f2;
   }

   void Sort() {
       string[] chunk_list = [ "a", "b" ];
       auto mrg = &Merge;
       auto retfile = reduce!(mrg)(chunk_list[0], chunk_list[1..$]);
   }
}

void main(string[] args)
{
   auto s = new ExternalSorter;
   s.Sort;
}

But I know how to make it work because I look at the error message. You go to std.algorithm and make NxNHelper from private to public. Then inside NxNHelper also make For from private to public. Then code works.

Maybe bug report to Walter is necessary. Private should work because lookup is in correct module. It is bug in compiler not library. Can you please? Thank you, Dee Girl
May 22, 2008
Re: std.algorithm issue
Brian Myers:
>     string Merge(string f1, string f2) {
>     .
>     .
>     .
>     }

I don't exactly know what you are trying to do, but using s1~s2 to merge an array of strings is probably O(n^2) if the higher order functions you use (or the compiler) aren't smart enough.
There is a join() function in std.string that is O(1), and there's a faster version of it in my libs (and probably in Tango too).

Bye,
bearophile
May 22, 2008
Re: std.algorithm issue
I'll look into submitting a bug report to Walter. Thanx bearophile.

Dee Girl, I'm actually not merging strings. The strings are file names. Merge is the merge phase for an external sort. In my next project I'll use map to do something like what you're talking about. I'll have to test the difference between map!-ing a custom function and doing join, and using reduce and a custom function.

Thanx to both of you.

Brian

bearophile Wrote:

> Brian Myers:
> >     string Merge(string f1, string f2) {
> >     .
> >     .
> >     .
> >     }
> 
> I don't exactly know what you are trying to do, but using s1~s2 to merge an array of strings is probably O(n^2) if the higher order functions you use (or the compiler) aren't smart enough.
> There is a join() function in std.string that is O(1), and there's a faster version of it in my libs (and probably in Tango too).
> 
> Bye,
> bearophile
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home