Customisable algorithms

[tcbrindle]

We should provide a mechanism for user-defined sequences (and library-defined sequences) to use custom implementations of Flux algorithms and adaptors, when they can do so more efficiently or offer more functionality than the default.

Motivation

The repeat(val) sequence factory endlessly repeats val, while repeat(val, n) repeats val exactly n times. Under the new model, the infinite version is iterable only, while the finite version is a random_access_collection. This means that repeat(val).take(n) will also be iterable-only, when it really should be exactly the same as repeat(val, n) (i.e. random-access). In order to achieve this, we need to do one of two things: either modify take so that it special-cases repeat, or provide a way for repeat to specialise the take algorithm.

If it was just repeat(val).take(n) that was the problem, then special-casing would probably be the way to go. But when you look into it, more appear where generic customisation would be useful. For example:

• Sticking with infinite repeat: the drop, stride and reverse adaptors could all be no-ops
• Similar to repeat(), iota(n) is iterable-only but iota(n).take(m) could be random-access
• take() and drop() for iota(m, n) could be specialised to just adjust the bounds of the iota sequence
• take(n).take(m) and drop(n).drop(m) could be specialised to just adjust the count
• take() and drop() for random-access slices could be specialised to just adjust their bounds
• Almost anything you do with an empty sequence results in another empty sequence

Ranges has lots of special cases in its views function objects (in particular views::take and views::drop): it would be nice if we could do the same things but in a more principled way that end-users can also hook in to.

Mechanism

The special cases we currently have (e.g. reverse().reverse()) use the same approach as ranges, i.e. just an if constexpr inside the function object. A more generic approach would be to provide a flux::implementation class template which users could specialise:

template <typename Fn, typename... Types>
struct implementation; // not defined

template <typename Fn, typename... Types>
concept has_custom_impl = requires {
    { sizeof(implementation<Fn, Types...>) > 0 };
};

We could then define take as:

struct take_fn {
    template <adaptable_iterable Iter>
    auto operator()(Iter&& iter, int_t count) const
    {
        FLUX_ASSERT(count >= 0);
        using R = std::remove_cvref_t<Iter>;
        if constexpr (has_custom_impl<take_fn, R>) {
            return implementation<take_fn, R>{}(FLUX_FWD(iter), count);
        } else {
            return take_adaptor<R>(FLUX_FWD(iter), count);
        }
    }
};

inline constexpr auto take = take_fn{};

Later, a type wanting to specialise take could do it like so:

template <typename Value>
struct implementation<take_fn, repeat_iterable<Value>> {
    auto operator()(repeat_iterable<Value>&& iter, int_t count) const
    {
        return repeat_collection<Value>(std::move(iter).get_value(), count);
    }
};

The only potential down-side that I can see with this approach is that the compiler will need to (try to) instantiate implementation<F, Arg> for every function call. I'm not sure whether this would actually be measurable given the amount of concept checking etc we do anyway, but it's worth bearing in mind. Perhaps a good first step would be to do this only for the most important functions (i.e. take() and drop()) and see what the impact is.

[n0F4x]

It feels like you are trying to tackle two problems at once here.

1. Infinite sequences can't become random access
2. Optimizations of "empty" sequence adaptors

I would like to give feedback on the first problem, as I feel like you are either missing an important abstraction, or the current abstractions you have are incomplete.

Intuitively, I would think that repeat and similar sequences should be random_access.
By looking at your slides from cpponsee, I see the following:

• repeat could be a collection by defining a custom position type that can be used for bounds checking.
  It might not fit the concept of being totally orderable.
  However, unfortunately, I don't see why you need total ordering when this type is only necessary for bounds checking.
  One way to go would be to use a different position and sentinel type even.

• Given that repeat is a collection with custom type(s) for access and bounds checking, the only incomprehensible part for making it a random_access_collection is the definition of distance(pos1, pos2).
  Again, intuitively, random access collections don't necessarily need the concept of a distance.
  Which means that there are potential holes within the current design space.

  Another option is, of course, to say that the distance between two of these positions is zero or infinite.
  (I don't really know how to interpret these results at the moment. Maybe someone smarter will come up with a better solution.)

• The same can be said for iota, except that the distance here is actually meaningful.

[tcbrindle]

Hi @n0F4x, thanks for the feedback!

I can see where you're coming from: if we have a sequence that just repeats the number 4 endlessly, then it seems like we should "obviously" be able to jump forwards and backwards arbitrary distances within that sequence in constant time. And in fact that's exactly how I did things in the current version of Flux.

So, why do I want to change this for the new version? The basic problem is that for the collection API, we absolutely need to be able to test positions for equality -- even for a basic for loop for example, we need to be able to ask whether current_pos == start_pos + 10 so that we know where to stop. This means that in order to have truly infinite collections, we'd need to be able to count to infinity, and I don't know how to do that on a computer with finite memory :)

The current version of repeat uses a size_t counter which rolls over, meaning it's not really infinite at all and you can "break" the API by advancing by SIZE_MAX places from the start and then advancing once more. I've never been happy about this, and it's something I want to fix in the new version.

However, unfortunately, I don't see why you need total ordering when this type is only necessary for bounds checking.

Bounds checking for collections could be done with a customisable function like bool is_in_bounds(collection, position), which is basically how current Flux does things (except right now the function is called is_last).

The total ordering requirement comes from the need to easily perform bounds checking for arbitrary slices of collections. A slice looks like so:

template <collection BaseColl>
struct slice {
    BaseColl* base;
    position_t<BaseColl> from;
    position_t<BaseColl> to;
};

Given a position pos, how do we ensure that it is within the bounds of the slice? Calling is_in_bounds(base, pos) will only tell us whether the position is within the bounds of the parent collection, which isn't what we want. In order to be able to bounds check a slice, we'd instead need a function like bool is_in_bounds(base, start, end, pos). This is equivalent to requiring a total ordering on positions, except the latter is easier to implement (because we can use default functions in C++20) and IMO easier to understand.

One way to go would be to use a different position and sentinel type even.

I'm not sure what the advantage of a separate sentinel type would be in this case?

Again, intuitively, random access collections don't necessarily need the concept of a distance.

Again, I can see where you're coming from, but you really do want constant-time distance for random access collections to be useful. For example, the advance function, which get used all over the place (and I really ought to make public) relies on this. There are other adaptors which use distance in their implementation of random-access jumps to make sure they don't overstep bounds.

And apart from that, the standard library's random_access_iterator concept requires a constant-time distance operation (for the same reasons as we do) and I'd really like Flux random-access collections to be able to offer proper random-access STL iterators.