.net — Реализация Bind () (SelectMany в LINQ) без выхода (в C ++)
Я пытаюсь реализовать Ana, Cata а также Bind (от это видео) в C ++. Мне удалось Ana а также Cata, но Bind ускользает от меня
Вот что я имею для Ana а также Cata:
#define FEnumerable function<function<Option<T>(void)>(void)>
#define TResult function<function<Option<R>(void)>(void)>
template<typename T> class Option {
public:
bool HasValue;
T value;
Option(T value) : HasValue(true), value(value) { }
Option() : HasValue(false) { }
};
template<typename T> FEnumerable Ana(T seed, function<bool(T)> condition, function<T(T)> next) {
auto result = [condition, next, seed]() -> function<Option<T>()> {
return [condition, next, seed]() -> Option<T> {
static Option<T> value;
value = Option<T>(value.HasValue ? next(value.value) : seed);
if (condition(value.value))
return Option<T>(value.value);
return Option<T>();
};
};
return result;
};
template<typename T, typename R> TResult Ana(T seed, function<bool(T)> condition, function<T(T)> next, function<R(T)> translation) {
auto result = [condition, next, seed, translation]() -> function<Option<R>()> {
return [condition, next, seed, translation]() -> Option<R> {
static Option<T> value;
value = Option<T>(value.HasValue ? next(value.value) : seed);
if (condition(value.value))
return Option<R>(translation(value.value));
return Option<R>();
};
};
return result;
};
template<typename T, typename A> A Cata(FEnumerable source, A seed, function<A(A, T)> fn) {
auto e = source();
A result = seed;
Option<T> value;
while ((value = e()).HasValue)
result = fn(result, value.value);
return result;
};
template<typename T, typename A, typename R> R Cata(FEnumerable source, A seed, function<A(A, T)> fn, function<R(A)> translation) {
auto e = source();
R result = seed;
Option<T> value;
while ((value = e()).HasValue)
result = fn(result, value.value);
return translation(result);
};
До сих пор, я считаю, я проделал достойную работу. Последовательности лениво оцениваются (что было бы тривиально в .NET в наши дни с ключевым словом Yield) и предположительно легковесны. Тем не менее, я просто не могу наклонить голову вокруг лямбды, необходимые для Bind:
template<typename T> TResult Bind(FEnumerable source, function<TResult(T)> selector) {
...
}
Другими словами, Bind() должен принять FEnumerable<T> (ленивая последовательность) и функция выбора, которая принимает одно значение и возвращает последовательность значений; и затем Bind должен вызвать функцию выбора один раз для каждого входного значения, а затем вернуть все значения, возвращенные селектором, в одной большой последовательности. Но лениво Как FEnumerable<R>,
Для справки вот как это будет выглядеть в C # с yield:
foreach (var value in source)
foreach (var result in selector(value))
yield return result;
Да, без урожая немного сложнее. Вот как это будет выглядеть в C ++ без ленивых вычислений:
list<R> results;
while ((auto value = source()).HasValue)
while ((auto result = selector(value)).HasValue)
results.push_back(result);
return results;
Но мне нужна ленивая оценка, что означает вложенные лямбды. Если кто-нибудь зайдет так далеко, а голова не взорвется, пожалуйста, помогите мне.
Решение
Мы могли бы попытаться сделать подсистему, то есть последовательные результаты source когда мы перебираем его, часть состояния закрытия:
template<typename T>
TResult Bind(FEnumerable source, function<TResult(T)> selector)
{
return [source, selector]() -> function<Option<R>()>
{
auto e = source();
// Note that std::function is nullable and I am using
// this possible state!
// If this isn't std::function, making subsource an
// Option<function<Option<R>()> is always a possibility
function<Option<R>()> subsource;
return [e, subsource, selector]() -> Option<R>
{
while(!subsource) {
// This means we need to fetch a new subsource
auto candidate = e();
if(!candidate.HasValue) {
// Iteration ends here once `e` has run out
return Option<R>();
} else {
subsource = selector(candidate.value)();
}
auto result = subsource();
if(!result.HasValue) {
// We selected over an empty subsource, so let's
// try again and maybe pick a new fresh one
subsource = nullptr;
continue;
}
return result;
}
};
};
}
Обратите внимание, что это зависит от e() быть вызванным повторно, предполагая, что пустой Option<T> возвращается каждый раз после окончания итерации. В противном случае вы можете явно кодировать состояние «у нас закончились подисточники», например, с еще одной переменной замыкания.
Или, может быть, клиентский код несет бремя прекращения итерации по результату Bind как только будет достигнут конец итерации, в этом случае вам тоже нужно идти и конец source/e все еще будет достигнут только один раз.
Другие решения
Хорошо, я взял код от Люка Дантона, исправил пару вещей и заставил его работать. Вот код для всех, кто ищет решение:
template<typename T, typename R> TResult Bind(FEnumerable source, function<TResult(T)> selector) {
return [source, selector]() -> function<Option<R>()> {
auto e = source();
// Note that std::function is nullable and I am using this possible state!
// If this isn't std::function, making subsource an Option<function<Option<R>()> is always a possibility
function<Option<R>()> subsource;
return [e, subsource, selector]() mutable -> Option<R> {
while (true) {
while(!subsource) { // This means we need to fetch a new subsource
auto candidate = e();
if (!candidate.HasValue)
return Option<R>(); // Iteration ends here once `source` has run out
subsource = selector(candidate.value)();
}
auto result = subsource();
if (result.HasValue)
return result;
subsource = nullptr; // We selected over an empty subsource, so let's try again and maybe pick a new fresh one
}
return Option<R>();
};
};
}