就功能编程而言,C++能提供什么？

让我首先指出,其中大多数不是"内在的",或者我们应该说"必需"; 其中许多都不存在于值得注意的函数式语言中,理论上,许多这些特性可用于实现其他特性(例如无类型lambda演算中的高阶函数).

但是,让我们来看看:

关闭

闭包不是必需的,并且是语法糖:通过Lambda Lifting的过程,您可以将任何闭包转换为函数对象(甚至只是一个自由函数).

命名函数(C++ 03)

只是为了表明这不是一个问题,这里有一个简单的方法在C++ 03中没有lambdas这样做:

不是问题:

struct named_functor 
{
    void operator()( int val ) { std::cout << val; }
};
vector<int> v;
for_each( v.begin(), v.end(), named_functor());

匿名函数(C++ 11)

However, anonymous functions in C++11 (also called lambda functions, as they derive from the LISP history), which are implemented as non-aliasingly named function objects, can provide the same usability (and are in fact referred to as closures, so yes, C++11 does have closures):

No problem:

vector<int> v;
for_each( v.begin(), v.end(), [] (int val)
{
    std::cout << val;
} );

Polymorphic anonymous functions (C++14)

Even less of a problem, we don't need to care about the parameter types anymore in C++14:

Even Less Problem:

auto lammy = [] (auto val) { std::cout << val; };

vector<int> v;
for_each( v.begin(), v.end(), lammy);

forward_list<double> w;
for_each( w.begin(), w.end(), lammy);

I should note this fully support closure semantics, such as grabbing variables from scope, both by reference and by value, as well as being able to grab ALL variables, not merely specified ones. Lambda's are implicitly defined as function objects, providing the necessary context for these to work; usually this is done via lambda lifting.

Higher Order Functions No problem:

std::function foo_returns_fun( void );

这对你来说还不够吗？这是一家lambda工厂:

std::function foo_lambda( int foo ) { [=] () { std::cout << foo; } };

你不能创建函数,但是你可以运行对象,它们可以像普通函数一样作为std :: function传递.所以所有的功能都在那里,你可以把它放在一起.我可以补充一点,STL的大部分内容都是为了给你提供可重用的组件,用它来形成特殊的功能对象,近似于从整个布料中创建功能.

部分功能应用 没问题

std :: bind完全支持这个功能,并且非常擅长将函数转换为任意不同的函数:

void f(int n1, int n2, int n3, const int& n4, int n5)
{
    std::cout << n1 << ' ' << n2 << ' ' << n3 << ' ' << n4 << ' ' << n5 << '\n';
}

int n = 7;
// (_1 and _2 are from std::placeholders, and represent future
// arguments that will be passed to f1)
auto f1 = std::bind(f, _2, _1, 42, std::cref(n), n);

对于memoization和其他部分函数专业化技术,您必须使用包装器自己编写代码:

template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)>
memoize(ReturnType (*func) (Args...))
{
    auto cache = std::make_shared<std::map<std::tuple<Args...>, ReturnType>>();
    return ([=](Args... args) mutable  
    {
        std::tuple<Args...> t(args...);
        if (cache->find(t) == cache->end())
            (*cache)[t] = func(args...);

        return (*cache)[t];
    });
}

它可以完成,事实上它可以相对自动完成,但还没有人为你做过.}

组合器 没问题:

让我们从经典开始:map,filter,fold.

vector<int> startvec(100,5);
vector<int> endvec(100,1);

// map startvec through negate
std::transform(startvec.begin(), startvec.end(), endvec.begin(), std::negate<int>())

// fold startvec through add
int sum =  std::accumulate(startvec.begin(), startvec.end(), 0, std::plus<int>());

// fold startvec through a filter to remove 0's
std::copy_if (startvec.begin(), startvec.end(), endvec.begin(), [](int i){return !(i==0);} );

这些非常简单,但是标题<functional>,<algorithm>并<numerical>提供了许多函子(可以作为函数调用的对象),可以放入这些通用算法,以及其他通用算法.它们共同构成了构成特征和行为的强大能力.

让我们尝试更实用的功能:SKI可以很容易地实现,并且非常实用,源于无类型的lambda演算:

template < typename T >
T I(T arg)
{
    return arg;
}

template < typename T >
std::function<T(void*)> K(T arg)
{
return [=](void*) -> T { return arg; };
}

template < typename T >
T S(T arg1, T arg2, T arg3)
{
return arg1(arg3)(arg2(arg1));
}

These are very fragile; in effect, these must be of a type which returns it's own type and takes a single argument of their own type; such constraints would then allow for all the functional reasoning of the SKI system to be applied safely to the composition of these. With a little work, and some template metaprogramming, much of this could even be done at compile time through the magic of expression templates to form highly optimized code.

Expression templates, as an aside, are a technique in which an expression, usually in the form of a series of operations or sequential order of code, is based as an argument to a template. Expression templates therefore are compile time combinators; they are highly efficient, type safe, and effectively allow for domain specific languages to be embedded directly into C++. While these are high level topics, they are put to good use in the standard library and in boost::spirit, as shown below.

Spirit Parser Combinators

template <typename Iterator>
bool parse_numbers(Iterator first, Iterator last)
{
    using qi::double_;
    using qi::phrase_parse;
    using ascii::space;

    bool r = phrase_parse(
    first,                          
    last,                           
    double_ >> (char_(',') >> double_),   
    space                           
    );

    if (first != last) // fail if we did not get a full match
        return false;
    return r;
}

This identifies a comma deliminated list of numbers. double_ and char_ are individual parsers that identify a single double or a single char, respectively. Using the >> operator, each one passes themselves to the next, forming a single large combined parser. They pass themselves via templates, the "expression" of their combined action building up. This is exactly analogous to traditional combinators, and is fully compile time checked.

Valarray

valarray, a part of the C++11 standard, is allowed to use expression templates (but not required, for some odd reason) in order to facilitate efficiency of transforms. In theory, any number of operations could be strung together, which would form quite a large messy expression which can then be aggressively inlined for speed. This is another form of combinator.

I suggest this resource if you wish to know more about expression templates; they are absolutely fantastic at getting all the compile time checks you wish done, as well as improving the re-usability of code. They are hard to program, however, which is why I would advise you find a library that contains the idioms you want instead of rolling your own.

Function Signatures As Types No problem

void my_int_func(int x)
{
    printf( "%d\n", x );
}

void (*foo)(int) = &my_int_func;

or, in C++, we'd use std::function:

std::function<void(int)> func_ptr = &my_int_func;

Type Inference No problem

Simple variables typed by inference:

// var is int, inferred via constant
auto var = 10;

// y is int, inferred via var
decltype(var) y = var;

Generic type inference in templates:

template < typename T, typename S >
auto multiply (const T, const S) -> decltype( T * S )
{
    return T * S;
}

Furthermore, this can be used in lambdas, function objects, basically any compile time expression can make use of decltype for compile time type inference.

But that's not what you are really after here, are you? You want type deduction as well as type restriction, you want type reconstruction and type derivations. All of this can be done with concepts, but they are not part of the language yet.

So, why don't we just implement them? boost::concepts, boost::typeerasure, and type traits (descendant from boost::tti and boost::typetraits) can do all of this.

Want to restrict a function based on some type? std::enable_if to the rescue!

Ah, but that's ad hoc right? That would mean for any new type you'd want to construct, you'd need to do boilerplate, etc etc. Well, no, but here's a better way!

template<typename RanIter>
BOOST_CONCEPT_REQUIRES(
    ((Mutable_RandomAccessIterator<RanIter>))
    ((LessThanComparable<typename Mutable_RandomAccessIterator<RanIter>::value_type>)),
    (void)) // return type
stable_sort(RanIter,RanIter);

Now your stable_sort can only work on types that match your stringent requirements. boost::concept has tons of prebuilt ones, you just need to put them in the right place.

If you want to call different functions or do different things off types, or disallow types, use type traits, it's now standard. Need to select based on parts of the type, rather than the full type? Or allow many different types, which have a common interface, to be only a single type with that same interface? Well then you need type erasure, illustrated below:

Type Polymorphism No problem

Templates, for compile time type polymorphism:

std::vector<int> intvector;
std::vector<float> floatvector;
...

Type erasure, for run time and adaptor based type polymorphism:

boost::any can_contain_any_type;
std::function can_call_any_function;
any_iterator can_iterator_any_container;
...

Type erasure is possible in any OO language, and involves setting up small function objects which derive from a common interface, and translate internal objects to it. With a little boost MPL boilerplate, this is fast, easy, and effective. Expect to see this become real popular soon.

Immutable Datastructures Not syntax for explicit constructions, but possible:

Can be done via not using mutators or template metaprogramming. As this is a lot of code (a full ADT can be quite large), I will link you here, to show how to make an immutable singly linked list.

To do this at compile time would require a good amount of template magic, but can be done more easily with constexpr. This is an exercise for the reader; I don't know of any compile time libraries for this off the top of my head.

However, making an immutable datastructure from the STL is quite easy:

const vector<int> myvector;

There you are; a data structure that cannot be changed! In all seriousness, finger tree implementations do exist and are probably your best bet for associative array functionality. It's just not done for you by default.

Algebraic data types No problem:

The amazing boost::mpl allows you to constrain uses of types, which along with boost::fusion and boost::functional to do anything at compile time that you would want in regards to ADT. In fact, most of it is done for you:

#include <boost/mpl/void.hpp>
//A := 1
typedef boost::mpl::void_ A;

As stated earlier, a lot of the work isn't done for you in a single place; for example, you'd need to use boost::optional to get optional types, and mpl to get unit type, as seen above. But using relatively simple compile time template mechanics, you can do recursive ADT types, which means you can implement generalized ADT's. As the template system is turing complete, you have a turing complete type checker and ADT generator at your disposal.

It's just waiting for you to bring the pieces together.

Variant based ADT's

boost::variant provides type checked unions, in addition to the original unions in the language. These can be used with no fuss, drop in:

boost::variant< int, std::string > v;

This variant, which can be int or string, can be assigned either way with checking, and you can even do run time variant based visitation:

class times_two_visitor
    : public boost::static_visitor<>
{
public:
    void operator()(int & i) const
    {
        i *= 2;
    }
    void operator()(std::string & str) const
    {
        str += str;
    }
};

Anonymous/Ad-hoc data structures No problem:

Of course we have tuples! You could use structs if you like, or:

std::tuple<int,char> foo (10,'x');

You can also perform a good deal of operations on tuples:

// Make them
auto mytuple = std::make_tuple(3.14,"pi");
std::pair<int,char> mypair (10,'a');

// Concatenate them
auto mycat = std::tuple_cat ( mytuple, std::tuple<int,char>(mypair) );

// Unpack them
int a, b;
std::tie (a, std::ignore, b, std::ignore) = mycat; 

Tail Recursion No explicit support, iteration is sufficient

This is not supported or mandated in Common LISP, though it is in Scheme, and therefore I don't know if you can say it's required. However, you can easily do tail recursion in C++:

std::size_t get_a_zero(vector<int>& myints, std::size_t a ) {
   if ( myints.at(a) == 0 ) {
      return a;
   }
   if(a == 0) return myints.size() + 1;

   return f(myints, a - 1 );   // tail recursion
}

Oh, and GCC will compile this into an iterative loop, no harm no foul. While this behavior is not mandated, it is allowable and is done in at least one case I know of (possibly Clang as well). But we don't need tail recursion: C++ totally is fine with mutations:

std::size_t get_a_zero(vector<int>& myints, std::size_t a ) {
   for(std::size_t i = 0; i <= myints.size(); ++i){
       if(myints.at(i) == 0) return i;
    }
    return myints.size() + 1;
}

Tail recursion is optimized into iteration, so you have exactly as much power. Furthermore, through the usage of boost::coroutine, one can easily provide usage for user defined stacks and allow for unbounded recursion, making tail recursion unnecessary. The language is not actively hostile to recursion nor to tail recursion; it merely demands you provide the safety yourself.

Pattern Matching No problem:

This can easily be done via boost::variant, as detailed elsewhere in this, via the visitor pattern:

class Match : public boost::static_visitor<> {
public:
    Match();//I'm leaving this part out for brevity!
    void operator()(const int& _value) const {
       std::map<int,boost::function<void(void)>::const_iterator operand 
           = m_IntMatch.find(_value);
       if(operand != m_IntMatch.end()){
           (*operand)();
        }
        else{
            defaultCase();
        }
    }
private:
    void defaultCause() const { std::cout << "Hey, what the..." << std::endl; }
    boost::unordered_map<int,boost::function<void(void)> > m_IntMatch;
};

This example, from this very charming website shows how to gain all the power of Scala pattern matching, merely using boost::variant. There is more boilerplate, but with a nice template and macro library, much of that would go away.

In fact, here is a library that has done all that for you:

#include <utility>
#include "match.hpp"                // Support for Match statement

typedef std::pair<double,double> loc;

// An Algebraic Data Type implemented through inheritance
struct Shape
{
    virtual ~Shape() {}
};

struct Circle : Shape
{
    Circle(const loc& c, const double& r) : center(c), radius(r) {}
    loc    center;
    double radius;
};

struct Square : Shape
{
    Square(const loc& c, const double& s) : upper_left(c), side(s) {}
    loc    upper_left;
    double side;
};

struct Triangle : Shape
{
    Triangle(const loc& a, const loc& b, const loc& c) : first(a), second(b), third(c) {}
    loc first;
    loc second;
    loc third;
};

loc point_within(const Shape* shape)
{
    Match(shape)
    {
       Case(Circle)   return matched->center;
       Case(Square)   return matched->upper_left;
       Case(Triangle) return matched->first;
       Otherwise()    return loc(0,0);
    }
    EndMatch
}

int main()
{
    point_within(new Triangle(loc(0,0),loc(1,0),loc(0,1)));
    point_within(new Square(loc(1,0),1));
    point_within(new Circle(loc(0,0),1));
}

As provided by this lovely stackoverflow answer As you can see, it is not merely possible but also pretty.

Garbage Collection Future standard, allocators, RAII, and shared_ptr are sufficient

While C++ does not have a GC, there is a proposal for one that was voted down in C++11, but may be included in C++1y. There are a wide variety of user defined ones you can use, but the C++ does not need garbage collection.

C++ has an idiom know as RAII to deal with resources and memory; for this reason, C++ has no need for a GC as it does not produce garbage; everything is cleaned up promptly and in the correct order by default. This does introduce the problem of who owns what, but this is largely solved in C++11 via shared pointers, weak pointers, and unique pointers:

// One shared pointer to some shared resource
std::shared_ptr<int> my_int (new int);

// Now we both own it!
std::shared_ptr<int> shared_int(my_int);

// I can use this int, but I cannot prevent it's destruction
std::weak_ptr<int> weak_int (shared_int);

// Only I can ever own this int
std::unique_ptr<int> unique_int (new int);

These allow you to provide a much more deterministic and user controlled form of garbage collection, that does not invoke any stop the world behavior.

That not easy enough for you? Use a custom allocator, such as boost::pool or roll your own; it's relatively easy to use a pool or arena based allocator to get the best of both worlds: you can easily allocate as freely as you like, then simply delete the pool or arena when you are done. No fuss, no muss, and no stopping the world.

However, in modern C++11 design, you would almost never use new anyway except when allocating into a*_ptr, so the wish for a GC is not necessary anyway.

In Summary

C++ has plenty of functional language features, and all of the ones you listed can be done, with the same power and expression ability of Haskell or Lisp. However, most of these features are not built in by default; this is changing, with the introduction of lambda's (which fill in the functional parts of the STL), and with the absorption of boost into the standard language.

Not all of these idioms are the most palatable, but none of them are particularly onerous to me, or unamendable to a few macros to make them easier to swallow. But anyone who says they are not possible has not done their research, and would seem to me to have limited experience with actual C++ programming.

从您的列表中,C++可以:

功能签名作为类型

类型多态(但不是像许多函数式语言中的第一类)

不可变数据结构(但它们需要更多工作)

它只能做非常有限的形式:

高阶函数/闭包(基本上,没有GC,大多数更有趣的高阶函数习惯用法都是无法使用的)

adhoc数据结构(如果你的意思是轻量级结构类型的形式)

你基本上可以忘记:

代数数据类型和模式匹配

部分函数应用程序(通常需要隐式闭包)

类型推断(尽管在C++版本中人们称之为"类型推断",它与你用Hindley/Milner a la ML或Haskell得到的结果相差甚远)

尾调用(一些编译器可以优化尾部自递归的一些有限情况,但是没有保证,并且语言对一般情况(指向堆栈,析构函数以及所有这些)的指针有积极的敌意)

垃圾收集(你可以使用Boehm的保守收藏家,但它不是真正的替代品,而且不太可能与第三方代码和平共存)

总的来说,尝试做任何超出琐事的功能都将是C++中的一个主要痛苦或彻底无法使用.甚至那些容易的事情往往需要如此多的样板和沉重的符号,以至于它们不是很有吸引力.(有些C++爱好者喜欢声称相反,但坦率地说,他们中的大多数似乎对实际的函数式编程有相当有限的经验.)