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

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

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

Цель

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


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

Ограничения

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

auto iter = --list.end();

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

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

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

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

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

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

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

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

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

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

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

Тип	Описание
value_type	T
self_type	собственный тип
func_type	тип функтора, используемого для генерации элемента. Функтор возвращает объект self_type.
iterator	константный forward итератор
const_iterator	константный forward итератор

Методы

Метод	Описание
push_front	вставка в начало
push_back	вставка в конец
empty	проверка, является ли контейнер пустым
clear	удалить все элементы
pop_front	удалить первый элемент

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

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

Сигнатура	Описание
list();	Создает пустой контейнер
template<typename ... Args> explicit list(Args&&... args)	Cоздает контейнер и помещает в него переданные элементы. Могут быть переданы значения следующих типов: value_type func_type 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 нужен только для вывода информации на экран.

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




Также нужно хранить информацию о новом состоянии, а именно состояние и набор перемещений, приведших к нему. За это будет отвечать класс 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 используется для генерации элементов ленивого списка.

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


Метод 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