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

• Philippe Sigaud (30/31) Aug 01 2010 I agree. all() and any/some() are both easy to code, I think, and useful...
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
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
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
=?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
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
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
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
"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
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
"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
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
"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
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
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
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