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
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




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


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 Philippe Sigaud <philippe.sigaud gmail.com> writes:
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
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 reply 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
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 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 reply "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
next sibling parent reply 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
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 parent reply 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
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 parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
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


 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.


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.
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 parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
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


request for it already.
Aug 02 2010