A lazy sequence.

lazy_range.cc

#include <iostream>
#include <functional>
#include <memory>

template<typename T>
class lazy_value {
    union {
        std::function<T()> _f;
        mutable T _value;
    };
    mutable T& (*_thunk)(const lazy_value&);

    static T& eval_thunk(const lazy_value& lv) {
        auto&& v = lv._f();
        lv._f.~function();
        new (&lv._value) T(std::move(v));
        lv._thunk = &get_thunk;
        return lv._value;
    }

    static T& get_thunk(const lazy_value& lv) {
        return lv._value;
    }

public:
    explicit lazy_value(std::function<T()> f)
            : _f(std::move(f))
            , _thunk(&eval_thunk)
    { }

    ~lazy_value() {
        if (_thunk == &eval_thunk) {
            _f.~function();
        } else {
            _value.~T();
        }
    }

    lazy_value(lazy_value<T>&& lv) {
        static_assert(std::is_move_constructible<T>::value, "T must be move constructible");
        static_assert(std::is_move_constructible<std::function<T()>>::value, "std::function<T()> must be move constructible");
        if (lv._thunk == &eval_thunk) {
            _f = std::move(lv._f);
            _thunk = &eval_thunk;
        } else {
            _value = std::move(lv._value);
            _thunk = &get_thunk;
        }
    }

    lazy_value& operator=(lazy_value&& other) {
        if (this != &other) {
            this->~lazy_value();
            new (this) lazy_value(std::move(other));
        }
    }

    const T& get() const & {
        return _thunk(*this);
    }

    T& get() & {
        return _thunk(*this);
    }

    T&& get() && {
        return std::move(_thunk(*this));
    }

    template <typename Func>
    friend std::ostream& operator<<(std::ostream& os, const lazy_value<Func>& lv) {
        return os << lv.get();
    }
};

template<class T>
class cell;

template<class T>
class lazy_range {
    std::shared_ptr<lazy_value<cell<T>>> _lazy_cell = nullptr;
public:
    class iterator {
        std::shared_ptr<lazy_value<cell<T>>> _current;
    public:
        struct end_iterator_tag { };
        explicit iterator(const std::shared_ptr<lazy_value<cell<T>>>& current) 
                : _current(current) {
        }
        explicit iterator(end_iterator_tag) 
                : _current(nullptr) {
        }
        iterator& operator++() {
            _current = _current->get().tail()._lazy_cell;
            return *this;
        }
        iterator operator++(int) {
            iterator i(*this);
            ++(*this);
            return i;
        }
        const T& operator*() const { return _current->get().get(); }
        const T* operator->() const { return &_current->get().get(); }
        bool operator==(const iterator& i) const { return _current == i._current; }
        bool operator!=(const iterator& i) const { return !(*this == i); }
    };
public:
    lazy_range() = default;

    explicit lazy_range(std::function<cell<T>()> f)
            : _lazy_cell(std::make_shared<lazy_value<cell<T>>>(std::move(f)))
    {}
    
    iterator begin() {
        return _lazy_cell ? iterator(_lazy_cell) : end();
    }

    iterator end() {
        return iterator(typename iterator::end_iterator_tag());
    }
};

template<class T>
class cell {
    T _v;
    lazy_range<T> _tail;
public:
    cell() = default;

    explicit cell(T v) 
        : _v(std::move(v)) { 
    }
    
    cell(T v, lazy_range<T>&& tail)
        : _v(std::move(v))
        , _tail(std::move(tail)) {
    }
    
    const T& get() const & {
        return _v;
    }

    T&& get() && {
        return std::move(_v);
    }

    const lazy_range<T>& tail() const {
        return _tail;
    }
};

template<typename Range>
bool m(Range&& r) {
    int sum = 0;
    for (auto x : r) {
        sum += x;
    }
    auto a = r.begin();
    auto b = a;
    b++;
    return a != b;
}

void foo() {
    std::vector<int> v = { 1, 2, 3};
    m(v);

    std::function<lazy_range<int>(int, int)> sum;
    sum = [&sum] (int start, int end) -> lazy_range<int> {
        if (start > end) {
            return lazy_range<int>();
        }
        return lazy_range<int>([&sum, start, end] {
            return cell<int>(start, sum(start + 1, end));
        });
    };
    m(sum(1, 3));
}