I have a function

int f(int);

I want to get

[0, f(0), f(f(0)), f(f(f(0))), ...]

until f return -1. I was wondering if there is a name for this in functional programming. It looks like recursion.

CodePudding user response：

The closest thing in range-v3 to do this views::partial_sum¹. This takes a binary function, applying it to the result of the previous element in the destination range and the next element in the source range.

But here, we can simply ignore the next element in the source range, since we don't care about it - just the previous element:

auto recurrence =
    rv::iota(0)
    | rv::partial_sum([](int prev, int){
        return f(prev);
      })
    | rv::take_while([](int i){
        return i != -1;
      })

iota(0) gives you the range [0, 1, 2, ...]. It doesn't actually matter what the contents are after the 0, just that they're infinite. rv::repeat(0) also works, that's just the range [0, 0, 0, ...]

The partial_sum then gives you the range [0, f(0), f(f(0)), f(f(f(0))), ...]

And then take_while stops when we reach -1. Note that -1 is not included in the result - if you want to include that, the construction is... trickier.

In general though, this kind of thing is much easier to do with a generator:

auto recurrence() -> generator<int> {
    int i = 0;
    while (i != -1) {
        co_yield i;
        i = f(i);
    }
}

Which is also easier to restructure if you want to include the -1:

auto recurrence() -> generator<int> {
    int i = 0;
    while (true) {
        co_yield i;
        if (i == -1) {
            break;
        }
        i = f(i);
    }
}

¹ range-v3 has views::generate, but that takes a nullary function - it gives you the range [f(), f(), f(), ...], but allowing for f() to return a different value every time. I suppose we could use that to do:

views::generate([cur=0, next=0]() mutable {
    cur = next;
    next = f(next);
    return cur;
})

Which we could built up a:

auto generate_unary = [](auto init, auto f){
    return views::generate([cur=init, next=init, f]() mutable {
        cur = next;
        next = f(next);
        return cur;
    });
};

And then we can generate_unary(0, f)