Lazy algorithms

[tcbrindle]

In this comment, @mknejp mentions wanting a max_element that works lazily rather than eagerly.

This is actually pretty tricky to do with the current Flux or STL iteration models, because the need to start "on track" means that the max-fold would have to happen really early -- so you may as well just do it eagerly, and just return an optional that you can continue to chain from.

But the move the new iterable model changes things, because now we can delay doing the actual fold until the first call to iterate(). So we could potentially write a lazy_max_adaptor as something like this (untested):

template <iterable Base>
struct lazy_max_adaptor {
     Base base;

     struct context_type {
            optional<iterable_value_type<Base>> max_elem;  

            using element_type = iterable_value_type<Base>;

            auto run_while(auto&& pred) {
                if (max_elem.has_value()) {
                    auto r = pred(*std::move(max_elem));
                    max_elem.reset();
                    if (!r) return iteration_result::incomplete;
                }
                return iteration_result::complete;
            }
      };

     auto iterate() { return context_type{.max_elem = flux::max(base)}; }
};

Of course, this doesn't just apply to max() -- there are a lot of algorithms that we might want to perform lazily like this. It might even be possible to have a lazy wrapper, so you could write something like flux::lazy(flux::sort, comparator) as part of a pipeline and it would defer doing the actual sort until the user explicitly started iteration?