Ленивый список в C++

В Scala есть интересная коллекция — Stream. Контейнер, который представляет собой список, элементы которого вычисляются (и сохраняются после этого) при первом обращении:

The class Stream implements lazy lists where elements are only evaluated when they are needed.

Мне захотелось реализовать нечто подобное на C++.

Цель

Хочется получить контейнер, который можно использовать со стандартными алгоритмами и чтобы его элементы могли генерироваться по мере обращения к ним.

typedef lazy::list<int> list_type;

list_type fibonacci(int n1, int n2)
{
     int next = n1 + n2;
     std::cout << "fibonacci(" << n1 << ", " << n2 << ") -> " << n1 << std::endl;
     return list_type(n1, std::bind(&fibonacci, n2, next));
}

int main() 
{ 
    list_type list(fibonacci(0, 1));

    auto res3 = std::find_if(list.begin(), list.end(), [](int v){return v > 3;});
    std::cout << "first number greater 3 is " << *res3 << std::endl;
    std::cout << std::endl;

    auto res10 = std::find_if(list.begin(), list.end(), [](int v){return v > 10;});
    std::cout << "first number greater 10 is " << *res10 << std::endl;
    return 0; 
}

fibonacci(0, 1) -> 0
fibonacci(1, 1) -> 1
fibonacci(1, 2) -> 1
fibonacci(2, 3) -> 2
fibonacci(3, 5) -> 3
fibonacci(5, 8) -> 5
first number greater 3 is 5

fibonacci(8, 13) -> 8
fibonacci(13, 21) -> 13
first number greater 10 is 13

Как видно из примера, функция генерации элемента вызывается только один раз для каждого элемента, полученное значение хранится в контейнере и повторно не вычисляется.

Ограничения

Предположим, мы хотим выполнить что-то типа:

auto iter = --list.end();

Чтобы получить элемент, предшествующий end, необходимо обойти все элементы, генерируемые функцией, а это бесконечность (для примера выше). Соответственно, итератор по ленивому списку будет однонаправленный — ForwardIterator. Аналогичная ситуация будет и при получении количества элементов в списке, и при удалении последнего элемента (pop_back). Таким образом, этих методов у контейнера не будет.

Для простоты я не стал реализовывать вставку в произвольное место и удаление произвольного элемента. Исключительно из соображения, что последовательность элементов может генерироваться какой-то функцией, и при вставке/удалении эта последовательность будет нарушена. Из этих же соображений элементы не модифицируемые. Но это уже условности.

Что же получилось?

Получился список, в который можно добавлять как элементы, так и функторы, генерирующие ленивый список, который в свою очередь может содержать элементы и функторы. Удалять можно либо первый элемент (pop_front), либо все элементы (clear). Вставка элементов осуществляется в начало или конец списка.

Итератор по списку однонаправленный, не позволяющий модифицировать элементы списка.

template< typename T, typename Allocator = std::allocator<T> > class list;

template< typename T, typename Allocator = std::allocator<T> >
class list
{
public:
    typedef list<T, Allocator> self_type;
    typedef T value_type;
    typedef std::function<self_type ()> func_type;
    typedef __details_lazy_list::const_iterator<self_type> iterator;
    typedef __details_lazy_list::const_iterator<self_type> const_iterator;

    friend __details_lazy_list::const_iterator<self_type>;

    list();
    list(const self_type& that);
    list(self_type&& that);

    template<typename ... Args>
    explicit list(Args&&... args)
    {
        push_others(std::forward<Args>(args)...);
    }

    void push_back(const value_type& value);
    void push_back(value_type&& value);
    void push_back(const func_type& func);
    void push_back(func_type&& func);
    void push_back(const self_type& that);
    void push_back(self_type&& that);

    void push_front(const value_type& value);
    void push_front(value_type&& value);
    void push_front(const func_type& func);
    void push_front(func_type&& func);
    void push_front(const self_type& that);
    void push_front(self_type&& that);

    void clear();

    bool empty() const;

    const_iterator begin() const;
    const_iterator end() const;

private:
    typedef std::list<value_type, Allocator> container_type;
    typedef typename container_type::iterator inner_iterator;
    typedef value_type const * funcs_map_key_type;
    typedef std::pair<funcs_map_key_type, func_type> funcs_map_value_type;
    typedef std::map<funcs_map_key_type, func_type> funcs_map_type;

    void forward(const_iterator& iter) const;
    void insert(inner_iterator pos, self_type&& that) const;

    template<typename Arg, typename ...Args>
    void push_others(Arg&& arg, Args&&... args)
    {
        push_back(std::forward<Arg>(arg));
        push_others(std::forward<Args>(args)...);
    }

    template<typename Arg>
    void push_others(Arg&& arg)
    {
        push_back(std::forward<Arg>(arg));
    }

    void push_others() {}

    mutable container_type _cont;
    mutable funcs_map_type _funcs;
};

template< typename lazy_list_type >
class const_iterator:
    public std::iterator<std::input_iterator_tag, typename lazy_list_type::value_type>
{
    friend lazy_list_type;
public:
    typedef std::iterator<std::input_iterator_tag, typename lazy_list_type::value_type> base_type;
    const_iterator();

    typename base_type::reference const operator* () const;
    typename base_type::pointer const operator-> () const;

    const_iterator& operator++();
    const_iterator operator++(int);

    bool operator== (const const_iterator& that);
    bool operator!= (const const_iterator& that);
private:
    typedef typename lazy_list_type::inner_iterator inner_iterator;

    const_iterator(const lazy_list_type* owner, inner_iterator iter);

    const lazy_list_type* _owner;
    inner_iterator _iter;
};

В конце статьи есть ссылка на репозиторий, где можно взять реализацию с юнит-тестами.

Шаблонные параметры.

T — тип хранимых элементов

Allocator — аллокатор, используемый для размещения элементов.

Внутренние типы

Методы

Методы push_front и push_back принимают функтор, генерирующий элементы, значение хранимого элемента или другой объект типа self_type.

Конструкторы

Как это работает

Внутри используются два стандартных контейнера — std::list для хранения значений и std::map для хранения функторов. Функтор должен возвращать ленивый список, т.е. self_type. Это позволяет, во-первых, рассчитать при необходимости сразу несколько элементов, а во-вторых, не заботиться о случае, когда нет следующего значения — закончилась последовательность, в этом случае можно просто вернуть пустой контейнер.

С добавлением нового элемента все просто — он сразу добавляется во внутренний список.

При добавлении функтора проверяется, есть ли функтор, ассоциированный с элементом, после которого он добавляется (push_back). Если функтора нет, то переданный функтор добавляется в map, а в качестве ключа берется указатель на предыдущий элемент. При добавлении в начало, в пустой контейнер или после элемента, с которым уже есть ассоциированный функтор, просто вызывается метод функтора operator(), и значения из полученного контейнера вставляются в нужное место (в начало или конец), в map добавляются новые функторы, если они есть в возвращенном контейнере.

Можно было бы хранить в списке пару "значение — функтор", но мне кажется, что в процессе работы количество функторов будет существенно меньше количества вычисленных элементов, и затраты памяти в случае хранения пар будут выше.
Опять же, так как предполагаю, что количество функторов не будет очень большим, то нет особой разницы, что использовать — map или unordered_map. Единственное, что при использовании map затраты памяти будут чуть меньше, мне так кажется.

Когда инкрементируется итератор, то проверяется наличие функтора для текущего элемента, если он есть, то возвращаемое им значение добавляется в контейнер, а функтор удаляется. После этого инкрементируется итератор на внутренний список. Если функтора нет или он вернул пустой контейнер, то просто производится переход к следующему элементу во внутреннем списке.

Зачем все это?

К реализации такого списка меня подтолкнула задача Water Pouring, представленная в лекции по языку Scala. Суть в следующем: есть несколько стаканов фиксированного объема, кран, из которого можно наполнить любой стакан (мы можем наполнить стакан только полностью), и раковина, куда можно вылить содержимое стаканов. Наполняя, опустошая и переливая воду из одного стакана в другой, нужно получить заданное количество воды в одном из стаканов. Решение — последовательность действий для получения такого состояния.

Например, есть два стакана объемом 3 и 5 литров, мы хотим получить 4 литра.

Будем рассматривать текущее количество воды в каждом из стаканов как состояние. Из каждого состояния можно получить новый набор возможных состояний, применив одну из возможных операций: наполнить, вылить, перелить. Из каждого набора состояний можно получить новый набор. Чтобы не зациклиться, будем отдельно хранить полученные состояния и отбрасывать их при получении набора новых состояний.

В каждом наборе состояний будем смотреть, есть ли искомое состояние — стакан с искомым уровнем воды.

Нам понадобятся возможные варианты воздействия на текущее состояние. Каждый вариант перемещения воды будет наследовать интерфейс imove:

class imove
{
public:
    virtual state operator()(const state& cur) const = 0;
    virtual std::unique_ptr<imove> clone() const = 0;
    virtual std::string to_string() const = 0;
    virtual ~imove() {}
};

Метод to_string нужен только для вывода информации на экран.

Для этой задачи возможны следующие типы перемещения:

class fill: public imove
{
public:
    fill(unsigned glass, unsigned capacity);
    state operator()(const state& cur) const override;
    std::unique_ptr<imove> clone() const override;
    std::string to_string() const override;
protected:
    const unsigned _glass;
    const unsigned _capacity;
};

fill::fill(unsigned glass, unsigned capacity) :
    _glass(glass),
    _capacity(capacity)
{}

state fill::operator()(const state& cur) const
{
    assert(cur.size() > _glass);
    state next(cur);
    next[_glass] = _capacity;
    return next;
}
std::unique_ptr<imove> fill::clone() const
{
    return std::unique_ptr<imove>(new fill(_glass, _capacity));
}
std::string fill::to_string() const
{
    return "fill(" + std::to_string(_glass) + ")";
}

class empty: public fill
{
public:
    empty(unsigned glass);
    std::unique_ptr<imove> clone() const override;
    std::string to_string() const override;
};

empty::empty(unsigned glass) :
    fill(glass, 0)
{}

std::unique_ptr<imove> empty::clone() const
{
    return std::unique_ptr<imove>(new empty(_glass));
}

std::string empty::to_string() const
{
    return "empty(" + std::to_string(_glass) + ")";
}

class pour: public imove
{
public:
    pour(unsigned from, unsigned to, unsigned capacity_to);
    state operator()(const state& cur) const override;
    std::unique_ptr<imove> clone() const override;
    std::string to_string() const override;
protected:
    const unsigned _from;
    const unsigned _to;
    const unsigned _capacity_to;
};

pour::pour(unsigned from, unsigned to, unsigned capacity_to) :
    _from(from),
    _to(to),
    _capacity_to(capacity_to)
{}

state pour::operator()(const state& cur) const
{
    assert((cur.size() > _from) && (cur.size() > _to));
    assert(_capacity_to >= cur[_to]);
    unsigned amount = std::min(cur[_from], _capacity_to - cur[_to]);
    state next(cur);
    next[_from] -= amount;
    next[_to] += amount;
    return next;
}

std::unique_ptr<imove> pour::clone() const
{
    return std::unique_ptr<imove>(new pour(_from, _to, _capacity_to));
}

std::string pour::to_string() const
{
    return "pour(" + std::to_string(_from) + ", " + std::to_string(_to) + ")";
}

Также нужно хранить информацию о новом состоянии, а именно состояние и набор перемещений, приведших к нему. За это будет отвечать класс path:

class path
{
public:
    path(const state& initial_state);
    path(const path& that);

    void extend(imove_ptr move);
    const state& end_state() const;
    std::string to_string() const;
    bool empty() const;
private:
    std::list<imove_ptr> _history;
    state _end_state;
};

И собственно класс, который использует ленивый список и вышеперечисленные вспомогательные классы для нахождения решения:

typedef std::list<path> paths_list;

class water_pouring
{
public:
    water_pouring(std::initializer_list<unsigned> capacities);

    path solve(unsigned target);
private:
    typedef lazy::list<paths_list> list_of_paths_type;
    list_of_paths_type extend(const paths_list& paths);

    const std::vector<unsigned> _capacities;
    const std::vector<imove_ptr> _posible_moves;
    const state _initial;
    std::set<state> _explored_states;
    list_of_paths_type _paths;
};

Класс имеет два публичных метода — конструктор, который принимает емкости стаканов, и метод, возвращающий путь достижения требуемого состояния.

Приватный метод extend используется для генерации элементов ленивого списка.

Он хранит емкости стаканов, набор возможных перемещений, начальное состояние, уже "найденные" состояния и собственно ленивый список состояний с историей их получения.

std::vector<imove_ptr> create_moves(const std::vector<unsigned>& capacities)
{
    std::vector<imove_ptr> moves;
    for (size_t i = 0; i < capacities.size(); ++i)
    {
        moves.emplace_back(new empty(i));
        moves.emplace_back(new fill(i, capacities[i]));
        for (size_t j = 0; j < capacities.size(); ++j)
        {
            if (i != j)
                moves.emplace_back(new pour(i, j, capacities[j]));
        }
    }
    return moves;
}

Метод water_pouring::extend:

water_pouring::list_of_paths_type water_pouring::extend(const paths_list& paths)
{
    paths_list next;
    for (auto& cur_path: paths)
    {
        for (auto move: _posible_moves)
        {
            state next_state = (*move)(cur_path.end_state());

            if (_explored_states.find(next_state) == _explored_states.end())
            {
                path new_path(cur_path);
                new_path.extend(move);
                next.push_back(new_path);
                _explored_states.insert(next_state);
            }
        }
    }

    if (next.empty())
        return list_of_paths_type();

    return list_of_paths_type(next, std::bind(&water_pouring::extend, this, next));
}

Метод water_pouring::solve:

path water_pouring::solve(unsigned target)
{
    paths_list::const_iterator solution;
    auto it = std::find_if(
        _paths.begin(),
        _paths.end(),
        [target, &solution](const paths_list& paths) -> bool {
            solution = std::find_if(
                paths.begin(),
                paths.end(),
                [target](const path& p) -> bool {
                    auto it = std::find(
                            p.end_state().begin(),
                            p.end_state().end(),
                            target);
                    return it != p.end_state().end();
                });
            return solution != paths.end();
        });

    if (it != _paths.end())
        return *solution;

    return path(state({0}));
}

Собственно, для поиска решения используется функция std::find_if, а в качестве предиката — лямбда функция, просматривающая пути на наличие необходимого состояния. Лямбда захватывает по ссылке solution, чтобы лишний раз не проходиться по списку решений, на которые будет указывать итератор it в случае, если решение было найдено.

В итоге программа выведет следующее решение:

fill(1) pour(1, 0) empty(0) pour(1, 0) fill(1) pour(1, 0) --> (3, 4)

Придумать другую задачу, где мог бы пригодиться "ленивый" список, я не смог. Надеюсь, идея кому-нибудь приглянется.

Ссылки

• Исходный код lazy_list
• Исходный код решения Water Pouring на C++
• Исходный код решения Water Pouring на Scala
• Курс лекций Functional Programming Principles in Scala в рамках которого была расмотрена и задача Water Pouring
• Для юнит тестов использовал фреймворк Catch

Автор: Hokum

Источник