www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - merging map/filter/reduce/... in D

reply glathoud <glathoud yahoo.fr> writes:
Hello,

I am a D beginner, please excuse me if these questions are 
irrelevant.

I had a look at this post:
http://forum.dlang.org/post/aarldotsgluwdgteentl forum.dlang.org

Looking at the source code of compose!:
https://github.com/D-Programming-Language/phobos/blob/v2.070.0/std/functional.d#L889

I have the impression that function implementations are not 
merged:

     return fun0(fun1(a));

For example, fun1(a) outputs a temporary array, which is then 
used as input for fun0. Merging the implementations of fun0 and 
fun1 would eliminate the need for a temporary array.

Two questions:
* is my understanding correct?
* would be a "code-merging" approach (e.g. transducer) feasible 
in D?

Best regards,
Guillaume
Jan 28 2016
parent reply Ivan Kazmenko <gassa mail.ru> writes:
On Friday, 29 January 2016 at 07:17:04 UTC, glathoud wrote:

 I have the impression that function implementations are not 
 merged:

     return fun0(fun1(a));

 For example, fun1(a) outputs a temporary array, which is then 
 used as input for fun0. Merging the implementations of fun0 and 
 fun1 would eliminate the need for a temporary array.


If fun1(a) indeed eagerly returns a temporary array, you are 
right.  Still, if the author of fun1 cares to be generic enough, 
it usually returns a lazy range: a struct with front, empty and 
popFront.  Whenever fun0 requests the next element of the range, 
fun1 calculates it and gives it away (returns front and calls 
popFront).

Note that all this - which function calls which other function - 
is known at compile time.  To merge the actual code of fun0 and 
popFront of fun1's return value is then the job for the optimizer 
pass, it's basically inlining.

Note that a temporary array can theoretically also be optimized 
out by an advanced optimizer.

Ivan Kazmenko.
Jan 28 2016
parent reply glathoud <glathoud yahoo.fr> writes:
Thanks. I am glad be wrong on that one.

I had a look at map & filter in the source code ; pleased to see 
they're lazily implemented!

map
https://github.com/D-Programming-Language/phobos/blob/master/std/algorithm/iteration.d#L425

filter
https://github.com/D-Programming-Language/phobos/blob/master/std/algorithm/iteration.d#L924
I had to look for FilterResult!
https://github.com/D-Programming-Language/phobos/blob/master/std/algorithm/iteration.d#L979

Small remark: One could make the laziness of filter a bit more 
clear in the doc though - at least for newbies like me.
http://dlang.org/phobos/std_algorithm_iteration.html

Best regards,
Guillaume
Jan 29 2016
parent cym13 <cpicard openmailbox.org> writes:
On Friday, 29 January 2016 at 08:06:14 UTC, glathoud wrote:

 Thanks. I am glad be wrong on that one.

 I had a look at map & filter in the source code ; pleased to 
 see they're lazily implemented!

 map
 https://github.com/D-Programming-Language/phobos/blob/master/std/algorithm/iteration.d#L425

 filter
 https://github.com/D-Programming-Language/phobos/blob/master/std/algorithm/iteration.d#L924
 I had to look for FilterResult!
 https://github.com/D-Programming-Language/phobos/blob/master/std/algorithm/iteration.d#L979

 Small remark: One could make the laziness of filter a bit more 
 clear in the doc though - at least for newbies like me.
 http://dlang.org/phobos/std_algorithm_iteration.html

 Best regards,
 Guillaume


While it's not entirely true because one can implement a non-lazy 
range, any time you see the word "range" in the documentation you 
should think that it is lazy. Ranges are an important concept in 
D so we usually don't bother explaining it in the doc. You can 
read about it here if you need to: 
http://ddili.org/ders/d.en/ranges.html and 
http://dlang.org/phobos/std_range.html
Jan 29 2016