Возможны ли в С++ внутренние возможности FP?
ОБНОВЛЕНО:
Из вашего списка, С++ может делать:
Он может делать только очень ограниченные формы:
Вы можете существенно забыть о:
В целом, попытка сделать что-либо функциональное, выходящее за рамки мелочей, будет либо серьезной болью на С++, либо непригодной для использования. И даже те вещи, которые достаточно легки, часто требуют так много шаблонов и тяжелых обозначений, что они не очень привлекательны. (Некоторые поклонники С++ любят заявлять об обратном, но, откровенно говоря, большинство из них, похоже, имеют довольно ограниченный опыт работы с фактическим функциональным программированием.)
Позвольте мне начать с того, что большинство из них не являются "внутренними", или, скажем так, "обязательными"; многие из них отсутствуют в известных функциональных языках, и, теоретически, многие из этих функций могут быть использованы для реализации других (таких как функции более высокого порядка в нетипизированном лямбда-исчислении).
Однако пропустите эти:
Затворы
Замки не нужны и являются синтаксическим сахаром: в процессе Lambda Lifting вы можете преобразовать любое закрытие в объект функции (или даже просто свободная функция).
Именованные функторы (С++ 03)
Просто чтобы показать, что это не проблема для начала, вот простой способ сделать это без lambdas в С++ 03:
Не проблема:
struct named_functor
{
void operator()( int val ) { std::cout << val; }
};
vector<int> v;
for_each( v.begin(), v.end(), named_functor());
Анонимные функции (С++ 11)
Однако анонимные функции в С++ 11 (также называемые лямбда-функциями, поскольку они происходят из истории LISP), которые реализованы как объекты с псевдонимом имени, могут обеспечивать одинаковое удобство (и на самом деле называемый закрытием, так что да, С++ 11 имеет закрытие):
Нет проблем:
vector<int> v;
for_each( v.begin(), v.end(), [] (int val)
{
std::cout << val;
} );
Полиморфные анонимные функции (С++ 14)
Еще меньше проблем, нам больше не нужно заботиться о типах параметров в С++ 14:
Еще меньше проблем:
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);
Я должен отметить, что эта полностью поддерживает семантику закрытия, такую как захват переменных из области видимости как по ссылке, так и по значению, а также возможность захватить ВСЕ переменные, а не только указанные. Лямбда неявно определяется как функциональные объекты, обеспечивая необходимый контекст для их работы; обычно это делается посредством подъема лямбда.
Функции более высокого порядка Нет проблем:
std::function foo_returns_fun( void );
Разве это недостаточно для вас? Здесь lambda factory:
std::function foo_lambda( int foo ) { [=] () { std::cout << foo; } };
Вы не можете создавать функции, но вы можете использовать объекты, которые могут передаваться как функции std::, такие же, как и обычные функции. Таким образом, вся функциональность есть, это просто для вас, чтобы собрать ее вместе. Я мог бы добавить, что большая часть 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 можно легко реализовать и очень функционально, исходя из нетипизированного лямбда-исчисления:
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));
}
Они очень хрупкие; по сути, они должны быть типа, который возвращает его собственный тип и принимает один аргумент своего типа; такие ограничения затем позволят всем функциональным рассуждениям системы SKI безопасно применяться к их составу. С небольшой работой и некоторым метапрограммированием шаблонов многое можно было бы сделать во время компиляции через магию шаблонов выражений, чтобы сформировать высоко оптимизированный код.
Шаблоны экспрессии, как и в стороне, являются методом, в котором выражение, обычно в виде последовательности операций или последовательного порядка кода, основано как аргумент шаблону. Таким образом, шаблоны выражений являются компиляционными комбинаторами времени; они высокоэффективны, безопасны по типу и позволяют эффективно внедрять языки, специфичные для домена, непосредственно на С++. Хотя это темы высокого уровня, они хорошо используются в стандартной библиотеке и в boost:: spirit, как показано ниже.
Комбинировщики Духовного Парсера
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;
}
Это определяет список чисел с разделителями-запятыми. double_ и char_ являются отдельными парсерами, которые идентифицируют один двойной или один char, соответственно. Используя оператор → , каждый переходит к следующему, образуя один большой объединенный парсер. Они проходят через шаблоны, "выражение" их совокупного действия. Это точно аналогично традиционным комбинаторам и полностью проверяется временем компиляции.
Valarray
valarray, часть стандарта С++ 11, разрешено использовать шаблоны выражений (но не обязательно, для некоторых нечетных причины), чтобы облегчить эффективность преобразований. Теоретически любое количество операций могло бы быть натянуто вместе, что создавало бы довольно большое беспорядочное выражение, которое затем может быть агрессивно привязано к скорости. Это еще одна форма комбинатора.
Я предлагаю этот ресурс, если вы хотите больше узнать о шаблонах выражений; они абсолютно фантастичны в получении всех проверок времени компиляции, которые вы хотели бы сделать, а также улучшении повторного использования кода. Однако их сложно запрограммировать, поэтому я бы посоветовал вам найти библиотеку, содержащую идиомы, которые вы хотите, вместо того, чтобы кататься самостоятельно.
Подписи функций как типы Нет проблем
void my_int_func(int x)
{
printf( "%d\n", x );
}
void (*foo)(int) = &my_int_func;
или, в С++, мы будем использовать std:: function:
std::function<void(int)> func_ptr = &my_int_func;
Вывод типа Нет проблем
Простые переменные, набранные путем вывода:
// var is int, inferred via constant
auto var = 10;
// y is int, inferred via var
decltype(var) y = var;
Вывод общего типа в шаблонах:
template < typename T, typename S >
auto multiply (const T, const S) -> decltype( T * S )
{
return T * S;
}
Кроме того, это может быть использовано в lambdas, объектах функции, в основном любое выражение времени компиляции может использовать decltype для вывода типа времени компиляции.
Но это не то, что вы на самом деле после этого здесь, не так ли? Вы хотите, чтобы тип дедукции, а также тип ограничения, вы хотите тип реконструкции и типа деривации. Все это можно сделать с помощью понятий, но они еще не являются частью языка.
Итак, почему бы нам просто не реализовать их? boost:: concept, boost:: typeerasure и свойства типа (потомок от boost:: tti и boost:: typetraits) могут делать все это.
Хотите ограничить функцию на основе какого-то типа? std:: enable_if на помощь!
А, но это ad hoc правильно? Это означало бы для любого нового типа, который вы хотели бы построить, вам нужно было бы сделать шаблонный и т.д. И т.д. Ну, нет, но здесь лучший способ!
template<typename RanIter>
BOOST_CONCEPT_REQUIRES(
((Mutable_RandomAccessIterator<RanIter>))
((LessThanComparable<typename Mutable_RandomAccessIterator<RanIter>::value_type>)),
(void)) // return type
stable_sort(RanIter,RanIter);
Теперь ваш stable_sort может работать только с типами, которые соответствуют вашим строгим требованиям. boost:: concept имеет тонны готовых, вам просто нужно поместить их в нужное место.
Если вы хотите вызывать различные функции или делать разные вещи вне типов или запрещать типы, используйте черты типов, теперь они стандартные. Нужно выбирать на основе частей типа, а не полного типа? Или разрешить много разных типов, имеющих общий интерфейс, только одного типа с тем же интерфейсом? Ну, тогда вам нужно стирать стили, как показано ниже:
Тип Полиморфизм Нет проблем
Шаблоны для полиморфизма типа времени компиляции:
std::vector<int> intvector;
std::vector<float> floatvector;
...
Тип стирания, для времени выполнения и полиморфизма типа на основе адаптера:
boost::any can_contain_any_type;
std::function can_call_any_function;
any_iterator can_iterator_any_container;
...
Стирание стилей возможно на любом языке OO и включает в себя настройку небольших объектов функций, которые выводятся из общего интерфейса, и перевод на него внутренних объектов. Благодаря небольшой настройке MPL, это быстро, легко и эффективно. Ожидайте, что скоро это станет популярным.
Неизмеримые Datastructures Не синтаксис для явных конструкций, но возможно:
Может быть сделано с помощью не использования метапрограмм или метапрограмм. Поскольку это много кода (полный ADT может быть довольно большим), я свяжусь с вами здесь, чтобы показать, как сделать неизменным отдельно связанный список.
Для этого во время компиляции потребуется большое количество магии шаблонов, но с помощью constexpr можно сделать более легко. Это упражнение для читателя; Я не знаю никаких компиляционных библиотек времени для этого с моей головы.
Однако создание неизменной структуры данных из STL довольно просто:
const vector<int> myvector;
Вот ты; структуру данных, которая не может быть изменена! По всей серьезности реализации палец-дерева существуюти, вероятно, ваш лучший выбор для функциональности ассоциативных массивов. Это просто не сделано для вас по умолчанию.
Алгебраические типы данных Нет проблем:
Удивительный boost:: mpl позволяет сдерживать использование типов, которые наряду с boost:: fusion и boost:: functional сделать что-нибудь во время компиляции, которое вы хотели бы получить в отношении ADT, Фактически, большинство из них сделано для вас:
#include <boost/mpl/void.hpp>
//A := 1
typedef boost::mpl::void_ A;
Как было сказано ранее, большая часть работы не выполняется для вас в одном месте; например, вам нужно будет использовать boost:: optional, чтобы получить дополнительные типы, и mpl, чтобы получить тип устройства, как показано выше. Но используя относительно простые компиляционные шаблоны, вы можете создавать рекурсивные типы ADT, что означает, что вы можете реализовать обобщенные ADT. По мере того, как система шаблонов завершается, у вас есть полный контроль над телом и генератор ADT в вашем распоряжении.
Он просто ждет, пока вы соберете кусочки.
На основе ADT
boost:: variant предоставляет ассоциации с проверкой типа, в дополнение к исходным объединениям на языке. Их можно использовать без суеты, зайдите в:
boost::variant< int, std::string > v;
Этот вариант, который может быть int или string, может быть назначен любым способом с проверкой, и вы можете даже посещать на основе времени выполнения:
class times_two_visitor
: public boost::static_visitor<>
{
public:
void operator()(int & i) const
{
i *= 2;
}
void operator()(std::string & str) const
{
str += str;
}
};
Анонимные /Ad -hoc структуры данных Нет проблем:
Конечно, у нас есть кортежи! Вы можете использовать структуры, если хотите, или:
std::tuple<int,char> foo (10,'x');
Вы также можете выполнять множество операций с кортежами:
// 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;
Рекурсия хвоста Нет явной поддержки, итерации достаточно
Это не поддерживается или не поддерживается в Common LISP, хотя оно находится в Scheme, и поэтому я не знаю, можете ли вы сказать, что это необходимо. Однако вы можете легко выполнить хвостовую рекурсию в С++:
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
}
О, и GCC скомпилирует это в итеративный цикл, никакого вреда не будет. Хотя это поведение не является обязательным, оно допустимо и выполняется, по крайней мере, в одном случае, о котором я знаю (возможно, и о Кланге). Но нам не нужна рекурсия хвоста: С++ полностью с мутациями:
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;
}
Рекурсия хвоста оптимизирована на итерацию, поэтому у вас есть ровно столько же силы. Кроме того, с помощью boost:: coroutine можно легко обеспечить использование для определенных пользователем стеков и разрешить неограниченную рекурсию, что делает ненужную рекурсию хвоста. Язык не активно враждебен рекурсии или хвостовой рекурсии; это просто требует, чтобы вы обеспечивали безопасность самостоятельно.
Соответствие шаблону Нет проблем:
Это можно легко сделать с помощью boost:: variant, как подробно описано в этом разделе, через шаблон посетителя:
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;
};
Этот пример, из этого очень очаровательного веб-сайта показывает, как получить все возможности шаблона Scala, просто используя boost:: variant, Существует больше шаблонов, но с красивым шаблоном и библиотекой макросов большая часть этого будет уходить.
На самом деле, вот библиотека, которая сделала все это для вас:
#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));
}
Как предоставлено fooobar.com/questions/409688/... Как вы можете видеть, это не просто возможно, но и красиво.
Коллекция мусора Будущий стандарт, распределители, RAII и shared_ptr достаточны
В то время как С++ не имеет GC, есть предложение для одного, которое было проголосовано в С++ 11, но может быть включено в С++ 1y. Существует множество различных пользовательских определений, которые вы можете использовать, но С++ не нуждается в сборке мусора.
С++ имеет идиому как RAII для работы с ресурсами и памятью; по этой причине С++ не нуждается в GC, поскольку он не производит мусор; все очищается быстро и в правильном порядке по умолчанию. Это вводит проблему того, кому принадлежит что-то, но это в значительной степени разрешено в С++ 11 через общие указатели, слабые указатели и уникальные указатели:
// 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 destruction
std::weak_ptr<int> weak_int (shared_int);
// Only I can ever own this int
std::unique_ptr<int> unique_int (new int);
Это позволяет вам предоставлять гораздо более детерминированную и управляемую пользователем форму сбора мусора, которая не вызывает каких-либо остановок поведения в мире.
Это вам нелегко? Используйте специальный распределитель, например boost:: poolили сворачивать свои собственные; он относительно прост в использовании пула или арендодателя на основе арены, чтобы получить лучшее из обоих миров: вы можете легко распределить так свободно, как вам нравится, а затем просто удалите пул или арену, когда вы закончите. Не суетиться, не мусс и не останавливать мир.
Однако в современном дизайне С++ 11 вы почти никогда не будете использовать новые в любом случае, кроме как при распределении в * _ptr, поэтому пожелание GC не обязательно в любом случае.
В резюме
С++ имеет множество функциональных функций языка, и все перечисленные вами могут быть выполнены с той же мощью и способностью выражения Haskell или Lisp. Однако большинство из этих функций не встроены по умолчанию; это меняется с введением лямбда (которые заполняют функциональные части STL) и с поглощением повышения на стандартный язык.
Не все эти идиомы являются самыми привлекательными, но ни один из них не является особенно обременительным для меня или неприемлем для нескольких макросов, чтобы облегчить их проглатывание. Но любой, кто говорит, что они не возможны, не проводил своих исследований и, как мне кажется, имел ограниченный опыт работы с реальным программированием на C++.
(Просто добавьте немного ответа Алисы, что отлично.)
Я далек от эксперта по функциональному программированию, но язык метапрограммирования шаблона времени компиляции в С++ часто рассматривается как "функциональный", хотя и с очень тайным синтаксисом. На этом языке "функции" становятся (часто рекурсивными) экземплярами шаблонов классов. Частичная специализация служит для сопоставления шаблонов, прекращения рекурсии и т.д. Таким образом, факториал компиляции может выглядеть примерно так:
template <int I>
struct fact
{
static const int value = I * fact<I-1>::value;
};
template <>
struct fact<1>
{
static const int value = 1;
};
Конечно, это довольно отвратительно, но многие люди (особенно разработчики Boost) сделали невероятно умные и сложные вещи только с помощью этих инструментов.
Возможно, стоит упомянуть также ключевое слово С++ 11 constexpr, которое обозначает функции, которые могут быть оценены во время компиляции. В С++ 11 функции constexpr ограничены (в основном) только голым выражением return; но тернарный оператор и рекурсия допускаются, поэтому вышеупомянутый факториал времени компиляции может быть пересчитан гораздо более лаконично (и понятно) как:
constexpr int fact(int i)
{
return i == 1 ? 1 : i * fact(i-1);
}
с дополнительным преимуществом, которое fact() теперь можно вызывать во время выполнения. Является ли это составлением программирования в функциональном стиле, остается для читателя решить: -)
(С++ 14, вероятно, удалит многие ограничения из функций constexpr, позволяя вызывать очень большое подмножество С++ во время компиляции)