www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - inplace_merge, nWayUnion

reply bearophile <bearophileHUGS lycos.com> writes:
How do you perform with Phobos2 the C++ STL algorithm inplace_merge()?
http://www.cplusplus.com/reference/algorithm/inplace_merge/
If it is not present yet in Phobos2, then I'd like it eventually to be added.

-------------------

Regarding std.algorithm.nWayUnion, how do you merge iterables of different type
that yield the same type?


import std.stdio, std.algorithm, std.range;
void main() {
    auto r1 = map!q{a * 2}(iota(10));
    auto r2 = map!q{a * 5}(iota(15));
    auto r12 = nWayUnion([r1, r2]); // can't work
    writeln(r12);
}


A differently designed nWayUnion() allows me to use ranges of different type:

nWayUnion(r1, r2, r3, ...)

Bye,
bearophile
Aug 29 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 08/29/2010 06:00 PM, bearophile wrote:

 How do you perform with Phobos2 the C++ STL algorithm inplace_merge()?
 http://www.cplusplus.com/reference/algorithm/inplace_merge/
 If it is not present yet in Phobos2, then I'd like it eventually to be added.

 -------------------

 Regarding std.algorithm.nWayUnion, how do you merge iterables of different
type that yield the same type?


 import std.stdio, std.algorithm, std.range;
 void main() {
      auto r1 = map!q{a * 2}(iota(10));
      auto r2 = map!q{a * 5}(iota(15));
      auto r12 = nWayUnion([r1, r2]); // can't work
      writeln(r12);
 }


 A differently designed nWayUnion() allows me to use ranges of different type:

 nWayUnion(r1, r2, r3, ...)

 Bye,
 bearophile


I haven't implemented inplace_merge yet. About nWayUnion - great idea, 
but don't ever come back with a bug report "nWayUnion is difficult to 
understand".

Andrei
Aug 29 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Andrei:

 but don't ever come back with a bug report "nWayUnion is difficult to 
 understand".


Iff nWayUnion will be difficult to undertand I will write that nWayUnion is
difficult to undertand.

Bye,
bearophile
Aug 30 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 8/30/10 5:59 PDT, bearophile wrote:

 Andrei:

 but don't ever come back with a bug report "nWayUnion is difficult to
 understand".


 Iff nWayUnion will be difficult to undertand I will write that nWayUnion is
difficult to undertand.

 Bye,
 bearophile


My point is you need to understand that you are making contradictory 
requests.

Andrei
Aug 30 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

 My point is you need to understand that you are making contradictory 
 requests.


I understand your point, but I think you are wrong. I think that the usage and
semantics of a nWayUnion(r1, r2, ...) are simple to understand and use
(regardless the complexity of its signature).

You use it as:
foreach (x; nWayUnion(r1, r2))
Or as:
array(nWayUnion(r1, r2, r3))
etc. This is a natural enough.

Bye,
bearophile
Aug 30 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 8/30/10 14:06 PDT, bearophile wrote:

 Andrei Alexandrescu:

 My point is you need to understand that you are making contradictory
 requests.


 I understand your point, but I think you are wrong. I think that the usage and
semantics of a nWayUnion(r1, r2, ...) are simple to understand and use
(regardless the complexity of its signature).

 You use it as:
 foreach (x; nWayUnion(r1, r2))
 Or as:
 array(nWayUnion(r1, r2, r3))
 etc. This is a natural enough.

 Bye,
 bearophile


I'd be indeed wrong to claim that. What I was saying is that in a past 
bug report you complained that find() is too hard to understand. That 
was because find() supported things like heterogeneous ranges and 
finding more things than one in a single-pass manner. Making nWayUnion 
accept heterogeneous ranges would no doubt increase its implementation 
complexity - probably worth it given the increased leverage. All I'm 
saying is, please remember that solutions that are at the same time 
simpler and more general are in short supply.

Andrei
Aug 30 2010
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Andrei:

Sorry for my late answer, yesterday I was very busy.



What I was saying is that in a past bug report you complained that find() is
too hard to understand.<


An in a later post I have explained what in my opinion it can be done to
improve the situation (this is not a fully good answer, but it gives a good
idea of what I was thinking):
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=113555



That was because find() supported things like heterogeneous ranges and finding
more things than one in a single-pass manner.<


The main problem of find() is in what it returns, not in what it takes as
arguments.



Making nWayUnion accept heterogeneous ranges would no doubt increase its
implementation complexity - probably worth it given the increased leverage.<


My idea probably will make it more complex internally. But it's library code,
so what's more important is how complex its usage is, not its internal
complexity.

I have had to use nWayUnion three times so far, and in two times I was in need
to perform a 2-way or 3-way merge of lazy iterables, and I have had troubles in
using nWayUnion, so much that I have written my own merge. So I think currently
nWayUnion is not so useful because it is too much limited.



All I'm saying is, please remember that solutions that are at the same time
simpler and more general are in short supply.<


"simpler" means many different things. Your library code may be simple to use
and to understand and yet be complex internally. The point of a library of
algorithms is to make user code shorter and clean and efficient. I agree that
designing a good library is a job of balancing some opposed needs, but this is
not my fault, it's the nature of the game :-)


If you don't want to modify nWayUnion(), there is another solution, to not
modify nWayUnion and to create an adaptor:

nWayUnion(Sequence(r1, r2, r3))

Sequence() takes as arguments one or more iterables, it's like a Tuple and it
supports random access with [], but its template constraint assures that all
the given iterables yield the same type:

Sequence(iota(10), [20, 30])  this is OK.

Sequence(iota(10), [20.5, 30.5])  this is not OK.

So:
Sequence(r1, r2, r3)[0].front() returns what r1.front() returns.


I don't know if this is a good idea. I prefer the simpler syntax nWayUnion(r1,
r2, ...)

Bye,
bearophile
Aug 31 2010