Давайте возьмем Haskell в качестве нашего вдохновения - он ленив до глубины души.
Кроме того, давайте помнить, как Linq в C # использует перечислители монадическим (ургх - вот слово - извините) способом.
Не в последнюю очередь, давайте помнить, что сопрограммы должны предоставлять программистам. А именно, разделение вычислительных шагов (например, производителя-потребителя) друг от друга.
И давайте попробуем подумать о том, как сопрограммы относятся к ленивой оценке.
Все вышеперечисленное как-то связано.
Далее, давайте попробуем извлечь наше личное определение того, что означает "ленивый".
Одна интерпретация такова: мы хотим сформулировать наши вычисления составным образом, до их выполнения. Некоторые из тех частей, которые мы используем для составления нашего полного решения, могут очень хорошо опираться на огромные (иногда бесконечные) источники данных, а наши полные вычисления также приводят к конечному или бесконечному результату.
Давайте разберемся с конкретным кодом. Нам нужен пример для этого! Здесь я выбрал fizzbuzz «проблему» в качестве примера, просто потому, что есть какое-то хорошее, ленивое решение.
В Хаскеле это выглядит так:
module FizzBuzz
( fb
)
where
fb n =
fmap merge fizzBuzzAndNumbers
where
fizz = cycle ["","","fizz"]
buzz = cycle ["","","","","buzz"]
fizzBuzz = zipWith (++) fizz buzz
fizzBuzzAndNumbers = zip [1..n] fizzBuzz
merge (x,s) = if length s == 0 then show x else s
Функция Haskell cycle создает бесконечный список (конечно, ленивый!) Из конечного списка, просто повторяя значения в конечном списке навсегда. В энергичном стиле программирования, написание чего-то подобного вызовет сигнал тревоги (переполнение памяти, бесконечные циклы!). Но не так на ленивом языке. Хитрость в том, что ленивые списки вычисляются не сразу. Возможно никогда. Обычно только столько, сколько требуется для следующего кода.
Третья строка в блоке where выше создает еще одну ленту !! list путем объединения бесконечных списков fizz и buzz с помощью единственного рецепта двух элементов «объединить строковый элемент из любого входного списка в одну строку». Опять же, если бы это было немедленно оценено, нам пришлось бы ждать, пока на нашем компьютере не хватит ресурсов.
В 4-й строке мы создаем кортежи членов конечного ленивого списка [1..n] с нашим бесконечным ленивым списком fizzbuzz. Результат все еще ленивый.
Даже в основной части нашей функции fb нет необходимости стремиться. Вся функция возвращает список с решением, которое само по себе является -агентным. Вы также можете думать о результате fb 50 как о вычислении, которое вы можете (частично) оценить позже. Или сочетать с другими вещами, что приводит к еще большей (ленивой) оценке.
Итак, чтобы начать работу с нашей версией "fizzbuzz" на C ++, нам нужно подумать о том, как объединить частичные этапы наших вычислений в более крупные биты вычислений, каждый из которых отрисовывает данные предыдущих шагов по мере необходимости.
Вы можете увидеть полную историю в моей сути .
Вот основные идеи, стоящие за кодом:
Заимствуя из C # и Linq, мы «изобретаем» универсальный тип с состоянием Enumerator, который содержит
- текущее значение частичного вычисления
- Состояние частичного вычисления (чтобы мы могли получить последующие значения)
- Рабочая функция, которая создает следующее состояние, следующее значение и логическое значение, которое указывает, есть ли еще данные или закончилось ли перечисление.
Для возможности создания Enumerator<T,S> экземпляра с помощью мощности . (точка) этот класс также содержит функции, заимствованные из классов типов Haskell, таких как Functor и Applicative.
Рабочая функция для перечислителя всегда имеет вид: S -> std::tuple<bool,S,T, где S - переменная универсального типа, представляющая состояние, а T - переменная универсального типа, представляющая значение - результат шага вычисления.
Все это уже видно в первых строках определения класса Enumerator.
template <class T, class S>
class Enumerator
{
public:
typedef typename S State_t;
typedef typename T Value_t;
typedef std::function<
std::tuple<bool, State_t, Value_t>
(const State_t&
)
> Worker_t;
Enumerator(Worker_t worker, State_t s0)
: m_worker(worker)
, m_state(s0)
, m_value{}
{
}
// ...
};
Итак, все, что нам нужно для создания конкретного экземпляра перечислителя, нам нужно создать рабочую функцию, иметь начальное состояние и создать экземпляр Enumerator с этими двумя аргументами.
Вот пример - функция range(first,last) создает конечный диапазон значений. Это соответствует ленивому списку в мире Haskell.
template <class T>
Enumerator<T, T> range(const T& first, const T& last)
{
auto finiteRange =
[first, last](const T& state)
{
T v = state;
T s1 = (state < last) ? (state + 1) : state;
bool active = state != s1;
return std::make_tuple(active, s1, v);
};
return Enumerator<T,T>(finiteRange, first);
}
И мы можем использовать эту функцию, например, так: auto r1 = range(size_t{1},10); - Мы создали ленивый список из 10 элементов!
Теперь все, чего не хватает для нашего "вау" опыта, это посмотреть, как мы можем составить счетчики.
Возвращаясь к функции Haskells cycle, что довольно круто. Как бы это выглядело в нашем мире C ++? Вот оно:
template <class T, class S>
auto
cycle
( Enumerator<T, S> values
) -> Enumerator<T, S>
{
auto eternally =
[values](const S& state) -> std::tuple<bool, S, T>
{
auto[active, s1, v] = values.step(state);
if (active)
{
return std::make_tuple(active, s1, v);
}
else
{
return std::make_tuple(true, values.state(), v);
}
};
return Enumerator<T, S>(eternally, values.state());
}
Он принимает перечислитель в качестве входных данных и возвращает перечислитель. Локальная (лямбда) функция eternally просто сбрасывает входное перечисление в его начальное значение всякий раз, когда у него заканчиваются значения и вуаля - у нас есть бесконечная, постоянно повторяющаяся версия списка, который мы дали в качестве аргумента :: auto foo = cycle(range(size_t{1},3)); И мы можем уже безбожно сочиняем наши ленивые «вычисления».
zip - хороший пример, показывающий, что мы также можем создать новый перечислитель из двух входных перечислителей. Результирующий перечислитель выдает столько значений, сколько меньше любого из входных перечислителей (кортежи с 2 элементами, по одному для каждого входного перечислителя). Я реализовал zip внутри class Enumerator. Вот как это выглядит:
// member function of class Enumerator<S,T>
template <class T1, class S1>
auto
zip
( Enumerator<T1, S1> other
) -> Enumerator<std::tuple<T, T1>, std::tuple<S, S1> >
{
auto worker0 = this->m_worker;
auto worker1 = other.worker();
auto combine =
[worker0,worker1](std::tuple<S, S1> state) ->
std::tuple<bool, std::tuple<S, S1>, std::tuple<T, T1> >
{
auto[s0, s1] = state;
auto[active0, newS0, v0] = worker0(s0);
auto[active1, newS1, v1] = worker1(s1);
return std::make_tuple
( active0 && active1
, std::make_tuple(newS0, newS1)
, std::make_tuple(v0, v1)
);
};
return Enumerator<std::tuple<T, T1>, std::tuple<S, S1> >
( combine
, std::make_tuple(m_state, other.state())
);
}
Обратите внимание, как «объединение» также заканчивается объединением состояния обоих источников и значений обоих источников.
Поскольку этот пост уже TL; DR; для многих здесь ...
Резюме
Да, ленивая оценка может быть реализована в C ++. Здесь я сделал это, позаимствовав имена функций из haskell, а парадигму - из перечислителей C # и Linq. Там может быть сходство с питонами itertools, кстати. Я думаю, что они следовали подобному подходу.
Моя реализация (см. Ссылку на gist выше) является всего лишь прототипом, а не рабочим кодом, кстати. Так что никаких гарантий с моей стороны. Тем не менее, он хорошо подходит для демонстрации общего кода.
И что это был бы за ответ без финальной версии fizzbuz для C ++, а? Вот оно:
std::string fizzbuzz(size_t n)
{
typedef std::vector<std::string> SVec;
// merge (x,s) = if length s == 0 then show x else s
auto merge =
[](const std::tuple<size_t, std::string> & value)
-> std::string
{
auto[x, s] = value;
if (s.length() > 0) return s;
else return std::to_string(x);
};
SVec fizzes{ "","","fizz" };
SVec buzzes{ "","","","","buzz" };
return
range(size_t{ 1 }, n)
.zip
( cycle(iterRange(fizzes.cbegin(), fizzes.cend()))
.zipWith
( std::function(concatStrings)
, cycle(iterRange(buzzes.cbegin(), buzzes.cend()))
)
)
.map<std::string>(merge)
.statefulFold<std::ostringstream&>
(
[](std::ostringstream& oss, const std::string& s)
{
if (0 == oss.tellp())
{
oss << s;
}
else
{
oss << "," << s;
}
}
, std::ostringstream()
)
.str();
}
И ... чтобы продвинуться дальше - вот вариант fizzbuzz, который возвращает «бесконечный список» вызывающему:
typedef std::vector<std::string> SVec;
static const SVec fizzes{ "","","fizz" };
static const SVec buzzes{ "","","","","buzz" };
auto fizzbuzzInfinite() -> decltype(auto)
{
// merge (x,s) = if length s == 0 then show x else s
auto merge =
[](const std::tuple<size_t, std::string> & value)
-> std::string
{
auto[x, s] = value;
if (s.length() > 0) return s;
else return std::to_string(x);
};
auto result =
range(size_t{ 1 })
.zip
(cycle(iterRange(fizzes.cbegin(), fizzes.cend()))
.zipWith
(std::function(concatStrings)
, cycle(iterRange(buzzes.cbegin(), buzzes.cend()))
)
)
.map<std::string>(merge)
;
return result;
}
Стоит показать, так как вы можете узнать из него, как уклониться от вопроса, каков точный тип возврата этой функции (поскольку это зависит от реализации одной функции, а именно от того, как код комбинирует перечислители).
Также это демонстрирует, что мы должны были переместить векторы fizzes и buzzes за пределы области действия функции, чтобы они оставались неизменными, когда в конце концов ленивый механизм создает значения. Если бы мы этого не сделали, код iterRange(..) сохранил бы итераторы для векторов, которые давно ушли.