从迭代器推导参数类型

Question

我试图在foldr中实现Haskell函数C++：

template <typename F, typename ForwardIter, typename B>
B foldr(F f, B z0, ForwardIter begin, ForwardIter end)
{
    if (begin == end) {
        return z0;
    } else {
        auto lval = *begin;
        return f(lval, foldr(f, z0, ++begin, end));
    }
}

我的问题是。我可以使用F的信息将std::function的类型推断为ForwardIter吗？虚型:F= std::function<B(typename ForwardIter::value, B)>

考虑到指示参数之间关系的Haskell签名(a->b->b)->b->[a]->b，我想知道是否有一种方法可以在C++中指定这种关系。所以当我把一个错误的函子传递给第一个参数时，编译器会告诉我她需要一个具有精确签名的函子。

Answer 1

考虑到指示参数之间关系的Haskell签名(a->b->b)->b->[a]->b，我想知道是否有一种方法可以在C++中指定这种关系。

是的，有。不过，你会误以为用std::function就能做到这一点。std::function是一个具有已知签名的可调用对象的容器。为什么一个人要把东西包装在一个容器里，仅仅是为了把它作为一个参数传递？

您可以简单地使用尾部返回类型，例如：

template<typename F, 
         typename ForwardIter, 
         typename B,
         typename ValueType = typename std::iterator_traits<ForwardIter>::value_type>
auto foldr(F f, B z0, ForwardIter begin, ForwardIter end)
-> decltype(std::declval<F&>()(std::declval<ValueType&>(), std::declval<B&>())) { ...

您还可以为您的需求定义一个特征(例如，F可以使用迭代器的value_type参数和另一个B类型的参数进行调用，并返回B)，并使用该特性拒绝其他可调用项。

template<typename F, 
         typename ForwardIter, 
         typename B>
B foldr(F f, B z0, ForwardIter begin, ForwardIter end)
{
    using ValueType = typename std::iterator_traits<ForwardIter>::value_type;
    static_assert(is_callable<F&, B(ValueType&, B&)>(), "F must be callable with signature B(B, B)");
    ...

如果不能用正确的签名调用对象，这将导致错误。如果只希望将重载排除在过载分辨率之外，则可以将SFINAE与enable_if结合使用。

template<typename F, 
         typename ForwardIter, 
         typename B,
         typename ValueType = typename std::iterator_traits<ForwardIter>::value_type,
         typename std::enable_if<is_callable<F&, B(ValueType&,B&)>::value, int>::type = 0>
B foldr(F f, B z0, ForwardIter begin, ForwardIter end) { ...

或者你也可以利用这个特性来分配标签。或者别的什么。重要的一点是，这不是std::function的目的(这不仅仅是运行时开销的问题；它还会使某些代码在不依赖于std::function的情况下正常工作时无法编译)。

尽管如此，如果我编写这个函数，我会或多或少地像这样开始(注意所有的引用语义和转发)：

template<typename F, 
         typename It, 
         typename B,
         typename Reference = typename std::iterator_traits<It>::reference,
         typename std::enable_if<is_callable<F&, B(Reference&&,B)>::value, int>::type = 0>
B foldr(F&& f, B&& z0, It first, It last)
{
    if (first == end) {
        return std::forward<B>(z0);
    } else {
        auto&& r = *first; // must do here to avoid order of evaluation woes
        // don't forward f because we cannot "destroy" it twice, i.e. no moving!
        return f(std::forward<decltype(r)>(r), foldr(f, std::forward<B>(z0), ++first, end));
    }
}

Answer 2

使用decltype关键字。代码中使用auto表示您正在使用C++11。在函数顶部：

typedef decltype(*begin) ForwardIterValue;          // type of result of applying dereference operator
typedef std::function< B(ForwardIterValue, B) > F;  // desired function object

正如维基百科条目所说，

它的主要用途是在泛型编程中，通常很难，甚至不可能表示依赖于模板参数的类型。

根据构造函数对象的方式，使用auto也是可能的。

Answer 3

是的，这是可能的。好处是，如果您使用许多不同的函数重复调用foldr，但是ForwardIterator和B的类型相同，则只会得到生成代码的一个版本，从而(可能)得到一个更小的可执行文件。

然而，我的直觉是“不要这么做”。正是由于std::function的泛型属性，编译器很少有可能内联您对f()的调用；反过来，它可能很难解除对foldr的递归调用。另一方面，如果允许它为每个函数合成一个专门的foldr，则获得高度优化的实现的机会要大得多。如果f是一些简单的东西，如std::plus或类似的东西，则尤其如此。

例如，使用Clang 3.1 at -03尝试如下：

std::vector<int> v{1, 2, 3, 4};
std::cout << foldr(std::plus{}, 5, v.begin(), v.end()) << std::endl;

导致对foldr的调用被完全消除。使用std::function的同一版本代码的开销要大得多。

当然，本能和直觉是决定是否做某事的特别糟糕的方式，当涉及到C++模板时，这种方式会加倍。我建议两种方法都试一试，看看哪一种更好。