Привет.
Сидел я как-то вечером, ждал, пока соберется свежая ревизия clang, и смотрел на код одного своего проекта, в котором встречались не очень красивые вещи вроде
std::transform (someContainer.begin (), someContainer.end (), std::back_inserter (otherContainer),
[this] (const SomeUglyAndLongType& item) { return HandleItem (item); });
Зачем создавать целую лямбду, чтобы у функции двух аргументов (если, как пишут классики, this считать неявным нулевым аргументом) зафиксировать один из них? На каком-нибудь псевдохаскеле можно было бы просто написать что-то вроде
map (handleItem this) someContainer
Мапы, функторы и прочие монады сделаем как-нибудь в следующий раз, а вот вещи, напоминающие (handleItem this) можно попробовать научиться писать.
Итак, что хочется сделать? Хочется научиться каррировать произвольные функции, то есть, вызывать их по «кусочкам» — передали первый аргумент, получили какую-то новую функцию одного аргумента, передали второй, получили новую функцию, и так далее, пока все аргументы для нашей исходной функции не будут переданы. Когда аргументы кончились, переходим на личности и вызываем нашу исходную функцию со всеми указанными аргументами.
Или, если вдруг кому так понятнее будет, нужно из функции N аргументов T1 × T2 ×… × TN → R сделать последовательность функций T1 → (T2 → (… → (TN → R))). Хотя, кому так понятнее, тот и наверняка и без меня знает, что такое каррирование.
Сразу предупреждаю, что решение получится не production-quality по ряду причин, которые мы обсудим чуть позже.
Что нам для этого понадобится? Понадобится свежий компилятор с поддержкой C++14, например, clang 3.4 и новее. Нужна и стандартная библиотека из C++14, на некоторых линуксах с этим могут быть проблемы, так что с кодом можно играться и на онлайн-сервисах вроде этого.
Как должен выглядеть результат наших попыток сделать из C++ хаскель на, собственно, плюсах? Ну, например, как-нибудь так:
auto test (int t1, int t2, double t3, const std::string& str)
{
return t1 * t2 * t3 * str.size ();
}
// ...
std::cout << curry (test) (1) (2) (3.0) ("four") << std::endl;
Естественно, свободными функциями curry ограничиваться не должно.
Что нам нужно сделать? Да всего-ничего, написать функцию curry. Ну так давайте и напишем!
Пусть curry (f) возвращает какой-нибудь объект (назовём его CurryImpl), которому, очевидно, нужна будет функция f, которую мы передали в curry, а ещё у него должен быть перегружен operator(), и по условию задачи он должен принимать один аргумент непонятно какого типа, и непонятно что возвращать. Естественно, CurryImpl шаблонный, чтобы уметь запоминать любые функции:
template<typename F>
class CurryImpl
{
const F m_f; // наша функция, переданная в curry
public:
CurryImpl (F f)
: m_f { f }
{
}
template<typename T>
auto operator() (const T& arg) const
{
// осталось тут что-то написать
}
};
template<typename F>
auto curry (F f)
{
return CurryImpl<F> { f };
}
Давайте теперь посмотрим на оператор-круглые-скобки. Итак, этот оператор принимает один аргумент arg и либо вызывает искомую функцию m_f, если это последний аргумент в цепочке вызовов, либо возвращает другой объект, который запомнил этот arg.
Сначала разберёмся с тем, как запоминать аргументы.
Ну, тут на самом деле все довольно тривиально: нужно их просто брать и хранить в CurryImpl. Про эти аргументы мы ничего не знаем, равно как и про их типы, поэтому придётся добавить ещё один аргумент шаблона, да ещё и с вариадик. Непосредственно хранить значения аргументов можно, например, в std::tuple. Сообщать нашему CurryImpl про эти аргументы можно непосредственно в конструкторе. Итого, объявление класса модифицируется как-то так:
template<typename F, typename... PrevArgs>
class CurryImpl
{
const F m_f;
const std::tuple<PrevArgs...> m_prevArgs;
public:
CurryImpl (F f, const std::tuple<PrevArgs...>& prev)
: m_f { f }
, m_prevArgs { prev }
{
}
// а дальше все как раньше
};
Так, хорошо, с хранением разобрались, теперь осталось вызывать функцию. Тут всё становится немного интереснее: а как, собственно, определить, когда стоит прекратить накапливать аргументы и, собственно, вызвать m_f? А просто взять и вызвать, если получится — всё отлично!
А поможет нам в этом одно замечательное правило C++ — SFINAE, или Substitution Failure Is Not An Error. Если вкратце, [в данном контексте] суть в том, что, если компилятор при выборе кандидатов на вызов функции среди ряда перегруженных функций видит некое некорректное выражение в объявлении функции, то он её отбрасывает и смотрит дальше вместо error в консоли и слишком рано завершённой компиляции. Собственно, все эти std::enable_if и компания основаны именно на SFINAE.
Итак, SFINAE. Напишем функцию, которая будет вызывать нашу исходную m_f только тогда, когда такой вызов будет well-formed. В этом нам поможет замечательная шаблонная функция std::result_of. std::result_of<F (T1, T2, ...)> определяет вложенный тип type, равный типу, возвращаемому объектом F, если он вызван с аргументами типа T1, T2,… Подробнее она описана, например, здесь. Собственно, ключевые слова по ссылке, для C++14:
Only defined if F can be called with the arguments ArgTypes… in unevaluated context.
Для C++11 формулировка слегка другая, но это несущественно.
Кстати, в C++14 можно пользоваться удобным синонимом std::result_of_t<...> вместо typename std::result_of<...>::type.
Итак, пишем нашу функцию:
template<typename T>
std::result_of_t<F (PrevArgs..., T)> invoke (const T& arg) const // PrevArgs — аргумент CurryImpl, как мы помним
{
// тут как-то вызываем нашу m_f и возвращаем её результат
}
Как это работает? Если m_f, которая типа F, можно вызвать со всеми предыдущими аргументами и текущим, то всё хорошо, функция «существует», если нельзя — компилятор её и не рассматривает.
Если же вызвать функцию нельзя, то должна быть другая invoke, которая тоже принимает один аргумент, запоминает его и рекурсивно возвращает новый объект с оператором-круглые-скобки и всем прочим. Как-то так, например:
template<typename T>
auto invoke (const T& arg) const
{
return CurryImpl<F, PrevArgs..., T> { m_f, std::tuple_cat (m_prevArgs, std::tuple<T> { arg }) };
}
Что мы тут сделали? Вернули новый CurryImpl, который сохраняет все предыдущие аргументы плюс один новый. На уровне типов это отражается в записи PrevArgs..., T, если хотите, добавляющей T в variadic-список типов, а на уровне значений — просто соединяем два кортежа, старый m_prevArgs и новый одноэлементный кортеж.
Посмотрим снова на наш оператор-круглые-скобки. Теперь понятно, что мы должны в нём вызвать одну из наших двух перегрузок invoke, по возможности первую, которая вызывает функцию, а то так можно никогда не перестать копить аргументы. Как это сделать? Тут есть куча вариантов, мой любимый в таких случаях — использовать тот факт, что любая перегрузка лучше, чем перегрузка с эллипсисом (aka многоточие, aka вариадики C-стайл). То есть, добавляем ещё один параметр, который даже не будем использовать, например, int в первую функцию и ... во вторую, и получаем что-то подобное:
template<typename T>
auto operator() (const T& arg) const
{
return invoke (arg, 0);
}
private:
template<typename T>
std::result_of_t<F (PrevArgs..., T)> invoke (const T& arg, int) const
{
// тут как-то вызываем нашу m_f и возвращаем её результат
}
template<typename T>
auto invoke (const T& arg, ...) const
{
return CurryImpl<F, PrevArgs..., T> { m_f, std::tuple_cat (m_prevArgs, std::tuple<T> { arg }) };
}
То есть, если первая перегрузка доступна, всегда будет выбираться она: int компилятору нравится куда больше, чем ...
Осталось разобраться с вызовом функции из первой перегрузки, и всё будет хорошо.
Что нужно, чтобы вызвать функцию, аргументы которой (с точностью до arg) хранятся в кортеже? Надо как-нибудь распаковать тот кортеж и передать результаты распаковки в функцию как обычные аргументы. Проблема в том, что в точке вызова мы не знаем на этапе написания кода, сколько у нас аргументов, поэтому просто взять и руками подёргать std::get мы не можем. Ну и славно, негоже в 2014 году работу за компилятор делать. Вот был бы у нас какой-нибудь способ сделать вариадик из чисел от 0 до N-1, мы могли бы написать что-то такое:
// в Is лежат числа от 0 до (количество элементов в m_prevArgs)-1
template<typename T, std::size_t... Is>
auto invokeIndexed (const T& arg /*, тут ещё что-то, чтобы Is вывелся компилятором сам*/) const
{
return m_f (std::get<Is> (m_prevArgs)..., arg);
}
Здесь по правилам разворачивания variadic-параметров выражение std::get<Is> (m_prevArgs)... развернётся компилятором в std::get<I1> (m_prevArgs), std::get<I2> (m_prevArgs), и так далее для всех индексов Is.
А, стоп, так в точности такой вариант можно сделать на тех же вариадиках в C++11, а в C++14 его даже добавили в STL! Замечательно, всё встаёт на свои места. Идём по ссылке, видим замечательный метод std::index_sequence_for, который нам как раз нужен (у нас ведь на руках есть PrevArgs...), и пишем в теле нашей первой invoke вызов invokeIndexed:
return invokeIndexed (arg, std::index_sequence_for<PrevArgs...> {});
А invokeIndexed тогда вторым параметром должна принимать std::index_sequence, которая как раз и отвечает за хранение списка чисел:
template<typename T, std::size_t... Is>
auto invokeIndexed (const T& arg, std::index_sequence<Is...>) const
{
return m_f (std::get<Is> (m_prevArgs)..., arg);
}
Отлично! Всё работает! На радостях пишем то, с чего начинался пост, вроде такого:
struct Foo
{
auto doFoo (int baz, int qux)
{
return (m_bar + baz) / qux;
}
};
// ...
Foo someFoo;
const auto fooRes = Curry (&Foo::doFoo) (&someFoo) (2) (4);
И сразу же компилятор возвращает нас в жестокую реальность: выражение m_f (arguments) не является well-formed, если m_f — указатель на функцию-член класса.
Впрочем, как учили нас классики, любая проблема решается добавлением ещё одного уровня абстракции, поэтому добавим ещё один уровень, который будет ответственен непосредственно за вызов функции с аргументами. Уровень будет представляться в виде шаблонной структуры, параметризуемой типом нашей m_f, и будет иметь шаблонный оператор-круглые-скобки. Опишем сначала общий случай, когда мы просто берём и вызываем нашу функцию:
template<typename IF>
struct Invoke
{
template<typename... IArgs>
auto operator() (IF fr, IArgs... args)
{
return fr (args...);
}
};
Перепишем invokeIndexed:
template<typename T, std::size_t... Is>
auto invokeIndexed (const T& arg, std::index_sequence<Is...>) const
{
return Invoke<F> {} (m_f, std::get<Is> (m_prevArgs)..., arg);
}
К счастью, для частных случаев указателей на функции-члены никаких SFINAE не нужно, можно просто специализировать наш Invoke, да и выбирать из списка аргументов Args... первый — по соглашению он и будет нашим объектом, на котором нужно вызвать функцию. При этом ещё не забудем, что первый аргумент может быть как указателем на класс, так и ссылкой, и хочется поддерживать оба варианта вызова:
template<typename R, typename C, typename... Args>
struct Invoke<R (C::*) (Args...)>
{
auto operator() (R (C::*ptr) (Args...), C c, Args... rest)
{
return (c.*ptr) (rest...);
}
auto operator() (R (C::*ptr) (Args...), C *c, Args... rest)
{
return (c->*ptr) (rest...);
}
};
Кстати, между ними есть принципиальная разница, очевидная, конечно, но проговорить стоит: в первом случае изменения затронут локальную копию c, а во втором они будут видны и извне, на объекте, который в один из операторов-круглые-скобочки мы передали. То есть:
struct Foo
{
int m_state = 42;
auto doFoo (int bar)
{
m_state += bar;
return m_state;
}
};
Foo foo;
curry (&Foo::doFoo) (foo) (1); // foo.m_state всё ещё 42
curry (&Foo::doFoo) (&foo) (1); // foo.m_state теперь 43
Вот, в общем-то, и всё.
#include <tuple>
#include <type_traits>
#include <utility>
#include <iostream>
#include <string>
template<typename F, typename... PrevArgs>
class CurryImpl
{
const F m_f;
const std::tuple<PrevArgs...> m_prevArgs;
public:
CurryImpl (F f, const std::tuple<PrevArgs...>& prev)
: m_f { f }
, m_prevArgs { prev }
{
}
template<typename T>
auto operator() (const T& arg) const
{
return invoke (arg, 0);
}
private:
template<typename T>
std::result_of_t<F (PrevArgs..., T)> invoke (const T& arg, int) const
{
return invokeIndexed (arg, std::index_sequence_for<PrevArgs...> {});
}
template<typename IF>
struct Invoke
{
template<typename... IArgs>
auto operator() (IF fr, IArgs... args)
{
return fr (args...);
}
};
template<typename R, typename C, typename... Args>
struct Invoke<R (C::*) (Args...)>
{
auto operator() (R (C::*ptr) (Args...), C c, Args... rest)
{
return (c.*ptr) (rest...);
}
auto operator() (R (C::*ptr) (Args...), C *c, Args... rest)
{
return (c->*ptr) (rest...);
}
};
template<typename T, std::size_t... Is>
auto invokeIndexed (const T& arg, std::index_sequence<Is...>) const
{
return Invoke<F> {} (m_f, std::get<Is> (m_prevArgs)..., arg);
}
template<typename T>
auto invoke (const T& arg, ...) const
{
return CurryImpl<F, PrevArgs..., T> { m_f, std::tuple_cat (m_prevArgs, std::tuple<T> { arg }) };
}
};
template<typename F>
auto curry (F f)
{
return CurryImpl<F> { f, {} };
}
auto test (int t1, int t2, double t3, const std::string& str)
{
return t1 * t2 * t3 * str.size ();
}
struct Foo
{
int m_bar;
auto doFoo (int baz, int qux)
{
auto result = (m_bar + baz) / qux;
++m_bar;
return result;
}
};
int main ()
{
const auto res = curry (test) (1) (2) (3.0) ("four");
std::cout << res << std::endl;
Foo someFoo { 42 };
const auto fooRes = curry (&Foo::doFoo) (&someFoo) (2) (4);
std::cout << fooRes << " " << someFoo.m_bar << std::endl;
someFoo.m_bar = 42;
auto lambda = [someFoo] (int bar, int baz) mutable { return someFoo.doFoo (bar, baz); };
const auto lambdaRes = curry (lambda) (4) (2);
std::cout << lambdaRes << std::endl;
}
Ещё всё вместе есть онлайн.
Теперь ответы на некоторые предполагаемые вопросы:
Зачем параметризовать CurryImpl типом функции, почему бы просто не использовать std::function?
- В
std::functionвнутри сидит type erasure, который далеко не всегда девиртуализируется и инлайнится компилятором. Впрочем, это тема для отдельной статьи - Скучно.
А std::tuple тебе не скучно?
Нет, тем более, что собственная реализация была бы точно такая же, от тупла тут никакого оверхеда.
Зачем тут C++14, разве C++11 не хватит?
Неа, не хватит. C++14 тут полезен, в частности:
- чтобы писать
autoвместо возвращаемых значений функций, а не выписывать адские рекурсивныеdecltypeили ещё что похуже; - чтобы не переизобретать compile-time-последовательность чисел (
std::index_sequence_for, это вот всё).
Хотя, конечно, без всего этого вполне можно жить, самое главное — вариадики и вывод типов хотя бы в виде decltype.
Получается, что с функциями с аргументами по умолчанию передать можно будет только лишь аргументы без значений по умолчанию?
Верно.
Зачем везде копировать параметры?
Это представляется разумным: получающийся после частичного применения функции функтор может захотеться куда-нибудь передать как коллбек, вернуть из функции, и так далее. Копировать безопаснее, и вообще, вполне себе в функциональном стиле.
Почему оно не production-ready?
Потому что коллеги вас растерзают за такой код, а сисадмин и менеджер не захотят переходить на C++14 там наверняка где-то внутри бегает пара проблем, связанных с обработкой ссылок.
Автор: 0xd34df00d
