How to lazy reduce/accumulate monoid as part of a view sequence?

[nmlkjihgfedcba]

Hi there

I'd like to use something like view::reduce, view::accumulate to express lazy reductions of regular monoids or semigroups.

How can this be done? For a basic example, let's just say we want to express the lazy sum of a range of numbers, and then we want to build some other different lazy views on these reductions.

Thanks so much. I searched through the documentation for the past 8 hours but I was unable to find it so far.

[nmlkjihgfedcba]

How can I perform a bind lift here?

like this:

auto a = view::take(2) | view::bind(2, view::iota);
auto b = view::partial_sum() | view::reverse | view::take(1);
auto c = view::concat(view::single(1), view::single(100)) | a | b;

also, the reverse does not work with the forward iterator concept for the partial sum, so it does not reduce there.

[ericniebler]

The views are lazy sequence algorithms. One range in, one range out. accumulate is range algorithms that produces a value, not another range. There is no accumulate view, but there is an (eager) accumulate algorithm. Perhaps you can wrap that in a lambda?

[nmlkjihgfedcba]

hi Eric. I don't want it to be a value, but a lazy reduction only. It can temporarily become a range with a single element (i.e. view::partial_sum() | view::reverse | view::take(1)). This single element may be an intermediary step used in other expansions that become other ranges.

How do you define the range of the reverse head of a partial_sum, if reverse cannot be used?

view::partial_sum() | view::reverse but also even view::partial_sum() | view::take(2) | view::reverse produces: CONCEPT_ASSERT_MSG(BidirectionalRange<Rng>(), ...

[apmccartney]

I'll comment upfront that (imo) this sort of question is better directed to stack overflow than the ranges-v3 issue tracker.

I searched through the documentation for the past 8 hours but I was unable to find it so far.

Oof, that's rough. I admire your persistence.

partial_sum cannot be reversed

partial_sum cannot be implemented as anything stronger than a forward range in general. Note that partial_sum is defined in terms of an arbitrary binary operator. Reverse iteration would require somehow inferring the inverse operation. An inverse may not even exist, and even if it did, C++ (or any other language that I know of) does not provide a mechanism for that sort of inference.

generalized lazy evaluation

What you're asking for is somewhat outside the scope of the library. Unlike Haskel, C++ is an eager language, and the language lacks an analogue to Scala's lazy values.

The ranges libary is scoped to lazy sequence operations. In order to accomplish what you're describing with range-v3, the problem need be formulated as a lazy sequence operation. That said, any value can be lifted into a sequence using ranges::view::single, which is the range-v3 implementation of the sequence's monadic return operation. Once lifted into a sequence, functor mapping can be applied by way of ranges::view::transform, which is lazy.

I've written up a trivial example demonstrating this in wandbox here, and reproduced the example below should the link go stale in the future. Pardon the use of boost hana (although given the heavily functional accent in your description, I suspect you might appreciate the library).

example

source

#include <iostream>
#include <vector>

#include <range/v3/all.hpp>
#include <boost/hana.hpp>

int main(){
  auto original = ranges::view::iota(1, 10);
  std::cout << "original state: " << original << std::endl;

  auto lifted = ranges::view::single(original);
  std::cout << "after monadic lift: " << lifted << std::endl;

  auto addition_fold = boost::hana::reverse_partial(ranges::accumulate, 0 /* addition identity */);
  auto lifted_reduction = lifted | ranges::view::transform(addition_fold);
  std::cout << "lift >>= addition_fold: " << lifted_reduction << std::endl;

  auto flatten = lifted_reduction.front();
  std::cout << "reduction: " << flatten << std::endl;
 }

output

original state: [1,2,3,4,5,6,7,8,9]
after monadic lift: [[1,2,3,4,5,6,7,8,9]]
lift >>= addition_fold: [45]
reduction: 45