In Scala there is an interesting collection - Stream. The container, which is a list, whose elements are calculated (and saved after this) at the first call:

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

I wanted to implement something similar in C ++.

purpose

I want to get a container that can be used with standard algorithms and that its elements can be generated as they are accessed.


As you can see from the example, the function of generating an element is called only once for each element, the resulting value is stored in the container and is not recalculated.

Restrictions

Suppose we want to do something like:

 auto iter = --list.end(); 

To get the element preceding the end, you must go around all the elements generated by the function, and this is infinity (for the example above). Accordingly, the lazy list iterator will be unidirectional - ForwardIterator. A similar situation will occur when getting the number of items in the list, and when deleting the last item (pop_back). Thus, the container will not have these methods.

For simplicity, I did not implement the insertion in an arbitrary place and the removal of an arbitrary element. Exclusively from the consideration that the sequence of elements can be generated by some function, and when inserting / deleting this sequence will be broken. From the same considerations, the elements are not modifiable. But this is already a convention.

What happened?

The result is a list in which you can add both elements and functors that generate a lazy list, which in turn can contain elements and functors. You can delete either the first element (pop_front) or all elements (clear). Elements are inserted at the beginning or end of the list.

The list iterator is unidirectional, not allowing to modify the elements of the list.

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

At the end of the article there is a link to the repository, where you can get the implementation with unit tests.

Template parameters.

T - type of stored items

Allocator - Allocator used to place elements.

Internal types

Type of	Description
value_type	T
self_type	own type
func_type	The type of functor used to generate the element. The functor returns a self_type object.
iterator	constant forward iterator
const_iterator	constant forward iterator

Methods

Method	Description
push_front	insert in the beginning
push_back	insert at the end
empty	check if the container is empty
clear	delete all items
pop_front	delete first item

The push_front and push_back methods accept a functor that generates elements, the value of a stored element, or another object of type self_type.

Constructors

Signature	Description
list();	Creates an empty container
template<typename ... Args> explicit list(Args&&... args)	Creates a container and puts the transferred items into it. Values ​​of the following types can be transferred: value_type func_type self_type

How it works

Inside, two standard containers are used - std :: list for storing values ​​and std :: map for storing functors. The functor should return a lazy list, i.e. self_type This allows, first, to calculate several elements at once if necessary, and secondly, not to care about the case when there is no next value — the sequence has ended, in this case, you can simply return the empty container.

With the addition of a new element, everything is simple - it is immediately added to the internal list.

When adding a functor, it is checked whether there is a functor associated with the element after which it is added (push_back). If there is no functor, then the passed functor is added to the map, and the pointer to the previous element is taken as the key. When adding to the beginning, in an empty container or after an element with which an associated functor already exists, the operator () method of the functor is simply called, and the values ​​from the resulting container are inserted in the right place (at the beginning or end), new functors are added to the map, they are in the returned container.

One could store in the list a pair of "value - functor", but it seems to me that in the process of work the number of functors will be significantly less than the number of calculated elements, and the memory costs in the case of storing pairs will be higher.
Again, since I assume that the number of functors will not be very large, there is no particular difference what to use - map or unordered_map. The only thing is that when using map memory costs will be slightly less, I think so.

When an iterator is incremented, the presence of the functor for the current element is checked, if it exists, the value returned by it is added to the container, and the functor is deleted. After that, the iterator is incremented to the internal list. If there is no functor or it returns an empty container, then it simply moves to the next element in the internal list.

Why all this?

The implementation of such a list pushed me to the task of Water Pouring, presented in a lecture on the language of Scala. The point is this: there are several glasses of fixed volume, a faucet from which any glass can be filled (we can only fill the glass completely), and a sink where you can pour the contents of the glasses. Filling, emptying and pouring water from one glass to another, you need to get the specified amount of water in one of the glasses. The solution is a sequence of actions to obtain such a state.

For example, there are two glasses of 3 and 5 liters, we want to get 4 liters.


We will consider the current amount of water in each of the glasses as a state. From each state, you can get a new set of possible states by applying one of the possible operations: fill, pour, pour. From each set of states you can get a new set. In order not to loop, we will separately store the obtained states and discard them when receiving a set of new states.


In each set of states, we will look at whether the desired state is a glass with the desired water level.

We will need possible options to influence the current state. Each water transfer option will inherit the imove interface:

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

The to_string method is to_string needed to display information on the screen.

The following types of movement are possible for this task:




You also need to store information about the new state, namely the state and the set of movements that led to it. The path class will be responsible for this:

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

And the class itself, which uses the lazy list and the above-mentioned auxiliary classes to find a solution:

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

The class has two public methods — a constructor that takes the capacity of the glasses, and a method that returns the path to achieve the desired state.

The private extend method is used to generate lazy list items.

It stores the capacity of the glasses, a set of possible displacements, the initial state, the already “found” states and the actually lazy list of states with a history of their receipt.


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

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

Actually, to find a solution, the function std :: find_if is used, and the predicate is a lambda function, which looks at the paths to the presence of the required state. Lambda captures the solution link so that once again it does not go through the list of solutions that will be pointed to by it if the solution has been found.

As a result, the program will display the following solution:

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

I could not come up with another task where the lazy list could be useful. I hope the idea will attract someone.

Links

• Source code lazy_list
• C ++ Water Pouring Solution Source Code
• Scala Water Pouring Source Code
• A lecture course on Functional Programming Principles in Scala, within the framework of which the Water Pouring task was reviewed
• For unit tests used the Catch framework