Reorganization or algorithm and range

[Ogi-kun]

These two packages are closely related. Most algorithms work on ranges and ranges only. Range-based code usually needs to import some std.algorithm modules for basic things like map or fold. And it’s not always clear which of this packages defines a given function.

On the other hand, routines in algorithm that don’t operate on ranges seems too basic to be called “algorithms”: min, max, clamp, swap, move etc. Maybe they should be put to a separate module, like phobos.sys.utility?

There should be some better way to organize these packages, but I don’t have a clear answer how exactly it should be done. What do you think?

[atilaneves]

phobos.sys.utility?

Absolutely not, that name means nothing.

I'm not sure algorithm and range need rethinking.

[Ogi-kun]

Absolutely not, that name means nothing.

“Algorithm” is also a name that means nothing. Any subroutine is an algorithm.

So let’s define the terminology. This is how I see it:

• phobos.sys.utility — generic utility functions;
• phobos.sys.algorithm — generic range-processing functions.

Primitives like max, clamp, swap, move belong in utility package because they don’t operate on ranges. Now the difference between max and maxElement is more clear: they are in different packages!

On the other hand, splitter(Range)(Range r) (character-range specific version of splitter) don’t belong in algorithm because it’s not generic; it should be renamed to something like wordSplitter and put among other text-processing functions. (Or better, reimplemented to follow the Unicode line breaking algorithm.)

Some other generic utility functions are scattered throughout the library. For example, std.exception.assumeUnique has nothing to do with exceptions. These functions should find their home in utility.

// from std.algorithm.comparison:
among
castSwitch
clamp
either
max
min
predSwitch

// from std.algorithm.comparison:
move
moveEmplace
swap

// from std.concurrency:
initOnce

// from std.exception:
assumeUnique
mayPointTo
doesPointTo

I'm not sure algorithm and range need rethinking.

After working with D for 8 years I still can’t tell without looking whether a particular function is defined in algorithm or in range. chunks and evenChunks are in algorithm but chunkBy is in algorithm. stripLeft is algorithm but padLeft is in range. Seems completely arbitrary.

[LightBender]

We're not planning a redesign of std.algorithm. It'll be getting some name changes to more closely match industry standards for naming, and of course making sure that it no longer auto-decodes, but that's about it.

@jmdavis is currently redesigning std.range.

[atilaneves]

“Algorithm” is also a name that means nothing. Any subroutine is an algorithm.

Maybe if one ignores the C++ STL, which one should not.

phobos.sys.utility

Again, sorry, no. "utility", "helper", "misc", etc. might as well all be renamed to "i_give_up".

[Ogi-kun]

Maybe if one ignores the C++ STL, which one should not.

Okay, let’s see how various online references describle <algorithm>.

The algorithms library defines functions for a variety of purposes (e.g. searching, sorting, counting, manipulating) that operate on ranges of elements. — cppreference.com

The header defines a collection of functions especially designed to be used on ranges of elements. — cplusplus.com

The library has many functions that allow you to modify ranges of data from data structures. — w3schools.com

C++ Standard Library algorithms process iterator ranges that are typically specified by their beginning or ending positions. — microsoft.com

The algorithms library defines functions for a variety of purposes (e.g. searching, sorting, counting, manipulating) that operate on ranges of elements. — devdocs.io

Seems to be in line with my description.

Oh, and in C++11, they moved the definition of move and swap to… <utility>.

"utility", "helper", "misc", etc. might as well all be renamed to "i_give_up".

The functions that I described as “utility” are not just a bunch of random stuff. They all have shared characteristics: these are functions that operate on values in a type-agnostic manner. It’s a useful category. For example, isNaN is just a helper for x != x, but it’s not a “utility” function because it operates on floating point types only.

[rikkimax]

There is a very big difference between std.uni having a module called utility and std.algorithm having one.

Atila is right regarding std.algorithm, it should be categorising algorithms appropriately. This is very well studied we do not need to come up with them.

As for std.range the primitives certainly come under this, but I'm not sure that the rest do. They are algorithms that do range things, just like the rest of std.algorithm does. I would like us to reconsider where the non-primitives live.

[Ogi-kun]

There is a very big difference between std.uni having a module called utility and std.algorithm having one.

I’m not talking about std.algorithm.utility, I’m talking about std.utility.

[Ogi-kun]

Okay, a bold idea: just merge range with algorithm.

phobos.sys
  | algorithm
    | comparison
M   | iteration
    | mutation
    | searching
    | setops
    | sorting
+   | range
+   | traits

phobos.sys.algorithm.range is a small module that defines range primitives for arrays and primitives like walkLength and put.

phobos.sys.algorithm.traits defines isInputRange, ElementType, hasSlicing etc.

phobos.sys.algorithm.iteration gets functions that are currently defined in std.range package module.

There is no equivalent of std.range.interfaces because Phobos v3 will not support class-based ranges.

[rikkimax]

The traits would go into the more generalised traits module I would expect.

walkLength in iteration, put mutation?

I agree there is a way it could be done, however, let's see what other people think.

[Ogi-kun]

The traits would go into the more generalised traits module I would expect.

I’m not sure. Range traits are only interesting when you’re dealing with ranges.

walkLength in iteration, put mutation?

Maybe.