Make a range from Iterated function application

user_11998382 0
Viewed 58

If I have a function

std::array<unsigned,2> fib(std::array<unsigned,2> p)
{
    return {p[1],p[1]+p[0]};
}

I'd like to have a way to elegantly generate the infinite range

[x,fib(x),fib(fib(x)),fib(fib(fib(x))),...]

This comes up frequently enough that I need to find what's the best way to do this?

range-v3 std-ranges c++20 c++
4 Answers

I found that the generator from this repo works well:

template<typename F, typename Arg>
tl::generator<Arg> iterated_application(F fn, Arg x) {
    while (true) {
        co_yield x;
        x = fn(x);
    }
}

Which can be used as

int main() 
{
    auto fib = [](auto a) {return std::array{ a[1],a[1] + a[0] }; };
    for (auto i : iterated_application(fib, std::array{ 0,1 }) 
        | std::views::keys 
        | std::views::take(10))
    std::cout << i << std::endl;
}

https://godbolt.org/z/v73zvY9cM

user_119983820

You could always create your own iterator:

template<typename Arg>
struct impl_iterated_application {
    using value_type = Arg;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;

    const Arg& operator*() const { return current; }
    impl_iterated_application& operator++() 
    { 
        current = fn(current); 
        return *this; 
    }
    auto operator++(int) { auto temp = *this; ++* this; return temp; }
    
    impl_iterated_application(std::function<Arg(Arg)>  f = std::identity{}, Arg initial = {}) : current(initial), fn(f)
    {}
    //bool operator==(const impl_iterated& other) const = default;

private:
    Arg current;
    std::function<Arg(Arg)> fn;
};

which you would use in this factory function:

template<typename F, typename Arg>
auto iterated_application(F fn, Arg x)
{
    return std::ranges::subrange(impl_iterated_application(std::function<Arg(Arg)>{fn}, x), std::unreachable_sentinel);
}

https://godbolt.org/z/dxvn54ffv

I think co-routine generators are be the way to do this. I should try to get https://github.com/lewissbaker/cppcoro working.

user_119983820

I guess you could be a bit abusive and use partial sum, ignoring all but the first element in the adapted range:

auto fib = ranges::views::repeat(std::array{ 0,1 })
        | ranges::views::partial_sum([](auto a, auto){ return std::array{ a[1], a[0] + a[1] }; });
for (auto elem : fib |  ranges::views::take(10))
    std::cout << elem[0] << std::endl;
user_119983820

A mutable lambda also works

template<typename Arg, std::invocable<Arg> F>
auto iterated_application(F fn, Arg x)
{
    return ranges::views::generate(
        [p = x, f=fn]() mutable
        {
            auto p0 = p;
            p = f(p);
            return p0;
        });
}
user_119983820
Related