January 31, 2011
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
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
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
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
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
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
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
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
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
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