View mode: basic / threaded / horizontal-split · Log in · Help
January 31, 2011
Partially instantiating templates?
I'm building a function (or template or whatever, really) that is 
related to map and minPos in std.algorithm. Basically, it's the 
standard mathematical argmin, except that it also returns min. It looks 
something like this:

 auto minArg(alias fun, Range, T)(Range range, out T minVal) {
     ...
 }

Already there may be issues -- the return type should be 
ElementType(range) and T should be the return type of fun ... but it 
works. (Suggestions on these issues are welcome, but that's not really 
the main point here.)

The thing is, because I'm also returning the actual value, I'd rather 
not use the strategy of std.algorithm.minPos, which asks you to use an 
inverted function to get maxPos; instead, I'd like an explicit maxArg 
function. My idea was to have a common, more general optArg, which took 
an operator ("<" or ">") as a compile-time argument. Then I could do 
something like

 alias optArg!"<" minArg;
 alias optArg!">" maxArg;

Then, at some *later* time, I might want to do something like:

 alias maxArg!((v) {return dist(u,v);}) farthest;

(By the way: For some reason, I'm not allowed to use curry(dist,u) 
instead of the lambda here, it seems. Any insights on that? Would have 
been nice to use "d(u,a)" as well -- as I do use unaryFunc on the fun 
argument. That doesn't work either, though...)

I've been able to make either one of these two pieces of functionality 
work with some twiddling and nesting (i.e., *either* instantiating 
optArg into minArg/maxArg, *or* instantiating explicitly defined 
minArg/maxArg into specialized functions) but combining them has so far 
eluded me (unless I start fiddling with strinc constants and mixin(), 
which seems excessively hacky for such a simple thing).

Any ideas/suggestions? I'm sure I'm missing something obvious ... 
(Perhaps even existing functionality for minArg/maxArg -- although the 
general question still stands.)

-- 
Magnus Lie Hetland
http://hetland.org
January 31, 2011
Re: Partially instantiating templates?
Magnus Lie Hetland <magnus@hetland.org> wrote:

> I'm building a function (or template or whatever, really) that is  
> related to map and minPos in std.algorithm. Basically, it's the standard  
> mathematical argmin, except that it also returns min. It looks something  
> like this:
>
>   auto minArg(alias fun, Range, T)(Range range, out T minVal) {
>       ...
>   }
>
> Already there may be issues -- the return type should be  
> ElementType(range) and T should be the return type of fun ... but it  
> works. (Suggestions on these issues are welcome, but that's not really  
> the main point here.)

ElementType!Range minArg( alias fun, Range )( Range range, out  
ReturnType!fun ) {
    ...
}

Might I also ask why you use an out parameter instead of a tuple return?


> The thing is, because I'm also returning the actual value, I'd rather  
> not use the strategy of std.algorithm.minPos, which asks you to use an  
> inverted function to get maxPos; instead, I'd like an explicit maxArg  
> function. My idea was to have a common, more general optArg, which took  
> an operator ("<" or ">") as a compile-time argument. Then I could do  
> something like
>
>   alias optArg!"<" minArg;
>   alias optArg!">" maxArg;
>
> Then, at some *later* time, I might want to do something like:
>
>   alias maxArg!((v) {return dist(u,v);}) farthest;

D currently does not support template currying to any good degree.

However, there is at least one library out there that does that for you:

http://www.dsource.org/projects/dranges

In the file templates.d, there is the template CurryTemplate, which
rewrites a template to a set of nested templates. This would allow you
to partially instantiate a template, and add more parameters as you go.


> I've been able to make either one of these two pieces of functionality  
> work with some twiddling and nesting (i.e., *either* instantiating  
> optArg into minArg/maxArg, *or* instantiating explicitly defined  
> minArg/maxArg into specialized functions) but combining them has so far  
> eluded me (unless I start fiddling with strinc constants and mixin(),  
> which seems excessively hacky for such a simple thing).

dranges' templates.CurryTemplate should take care of some of your problems.
Not sure if it will fix them all.



-- 
Simen
January 31, 2011
Re: Partially instantiating templates?
On 2011-01-31 12:55:07 +0100, Simen kjaeraas said:

> ElementType!Range minArg( alias fun, Range )( Range range, out 
> ReturnType!fun ) {
>      ...
> }

Aaaah. I guess I tried ElementType(Range), forgetting to make it a 
compile-time parameter. Thanks. (Hadn't seen ReturnType; makes sense :)

> Might I also ask why you use an out parameter instead of a tuple return?

Well... I had a tuple return at first, but one of the advantages of 
returning multiple values that I'm accustomed to is the ability to 
assign to multiple variables, such as

 arg, val = minArg(...)

(Yeah, I'm a Python guy... ;)

As far as I can see, you can't do that here? Using result[0] and 
result[1] or the like, or assigning separately to two variables just 
seemed more cumbersome. Then again, I could use a tuple with named 
members, I guess. In your opinion, what would be the prettiest (in D 
terms) way of doing this?

[snip]
> D currently does not support template currying to any good degree.

OK. Well, I guess I don't really need it. Still trying to get a feel 
for what's "normal" D :)

> However, there is at least one library out there that does that for you:
> 
> http://www.dsource.org/projects/dranges
> 
> In the file templates.d, there is the template CurryTemplate, which
> rewrites a template to a set of nested templates. This would allow you
> to partially instantiate a template, and add more parameters as you go.

I see. I actually don't mind writing nested templates myself -- but for 
some reason I couldn't get them to work properly. (D kept complaining 
about declarations vs instances, and the like; I guess I'll have a look 
at how dranges does it.)

>> I've been able to make either one of these two pieces of functionality 
>> work with some twiddling and nesting (i.e., *either* instantiating 
>> optArg into minArg/maxArg, *or* instantiating explicitly defined 
>> minArg/maxArg into specialized functions) but combining them has so far 
>> eluded me (unless I start fiddling with strinc constants and mixin(), 
>> which seems excessively hacky for such a simple thing).
> 
> dranges' templates.CurryTemplate should take care of some of your problems.
> Not sure if it will fix them all.

OK, thanks.

By the way, if you have suggestions for other more "D-like" ways of 
encapsulating this functionality (basically a linear scan for an 
element that yields a max/min value for a given expression), I'd be 
interested to hear that too. The best way to solve a problem is often 
to rephrase it :)

-- 
Magnus Lie Hetland
http://hetland.org
January 31, 2011
Re: Partially instantiating templates?
Magnus Lie Hetland <magnus@hetland.org> wrote:

>> Might I also ask why you use an out parameter instead of a tuple return?
>
> Well... I had a tuple return at first, but one of the advantages of  
> returning multiple values that I'm accustomed to is the ability to  
> assign to multiple variables, such as
>
>   arg, val = minArg(...)
>
> (Yeah, I'm a Python guy... ;)
>
> As far as I can see, you can't do that here? Using result[0] and  
> result[1] or the like, or assigning separately to two variables just  
> seemed more cumbersome. Then again, I could use a tuple with named  
> members, I guess. In your opinion, what would be the prettiest (in D  
> terms) way of doing this?

You might want to try more from dranges - the reftuple:

_(arg,val) = minArg(...);

It resides in dranges.reftuple, and still has some warts, but it
usually works.

This is also a possible implementation (coded in about 5 minutes, gives
no nice error messages, but it seems to work :p ):


import std.typetuple;
import std.typecons;

template TypeOf( alias T ) {
    alias typeof( T ) TypeOf;
}

@property void _( T... )( Tuple!( staticMap!(TypeOf, T) ) args ) {
    foreach ( i, e; T ) {
        e = args[i];
    }
}

void main( ) {
    int a, b;
    _!(a,b) = tuple(b,a+b); // fibonacci
}


> I see. I actually don't mind writing nested templates myself -- but for  
> some reason I couldn't get them to work properly. (D kept complaining  
> about declarations vs instances, and the like; I guess I'll have a look  
> at how dranges does it.)

Yeah. D has the nice Eponymous Template Trick, but it sadly only works
for one level. :(


> By the way, if you have suggestions for other more "D-like" ways of  
> encapsulating this functionality (basically a linear scan for an element  
> that yields a max/min value for a given expression), I'd be interested  
> to hear that too. The best way to solve a problem is often to rephrase  
> it :)

So you have to test for every single element of the range?

If so, I think this works:


module foo;

import std.typecons;
import std.functional;
import std.array;

template optArg( alias pred ) {
    template optArg( alias fn ) {
        auto optArg( Range )( Range r ) {
            alias binaryFun!pred predicate;
            alias unaryFun!fn func;

            auto result = tuple( r.front, func( r.front ) );
            foreach ( e; r ) {
                auto tmp = func( e );
                if ( predicate( e, result[1] ) ) {
                    result = tuple( e, tmp );
                }
            }
            return result;
        }
    }
}

void main( ) {
    alias optArg!"a<b" minArg;
    alias minArg!"a" foo;
    assert( foo( [5,2,1,3] ) == tuple(1,1) );
}



-- 
Simen
January 31, 2011
Re: Partially instantiating templates?
On 2011-01-31 15:50:41 +0100, Simen kjaeraas said:

> You might want to try more from dranges - the reftuple:
> 
> _(arg,val) = minArg(...);
[snip]
> This is also a possible implementation (coded in about 5 minutes, gives
> no nice error messages, but it seems to work :p ):

Thanks :)

> Yeah. D has the nice Eponymous Template Trick, but it sadly only works
> for one level. :(

Right :-/

> So you have to test for every single element of the range?

Yup.

> If so, I think this works:

Thanks. Hm. The nesting does seem similar to how I did it, but I guess 
there must be some crucial difference ;-)

At the moment, I'm using a mixing to create the min and max templates 
(as rather large strings). Probably not ideal.

Thanks!

-- 
Magnus Lie Hetland
http://hetland.org
January 31, 2011
Re: Partially instantiating templates?
On 1/31/11, Simen kjaeraas <simen.kjaras@gmail.com> wrote:
>
> module foo;
>
> import std.typecons;
> import std.functional;
> import std.array;
>
> template optArg( alias pred ) {
>      template optArg( alias fn ) {
>          auto optArg( Range )( Range r ) {
>              alias binaryFun!pred predicate;
>              alias unaryFun!fn func;
>
>              auto result = tuple( r.front, func( r.front ) );
>              foreach ( e; r ) {
>                  auto tmp = func( e );
>                  if ( predicate( e, result[1] ) ) {
>                      result = tuple( e, tmp );
>                  }
>              }
>              return result;
>          }
>      }
> }
>
> void main( ) {
>      alias optArg!"a<b" minArg;
>      alias minArg!"a" foo;
>      assert( foo( [5,2,1,3] ) == tuple(1,1) );
> }
>

Damn! That's pretty nice, I didn't know we could nest with the
eponymous trick. This could be quite useful, thanks.
January 31, 2011
Re: Partially instantiating templates?
Andrej Mitrovic <andrej.mitrovich@gmail.com> wrote:

> On 1/31/11, Simen kjaeraas <simen.kjaras@gmail.com> wrote:
>>
>> module foo;
>>
>> import std.typecons;
>> import std.functional;
>> import std.array;
>>
>> template optArg( alias pred ) {
>>      template optArg( alias fn ) {
>>          auto optArg( Range )( Range r ) {
>>              alias binaryFun!pred predicate;
>>              alias unaryFun!fn func;
>>
>>              auto result = tuple( r.front, func( r.front ) );
>>              foreach ( e; r ) {
>>                  auto tmp = func( e );
>>                  if ( predicate( e, result[1] ) ) {
>>                      result = tuple( e, tmp );
>>                  }
>>              }
>>              return result;
>>          }
>>      }
>> }
>>
>> void main( ) {
>>      alias optArg!"a<b" minArg;
>>      alias minArg!"a" foo;
>>      assert( foo( [5,2,1,3] ) == tuple(1,1) );
>> }
>>
>
> Damn! That's pretty nice, I didn't know we could nest with the
> eponymous trick. This could be quite useful, thanks.

You can only do that using aliases.

-- 
Simen
January 31, 2011
Re: Partially instantiating templates?
Hm. Using code quite similar to you, supplying a lambda in the second 
aliasing, I get this error:

something.d(93): Error: template instance cannot use local 
'__dgliteral2(__T3)' as parameter to non-global template optArg(alias 
fun)

It seems it's explicitly objecting to what I want it to do...

Using optArg!"a", for example, works just fine -- but the whole point 
was to include some local state. Using local functions worked (I 
think...?) when I had a global template.

It seems D's compile-time computation system is less straightforward 
than I thought :)

-- 
Magnus Lie Hetland
http://hetland.org
January 31, 2011
Re: Partially instantiating templates?
Magnus Lie Hetland <magnus@hetland.org> wrote:

> Hm. Using code quite similar to you, supplying a lambda in the second  
> aliasing, I get this error:
>
> something.d(93): Error: template instance cannot use local  
> '__dgliteral2(__T3)' as parameter to non-global template optArg(alias  
> fun)
>
> It seems it's explicitly objecting to what I want it to do...
>
> Using optArg!"a", for example, works just fine -- but the whole point  
> was to include some local state. Using local functions worked (I  
> think...?) when I had a global template.
>
> It seems D's compile-time computation system is less straightforward  
> than I thought :)

This is a bug. Please report it.

-- 
Simen
January 31, 2011
Re: Partially instantiating templates?
On 1/31/11, Simen kjaeraas <simen.kjaras@gmail.com> wrote:
> You can only do that using aliases.
>

Yeah. I was just experimenting for the last half hour. I was hoping to
make it easier to make an alias to a nested template using the
eponymous trick. But it doesn't work at all. All I could come up with
is this trickery:

template optArg( alias pred )
{
   static class optArg2(alias fn)
   {
       static auto optArg3( Range )( Range r )
       {
           alias binaryFun!pred predicate;
           alias unaryFun!fn func;

           auto result = tuple( r.front, func( r.front ) );
           foreach ( e; r )
           {
               auto tmp = func( e );
               if ( predicate( e, result[1] ) )
               {
                   result = tuple( e, tmp );
               }
           }
           return result;
       }

       static auto opCall(Range)(Range r)
       {
           return optArg3!(Range)(r);
       }
   }

   alias optArg2 optArg;
}

void main( )
{
   alias optArg!("a<b").optArg!("a") foo;
   assert( foo( [5,2,1,3] ) == tuple(1,1) );
}

Of course, this won't work anymore:
   alias optArg!"a<b" minArg;
   alias minArg!"a" foo;
   assert( foo( [5,2,1,3] ) == tuple(1,1) );
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home