Re: Ranges and Algorithms -- Templates, Delegates, or Ranges?
> Indeed. The solution to OP's problem is std.algorithm.map. Local
instantiation should take care of aliases that refer to local
symbols, so OP's original complaint about std.algorithm.map is
invalid (albeit for a subtle reason). The following code compiles as
expected:
import std.algorithm, std.stdio;
auto fun(int[] a)
{
auto y = 3;
auto m = map!((x) { return x < y; })(a);
return m;
}
void main()
{
auto a = [ 1, 2, 3, 4, 5 ];
auto m = fun(a);
writeln(m);
}
> Note how map's lambda refers to a symbol local to fun.
I... didn't know that works. Wow! And it also seems to work with
function pointers too. :)
D amazes me every day. :D
Thanks for making such a great language guys!!
Re: Ranges and Algorithms -- Templates, Delegates, or Ranges?
On 2/22/11 5:15 AM, Mafi wrote:
Am 22.02.2011 11:29, schrieb %u:
Having learned functional programming in Scheme a couple months ago, I
tried my hand at using map(), reduce(), and filter() in D:
int addend = 5;
map(delegate int(int x) { return x + addend; }, iota(1, 5));
but it didn't work. It turned out that map() actually took the mapper
as its _template_ argument, not as a function argument. Not too much of
a problem, it probably seemed to be...
except that it's a critical problem. It makes map(), reduce(),
filter(), etc. to become 10x less useful, because there's no way to
change
their behavior at runtime, depending on program's state.
I did never try and so I'm unsure but shouldn't you be able to give a
delegate variable as template parameter.
std.algorithms.map's parameter is an alias parameter so it should be
able alias your variable and use it's runtime value.
If it does not work this way it's a bug IMO.
Mafi
Indeed. The solution to OP's problem is std.algorithm.map. Local
instantiation should take care of aliases that refer to local symbols,
so OP's original complaint about std.algorithm.map is invalid (albeit
for a subtle reason). The following code compiles as expected:
import std.algorithm, std.stdio;
auto fun(int[] a)
{
auto y = 3;
auto m = map!((x) { return x < y; })(a);
return m;
}
void main()
{
auto a = [ 1, 2, 3, 4, 5 ];
auto m = fun(a);
writeln(m);
}
Note how map's lambda refers to a symbol local to fun.
Local instantiation, invented by Walter, is a very innovative feature -
perhaps one of D's most innovative. When a template is instantiated with
a local alias (as e.g. map is inside fun) it is in fact instantiated
within the function, so it has access to its locals.
As this is a new feature and a rather subtle one, it has bugs and
limitations. In fact the function above has a bug, it prints:
[false, false, false, false, true]
although it should print
[true, true, false, false, false]
But I'm 100% convinced this is the way to go. I just submitted a bug
report reduced from the code above, see
http://d.puremagic.com/issues/show_bug.cgi?id=5641.
Andrei
Re: Ranges and Algorithms -- Templates, Delegates, or Ranges?
Mafi wrote:
> Am 22.02.2011 11:29, schrieb %u:
>> Having learned functional programming in Scheme a couple months ago, I
>> tried my hand at using map(), reduce(), and filter() in D:
>>
>> int addend = 5;
>> map(delegate int(int x) { return x + addend; }, iota(1, 5));
>>
>> but it didn't work. It turned out that map() actually took the mapper as
>> its _template_ argument, not as a function argument. Not too much of a
>> problem, it probably seemed to be... except that it's a critical problem.
>> It makes map(), reduce(), filter(), etc. to become 10x less useful,
>> because there's no way to change their behavior at runtime, depending on
>> program's state.
>>
>
> I did never try and so I'm unsure but shouldn't you be able to give a
> delegate variable as template parameter.
> std.algorithms.map's parameter is an alias parameter so it should be
> able alias your variable and use it's runtime value.
> If it does not work this way it's a bug IMO.
>
> Mafi
yes it works: map!((int x) { return x + addend; })(iota(1, 5));
It's called local template instantiation iirc, and is restricted to global
templates (which map is).
Re: Ranges and Algorithms -- Templates, Delegates, or Ranges?
Am 22.02.2011 11:29, schrieb %u:
Having learned functional programming in Scheme a couple months ago, I tried my
hand at using map(), reduce(), and filter() in D:
int addend = 5;
map(delegate int(int x) { return x + addend; }, iota(1, 5));
but it didn't work. It turned out that map() actually took the mapper as its
_template_ argument, not as a function argument. Not too much of
a problem, it probably seemed to be...
except that it's a critical problem. It makes map(), reduce(), filter(), etc.
to become 10x less useful, because there's no way to change
their behavior at runtime, depending on program's state.
I did never try and so I'm unsure but shouldn't you be able to give a
delegate variable as template parameter.
std.algorithms.map's parameter is an alias parameter so it should be
able alias your variable and use it's runtime value.
If it does not work this way it's a bug IMO.
Mafi
Ranges and Algorithms -- Templates, Delegates, or Ranges?
Having learned functional programming in Scheme a couple months ago, I tried my
hand at using map(), reduce(), and filter() in D:
int addend = 5;
map(delegate int(int x) { return x + addend; }, iota(1, 5));
but it didn't work. It turned out that map() actually took the mapper as its
_template_ argument, not as a function argument. Not too much of
a problem, it probably seemed to be...
except that it's a critical problem. It makes map(), reduce(), filter(), etc.
to become 10x less useful, because there's no way to change
their behavior at runtime, depending on program's state.
This was disappointing, but it wasn't like I couldn't write a better version of
it, so I did:
static T2[] map(T2, T1)(scope T2 delegate(T1) mapper, T1[] arr)
{
auto result = new T2[arr.length];
foreach (i, item; arr) { result[i] = mapper(item); }
return result;
}
except then I quickly realized that this was array-based, and useless for
ranges. So I wrote my own MapRange struct (which I didn't paste
here) and map() function:
static auto map(TFn, T...)(TFn map, T args)
if (isCallable!(TFn) && T.length > 0
&& allSatisfy!(isInputRange, T))
{ return MapRange!(TFn, T)(map, args); }
Everything seemed solved until today, when I realized something critical: the
mapper is no longer a 'scope' variable, and will require a heap
allocation each time a lambda with closure is created.
Of course, lambdas with closures are critical in functional programming, and
one of the reasons I moved to D was precisely features like the
'scope' keyword, that allowed you to avoid heap allocations. But I couldn't
make this a scope variable, because the delegate reference is
obviously escaped from the function.
So my question is, what's the solution to these needs? Do we really need three
versions of every function like map()? After all, we should be
able to perform **any** of the following, depending on the situation:
1. Call map() with the function as a template argument, the way it currently
works in std.algorithm. This is necessary to allow the compiler
to infer the types; otherwise, if we passed the function addresses, we'd have
to instantiate the template for the mapper manually, like:
map(&mapper!(int[typeof(SomeExpression)]), myRange);
2. Call map() with a *scoped* lambda that has a closure. This is critical to
functional programming, but at the same time, we need to somehow
prevent a reference to the mapper from escaping; otherwise, it will trigger a
heap allocation, which can be costly in loops. Of course, this
means that the mapping would have to occur entirely _inside_ the map() function
(because the delegate will no longer be accessible), and so
it means we would either need to pass it a sink() delegate, or we would need to
aggregate the results into an array. Neither is pretty, but
this feature is needed, so I don't know what a good solution is.
3. Call map() with a *range* and some kind of lambda, and have it return
another range that maps the original. This prevents the two issues
in #2 (regarding passing a sink or aggregating the results), but it would cause
a heap allocation.
Ultimately, since there's no universal solution and because all three of these
situations are useful in many cases, it seems to me that we
really need *three* versions of every higher-order function.
What do you think? Is there a better solution?
Thanks!
