从迭代函数应用程序中创建一个范围

Question

如果我有函数

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

我想要一种优雅地生成无限范围的方法

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

这种情况经常出现，我需要找到最好的方法是什么？

Answer 1

您始终可以创建自己的迭代器：

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;
};

您将在此工厂函数中使用的：

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

我认为 co-routine 生成器是实现此目的的方法。我应该尝试让 https://github.com/lewissbaker/cppcoro 正常工作。

Answer 2

我发现 this 存储库中的生成器运行良好：

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

可以用作

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

Answer 3

我猜你可能有点粗鲁，使用部分求和，忽略自适应范围中除第一个元素以外的所有元素：

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;

Answer 4

可变的 lambda 也可以工作

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;
        });
}

从迭代函数应用程序中创建一个范围

Make a range from Iterated function application

c++

c++20

range-v3

std-ranges