www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - What functions could be added to std.algorithm?

reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
A few hours ago, in a thread on D contracts, KennyTM~ said:

 BTW, there should be an 'all = reduce!"a&&b"' and 'any = reduce!"a||b"' in
std.algorithm, but short-circuited.

I agree. all() and any/some() are both easy to code, I think, and useful in many situations. In D, they could work on any input range, with any predicate. As they do not return ranges, I suggest to put them in std.algo. A possible implementation: bool all(alias pred = "a", R)(R range) if (isInputRange!R) { foreach(elem; range) { if (!unaryFun!predicate(elem)) return false; } return true; } Yeah, I know, std.algorithm is already quite big. In fact, I'm all for cutting it or using a (gasp) two-level hierarchy in Phobos, but I admit having no readily usable scheme to propose. algorithm.find, for all find-related thingies algorithm.sort, etc Map, filter and reduce could be put in std.range. At least, it's logical that map and filter, which are higher-level ranges, be put in std.range. Reduce, I don't know. * I also suggest that takeWhile!(predicate)(range) be added to ... well to where take() is right now. takeWhile lazily returns the elements of range as long as predicate holds for the front element. Then, it stops. http://d.puremagic.com/issues/show_bug.cgi?id=4535 * drop/dropWhile or popFrontNWhile (ugly name, I know) are also useful: they consume n elements from a range, or all elements as long a a predicate holds. Other low-level possibilities: * flatten, that takes a range of ranges (of any depth?) and lazily flatten them. It's very useful when a previous map application produces a range of ranges. btw, many PL that have a map construct also have a flatMap that compose flatten and map. * iterate!fun(seed) that produces the infinite range seed, fun(seed), fun(fun(seed), ... Hmm, I know realize that most of what I suggest should go into std.range more than in std.algorithm... Philippe
Aug 01 2010
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Philippe Sigaud (philippe.sigaud gmail.com)'s article
 A few hours ago, in a thread on D contracts, KennyTM~ said:
 BTW, there should be an 'all = reduce!"a&&b"' and 'any = reduce!"a||b"' in


 I agree. all() and any/some() are both easy to code, I think, and useful in
many

 In D, they could work on any input range, with any predicate. As they do not

 A possible implementation:
 bool all(alias pred = "a", R)(R range) if (isInputRange!R)
 {
     foreach(elem; range)
     {
         if (!unaryFun!predicate(elem)) return false;
     }
     return true;
 }
 Yeah, I know, std.algorithm is already quite big. In fact, I'm all for cutting

 but I admit having no readily usable scheme to propose.
  algorithm.find, for all find-related thingies
  algorithm.sort,
 etc

Please, no. This is why I hate Tango and Java. It's too hard to find what you need, and you have to write too much import declaration boilerplate. I love Phobos's flat, simple, even if at times sloppy, import system. Even so, I have a module in my personal lib that just publicly imports the 10 or so Phobos modules I use most frequently, because even in Phobos the amount of import declaration boilerplate is too much, but using std.all caused too many naming collisions with modules that I don't use.
Aug 01 2010
next sibling parent reply =?iso-8859-2?B?VG9tZWsgU293afFza2k=?= <just ask.me> writes:
Dnia 01-08-2010 o 16:32:50 Philippe Sigaud <philippe.sigaud gmail.com>  =

napisa=B3(a):

 I have to use Adam Ruppe's "find D keyword" website (very handy)  =

 regularly...

Link, please. ;)
Aug 01 2010
parent Pelle <pelle.mansson gmail.com> writes:
On 08/01/2010 05:25 PM, Adam Ruppe wrote:
 On 8/1/10, Tomek Sowiński<just ask.me>  wrote:
 Link, please. ;)

http://dpldocs.info If any tried to use it last week, you would have noticed it was down: my motherboard died, and the parts to fix it didn't arrive until Friday. It should be up most the time now. You can put in a search term to the box, or use http://dpldocs.info/std.string and the similar to jump right to the appropriate document.

I was like a crippled sheep without it. Thank you for this excellent website. I use it almost every day :) I mostly just use dpldocs.info/searchterm, and almost every time what I look for comes up. Awesome!
Aug 01 2010
prev sibling next sibling parent Adam Ruppe <destructionator gmail.com> writes:
On 8/1/10, Tomek Sowi=F1ski <just ask.me> wrote:
 Link, please. ;)

http://dpldocs.info If any tried to use it last week, you would have noticed it was down: my motherboard died, and the parts to fix it didn't arrive until Friday. It should be up most the time now. You can put in a search term to the box, or use http://dpldocs.info/std.string and the similar to jump right to the appropriate document.
Aug 01 2010
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 08/01/2010 09:32 AM, Philippe Sigaud wrote:
 On Sun, Aug 1, 2010 at 16:02, dsimcha <dsimcha yahoo.com
 <mailto:dsimcha yahoo.com>> wrote:

 [flat / nested]

     Please, no.  This is why I hate Tango and Java.  It's too hard to
     find what you
     need, and you have to write too much import declaration boilerplate.


 I agree that Java pushed that too far for my taste also. Looking at
 Tango, it's indeed really nested. But hey, std.c.* is already two-levels
 and I never heard anyone complaining. I thought there was a kind of
 agreement about some modules in Phobos that were beginning to be quite
 big, but I may be wrong.

 Now that I think about it, my real problem on this point is not so much
 that std.algorithm is too big but that:

 - I don't always know whether such or such function in in std.string,
 std.algorithm, std.range, etc.
 - The doc pages are not particularly organized.

 I have to use Adam Ruppe's "find D keyword" website (very handy)
 regularly...

       I love
     Phobos's flat, simple, even if at times sloppy, import system.  Even
     so, I have a
     module in my personal lib that just publicly imports the 10 or so
     Phobos modules I
     use most frequently, because even in Phobos the amount of import
     declaration
     boilerplate is too much, but using std.all caused too many naming
     collisions with
     modules that I don't use.


 I do the same. I always end up importing the same 10-15 modules.

 But, what about putting all() and some() in std.algorithm?

I agree that all of the functions you suggested deserve a place in std.algorithm (or std.range). Please add one bugzilla entry or better yet let me know if you'd like to join Phobos's devs (subject to team approval) so you can add them yourself. Also, I agree that std.algorithm has gotten a bit large. Any sensible ideas for addressing that should be discussed. Off the top of my head, I'm thinking that mutators vs. non-mutators could be a possible criterion for separation. BTW, it warms my heart to see that our std.algorithm is the fourth Google hit when searching for std::algorithm (or std.algorithm, which seems to produce the same results). I feel std.container can be a similarly compelling offering. *cough*RBTree*cough*Steve*cough* Andrei
Aug 01 2010
next sibling parent Pointing hand <lurkers lurking.org> writes:
Steven Schveighoffer Wrote:
 
 The bigger issue is the documentation.  D has been very stagnant in  
 improving the doc generator.  We are missing a global function/symbol  
 index, cross-linked docs, and many other goodies that have been in systems  
 like doxygen since its inception.

Tango had it all. The 3rd party document generator was excellent. Its parser actually followed the written language spec more closely than DMD. Unfortunately Tango and 3rd party utilities written by Tango enthusiastics cannot be used anymore because of license & political issues.
Aug 02 2010
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 08/02/2010 06:11 AM, Steven Schveighoffer wrote:
 On Sun, 01 Aug 2010 17:34:46 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 I agree that all of the functions you suggested deserve a place in
 std.algorithm (or std.range). Please add one bugzilla entry or better
 yet let me know if you'd like to join Phobos's devs (subject to team
 approval) so you can add them yourself.

 Also, I agree that std.algorithm has gotten a bit large. Any sensible
 ideas for addressing that should be discussed. Off the top of my head,
 I'm thinking that mutators vs. non-mutators could be a possible
 criterion for separation.

This doesn't matter too much. Parsing std.algorithm is quick by the compiler, and all of std.algorithm is templates. The bigger issue is the documentation. D has been very stagnant in improving the doc generator. We are missing a global function/symbol index, cross-linked docs, and many other goodies that have been in systems like doxygen since its inception.
 BTW, it warms my heart to see that our std.algorithm is the fourth
 Google hit when searching for std::algorithm (or std.algorithm, which
 seems to produce the same results). I feel std.container can be a
 similarly compelling offering. *cough*RBTree*cough*Steve*cough*

Yeah yeah :) My spare-time priorities: 1. New Minivan 2. Getting baby's room ready 3. Cleaning rest of house 4. Completing RBTree for you ;)

New baby? Congratulations! (Who said the D community isn't growing?) And yes, you're excused :o). In fact I'll use with credit the code you'd already sent me, only unittests are missing, which I can add myself. Andrei P.S. A couple of friends of mine swear by Honda Odyssey. In fact, one of them owns two.
Aug 02 2010
prev sibling next sibling parent Jonathan M Davis <jmdavisprog gmail.com> writes:
On Sunday 01 August 2010 07:32:50 Philippe Sigaud wrote:
 But, what about putting all() and some() in std.algorithm?

An enhancement request already exists for these: http://d.puremagic.com/issues/show_bug.cgi?id=4405 - Jonathan M Davis
Aug 01 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 01 Aug 2010 17:34:46 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 I agree that all of the functions you suggested deserve a place in  
 std.algorithm (or std.range). Please add one bugzilla entry or better  
 yet let me know if you'd like to join Phobos's devs (subject to team  
 approval) so you can add them yourself.

 Also, I agree that std.algorithm has gotten a bit large. Any sensible  
 ideas for addressing that should be discussed. Off the top of my head,  
 I'm thinking that mutators vs. non-mutators could be a possible  
 criterion for separation.

This doesn't matter too much. Parsing std.algorithm is quick by the compiler, and all of std.algorithm is templates. The bigger issue is the documentation. D has been very stagnant in improving the doc generator. We are missing a global function/symbol index, cross-linked docs, and many other goodies that have been in systems like doxygen since its inception.
 BTW, it warms my heart to see that our std.algorithm is the fourth  
 Google hit when searching for std::algorithm (or std.algorithm, which  
 seems to produce the same results). I feel std.container can be a  
 similarly compelling offering. *cough*RBTree*cough*Steve*cough*

Yeah yeah :) My spare-time priorities: 1. New Minivan 2. Getting baby's room ready 3. Cleaning rest of house 4. Completing RBTree for you ;) -Steve
Aug 02 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 02 Aug 2010 09:11:32 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 08/02/2010 06:11 AM, Steven Schveighoffer wrote:
 On Sun, 01 Aug 2010 17:34:46 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 I agree that all of the functions you suggested deserve a place in
 std.algorithm (or std.range). Please add one bugzilla entry or better
 yet let me know if you'd like to join Phobos's devs (subject to team
 approval) so you can add them yourself.

 Also, I agree that std.algorithm has gotten a bit large. Any sensible
 ideas for addressing that should be discussed. Off the top of my head,
 I'm thinking that mutators vs. non-mutators could be a possible
 criterion for separation.

This doesn't matter too much. Parsing std.algorithm is quick by the compiler, and all of std.algorithm is templates. The bigger issue is the documentation. D has been very stagnant in improving the doc generator. We are missing a global function/symbol index, cross-linked docs, and many other goodies that have been in systems like doxygen since its inception.
 BTW, it warms my heart to see that our std.algorithm is the fourth
 Google hit when searching for std::algorithm (or std.algorithm, which
 seems to produce the same results). I feel std.container can be a
 similarly compelling offering. *cough*RBTree*cough*Steve*cough*

Yeah yeah :) My spare-time priorities: 1. New Minivan 2. Getting baby's room ready 3. Cleaning rest of house 4. Completing RBTree for you ;)

New baby? Congratulations!

Thanks!
 (Who said the D community isn't growing?) And yes, you're excused :o).  
 In fact I'll use with credit the code you'd already sent me, only  
 unittests are missing, which I can add myself.

That would be good. I can add more later if I find some dcollections unit tests that cover more than what you add. Indirectly, the code should be well-tested since the RB algorithm is copied verbatim from dcollections which has full unit-tests. Before you do so though, I think I have a more updated version which includes lowerBound and upperBound fixed (and equalRange added). I'm not sure if I sent that to you, I'll send it now. I also started with one unittest copied from dcollections. Also note the docs aren't really Phobosified, I've not yet learned how the phobos docs work.
 Andrei

 P.S. A couple of friends of mine swear by Honda Odyssey. In fact, one of  
 them owns two.

My parents have one, and we will have one shortly :) -Steve
Aug 02 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 02 Aug 2010 08:32:47 -0400, Pointing hand <lurkers lurking.org>  
wrote:

 Steven Schveighoffer Wrote:
 The bigger issue is the documentation.  D has been very stagnant in
 improving the doc generator.  We are missing a global function/symbol
 index, cross-linked docs, and many other goodies that have been in  
 systems
 like doxygen since its inception.

Tango had it all. The 3rd party document generator was excellent. Its parser actually followed the written language spec more closely than DMD. Unfortunately Tango and 3rd party utilities written by Tango enthusiastics cannot be used anymore because of license & political issues.

At the risk of "feeding the troll," I don't think there's any political/licensing issues preventing using dil to generate the docs except that dil doesn't support d2 (or does it?). I really like the tango doc style, much better than phobos'. -Steve
Aug 02 2010
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--0016e6dd994607f201048cdc19d1
Content-Type: text/plain; charset=ISO-8859-1

On Mon, Aug 2, 2010 at 01:12, Jonathan M Davis <jmdavisprog gmail.com>wrote:

 On Sunday 01 August 2010 07:32:50 Philippe Sigaud wrote:
 But, what about putting all() and some() in std.algorithm?

An enhancement request already exists for these: http://d.puremagic.com/issues/show_bug.cgi?id=4405 Good, I remember the thread it originated from, but didn't there was a

--0016e6dd994607f201048cdc19d1 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Mon, Aug 2, 2010 at 01:12, Jonathan M Davis <= span dir=3D"ltr">&lt;<a href=3D"mailto:jmdavisprog gmail.com">jmdavisprog g= mail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style= =3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> <div class=3D"im">On Sunday 01 August 2010 07:32:50 Philippe Sigaud wrote:<= br> &gt; But, what about putting all() and some() in std.algorithm?<br> <br> </div>An enhancement request already exists for these:<br> <br> <a href=3D"http://d.puremagic.com/issues/show_bug.cgi?id=3D4405" target=3D"= _blank">http://d.puremagic.com/issues/show_bug.cgi?id=3D4405<br></a><br></b= lockquote><div>Good, I remember the thread it originated from, but didn&#39= ;t there was a request for it already.=A0</div> <div><br></div><div><br></div></div><br> --0016e6dd994607f201048cdc19d1--
Aug 02 2010
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--00032555834ae1d29f048cdc42e8
Content-Type: text/plain; charset=ISO-8859-1

On Sun, Aug 1, 2010 at 23:34, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

 I agree that all of the functions you suggested deserve a place in

let me know if you'd like to join Phobos's devs (subject to team approval) so you can add them yourself.

I'd be quite happy to join the Phobos' devs, if they accept me! In any case, as Jonathan said, all() and any() are 'bug' 4405. And takeWhile is 4535 (as per you suggestion, I added it a few days ago). http://d.puremagic.com/issues/show_bug.cgi?id=4535
 Also, I agree that std.algorithm has gotten a bit large. Any sensible ideas
 for addressing that should be discussed. Off the top of my head, I'm
 thinking that mutators vs. non-mutators could be a possible criterion for
 separation.

 BTW, it warms my heart to see that our std.algorithm is the fourth Google
 hit when searching for std::algorithm (or std.algorithm, which seems to
 produce the same results). I feel std.container can be a similarly
 compelling offering. *cough*RBTree*cough*Steve*cough*

That reminds me I've some questions to ask on recursive containers (graphs, trees). I'll try to make a post about it. --00032555834ae1d29f048cdc42e8 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Sun, Aug 1, 2010 at 23:34, Andrei Alexandresc= u <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.org">Se= eWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><blockquote class=3D"g= mail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-l= eft:1ex;"> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"><div class=3D"im"><br></div></blockquote> I agree that all of the functions you suggested deserve a place in std.algo= rithm (or std.range). Please add one bugzilla entry or better yet let me kn= ow if you&#39;d like to join Phobos&#39;s devs (subject to team approval) s= o you can add them yourself.<br> </blockquote><div><br></div><div>I&#39;d be quite happy to join the Phobos&= #39; devs, if they accept me!</div><div><br></div><div>In any case, as Jona= than said, all() and any() are &#39;bug&#39; 4405. And takeWhile is 4535 (a= s per you suggestion, I added it a few days ago).</div> <div><br></div><div><a href=3D"http://d.puremagic.com/issues/show_bug.cgi?i= d=3D4535">http://d.puremagic.com/issues/show_bug.cgi?id=3D4535</a></div><di= v>=A0</div><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin= :0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> <br> Also, I agree that std.algorithm has gotten a bit large. Any sensible ideas= for addressing that should be discussed. Off the top of my head, I&#39;m t= hinking that mutators vs. non-mutators could be a possible criterion for se= paration.<br> <br> BTW, it warms my heart to see that our std.algorithm is the fourth Google h= it when searching for std::algorithm (or std.algorithm, which seems to prod= uce the same results). I feel std.container can be a similarly compelling o= ffering. *cough*RBTree*cough*Steve*cough*<br> </blockquote><div><br></div><div>That reminds me I&#39;ve some questions to= ask on recursive containers (graphs, trees). I&#39;ll try to make a post a= bout it.</div><div><br></div><div><br></div></div> --00032555834ae1d29f048cdc42e8--
Aug 02 2010
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--0016e6dab3076cca8e048cc3f58c
Content-Type: text/plain; charset=ISO-8859-1

On Sun, Aug 1, 2010 at 16:02, dsimcha <dsimcha yahoo.com> wrote:

[flat / nested]

 Please, no.  This is why I hate Tango and Java.  It's too hard to find what
 you
 need, and you have to write too much import declaration boilerplate.

I agree that Java pushed that too far for my taste also. Looking at Tango, it's indeed really nested. But hey, std.c.* is already two-levels and I never heard anyone complaining. I thought there was a kind of agreement about some modules in Phobos that were beginning to be quite big, but I may be wrong. Now that I think about it, my real problem on this point is not so much that std.algorithm is too big but that: - I don't always know whether such or such function in in std.string, std.algorithm, std.range, etc. - The doc pages are not particularly organized. I have to use Adam Ruppe's "find D keyword" website (very handy) regularly...
  I love
 Phobos's flat, simple, even if at times sloppy, import system.  Even so, I
 have a
 module in my personal lib that just publicly imports the 10 or so Phobos
 modules I
 use most frequently, because even in Phobos the amount of import
 declaration
 boilerplate is too much, but using std.all caused too many naming
 collisions with
 modules that I don't use.

I do the same. I always end up importing the same 10-15 modules. But, what about putting all() and some() in std.algorithm? Philippe --0016e6dab3076cca8e048cc3f58c Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Sun, Aug 1, 2010 at 16:02, dsimcha <span dir= =3D"ltr">&lt;<a href=3D"mailto:dsimcha yahoo.com">dsimcha yahoo.com</a>&gt;= </span> wrote:<br><div><br></div><div>[flat / nested]=A0</div><blockquote c= lass=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;= padding-left:1ex;"> <div class=3D"im"> </div>Please, no. =A0This is why I hate Tango and Java. =A0It&#39;s too har= d to find what you<br> need, and you have to write too much import declaration boilerplate.</block= quote><div><br></div><div>I agree that Java pushed that too far for my tast= e also. Looking at Tango, it&#39;s indeed really nested. But hey, std.c.* i= s already two-levels and I never heard anyone complaining. I thought there = was a kind of agreement about some modules in Phobos that were beginning to= be quite big, but I may be wrong.</div> <div><br></div><div>Now that I think about it, my real problem on this poin= t is not so much that std.algorithm is too big but that:</div><div><br></di= v><div>- I don&#39;t always know whether such or such function in in std.st= ring, std.algorithm, std.range, etc.</div> <div>- The doc pages are not particularly organized.</div><div><br></div><d= iv>I have to use Adam Ruppe&#39;s &quot;find D keyword&quot; website (very = handy) regularly...</div><div>=A0</div><blockquote class=3D"gmail_quote" st= yle=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> =A0I love<br> Phobos&#39;s flat, simple, even if at times sloppy, import system. =A0Even = so, I have a<br> module in my personal lib that just publicly imports the 10 or so Phobos mo= dules I<br> use most frequently, because even in Phobos the amount of import declaratio= n<br> boilerplate is too much, but using std.all caused too many naming collision= s with<br> modules that I don&#39;t use.<br> </blockquote></div><br><div>I do the same. I always end up importing the sa= me 10-15 modules.</div><div><br></div><div>But, what about putting all() an= d some() in std.algorithm?</div><div><br></div><div>Philippe</div><div> <br></div> --0016e6dab3076cca8e048cc3f58c--
Aug 01 2010