1

我正在尝试在 C++中实现Ana,Cata和Bind（来自此视频）。我设法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 关键字将是微不足道的）并且可能是轻量级的。但是，我只是无法在以下所需的 lambdas 周围弯曲我的头Bind：

template<typename T> TResult Bind(FEnumerable source, function<TResult(T)> selector) {
    ...
}

也就是说，Bind()需要接受一个FEnumerable<T>（惰性序列）和一个接受单个值并返回一个值序列的选择器函数；然后 Bind 必须为每个输入值调用一次选择器函数，然后将选择器返回的所有值按一个大序列返回。却懒洋洋的。作为一个FEnumerable<R>.

作为参考，下面是它在 C# 中的外观，带有产量：

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;

但我需要惰性求值，这意味着嵌套的 lambda。如果有人在没有爆炸的情况下走到这一步，请帮助我。

4

2 回答 2

1

我们可以尝试创建一个子源，即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仍然只会到达一次。

于 2013-05-26T01:56:16.253 回答
1

好的，我从 Luc Danton 那里获取了代码，修复了一些问题并让它工作。这是寻找解决方案的其他人的代码：

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>();
        };
    };
}
于 2013-05-26T03:12:03.473 回答