Карринг vs Частичное применение функции

Перевод статьи Джона Скита, известного гуру языка C#, автора книги C# In Depth, сотрудника Google, человека #1 ^[1] по репутации на stackoverflow.com и наконец героя Jon Skeet Facts ^[2]. В этой статье Джон доступно объясняет, что представляют из себя карринг и частичное применение функции, концепции, пришедшие из мира функционального программирования. Кроме того, он подробно поясняет в чём их различие. Признаюсь, что я и сам их путал до прочтения этой статьи, поэтому мне показалось полезным сделать перевод.

Это немного странный пост, и прежде чем читать его вам, пожалуй, следует отнести себя к одной из этих групп:

• Те, кто не интересуются функциональным программированием и находят функции высшего порядка запутанными: вы можете пропустить эту статью полностью.
• Те, кто знают всё о функциональном программировании и хорошо понимают разницу между каррингом (currying) и частичным применением функции (partial function application): пожалуйста, внимательно прочтите этот пост и отпишитесь в комментариях, если найдете неточности.
• Те, кто частично знаком с функциональным программированием, и заинтересован узнать больше: отнеситесь к этому посту скептически и внимательно прочтите комментарии. Прочитайте другие статьи более опытных разработчиков для получения дополнительной информации.

В общем-то, я знаю, что некоторые люди иногда путают термины карринг и частичное применение функции — используют их взаимозаменяемо, когда этого делать не следует. Это одна из тех тем (как, например, монады), которую я до некоторой степени понимаю, и я решил, что лучшим способом удостовериться в своих знаниях будет написать об этом. Если это сделает эту тему более доступной для других разработчиков, тем лучше.

Этот пост не содержит Haskell

Почти во всех разъяснениях на эту тему, что я видел, были даны примеры на «правильных» функциональных языках, обычно на Haskell. Я ничего не имею против Haskell, просто мне обычно легче понять примеры на языке, который я хорошо знаю. Тем более, мне гораздо легче писать примеры на таком языке, поэтому все примеры в этом посте будут на C#. Собственно, все примеры доступны в одном файле ^[3], правда, несколько переменных в нем переименованы. Просто скомпилируйте и запустите.

C# на самом деле не является функциональным языком — я знаю достаточно, чтобы понимать, что делегаты не являются полной заменой для функций высшего порядка. Тем не менее, они достаточно хороши для демонстрации описываемых принципов.

Хотя можно продемонстрировать карринг и частичное применение, используя функцию (метод) с небольшим количеством аргументов, я решил использовать три аргумента для ясности. Хотя мои методы выполнения карринга и частичного применения будут обобщенными (поэтому все типы параметров и возвращаемого значения произвольны), в целях демонстрации я использую простую функцию:

static string SampleFunction(int a, int b, int c) 
{ 
    return string.Format("a={0}; b={1}; c={2}", a, b, c); 
}

Пока всё просто. В этом методе нет ничего хитрого, не ищите в нем ничего удивительного.

О чем вообще речь?

И карринг и частичное применение это способы преобразования одного вида функции в другой. Мы будем использовать делегаты в качестве аппроксимации функций, поэтому для работы с методом SampleFunction как со значением, мы можем написать:

Func<int, int, int, string> function = SampleFunction;

Эта строчка полезна по двум причинам:

• Присвоение значения переменной внушает идею, что это действительно значение. Экземпляр делегата является объектом, так же, как и экземпляр любого другого типа, а значение функциональной переменной — это просто ссылка.
• Преобразование группы методов (использование имени метода как способа создать делегат) плохо работает с выводом типов, когда вызывается обобщенный метод.

Теперь мы можем вызывать делегат с тремя аргументами:

string result = function(1, 2, 3);

Или то же самое:

string result = function.Invoke(1, 2, 3);

(Компилятор C# преобразует первую короткую форму во вторую. Сгенерированный IL будет тем же самым.)

Хорошо, если нам доступны все три аргумента единовременно, но что если нет? Для конкретного (хотя и несколько надуманного) примера, предположим у нас есть функция логирования с тремя параметрами (источник, серьезность, сообщение) и в пределах одного класса (который я буду называть BusinessLogic), мы хотим всегда использовать одно и то же значение для параметра «источник». Мы хотим иметь возможность легко логировать из любой точки класса, указывая только серьезность и сообщение. У нас есть несколько вариантов:

• Создать класс-адаптер, который принимает функцию логирования (или даже объект-логгер) и значение параметра «источник» в свой конструктор, сохраняет их в своих полях и выставляет наружу метод с двумя параметрами. Этот метод просто делегирует вызов сохраненному логгеру, передавая сохраненный «источник» первым параметром функции логгера. В классе BusinessLogic мы создаем экземпляр адаптера и сохраняем ссылку на него в поле, а далее просто вызываем метод с двумя параметрами где хотим. Пожалуй, это оверкилл, если нам нужен только адаптер от BusinessLogic, но его можно переиспользовать… до тех пор, пока мы будем адаптировать ту же логирующую функцию.
• Хранить исходный объект логгера в нашем классе BusinessLogic, но создать вспомогательный метод с двумя параметрами, внутри которого будет захардкожено значение для параметра «источник». Если нам надо сделать так в нескольких местах, это начинает раздражать.
• Использовать более функциональный подход — в данном случае частичное применение функции.

Я умышленно игнорирую различие между хранением ссылки на объект-логгер и хранением ссылки на функцию логирования. Очевидно, есть существенное различие, если нам нужно использовать более одной функции класса логгера, но для того, чтобы размышлять о карринге и частичном применении, мы будем думать о «логгере» как о «функции, принимающей три параметра» (как наша функция в примере).

Теперь, когда я дал псевдо-реальный конкретный кейс для мотивации, мы забудем его до конца статьи и будем рассматривать только функцию-пример. Я не хочу писать весь класс BusinessLogic, который будет делать вид, что занимается чем-то полезным; я уверен вы сможете сделать мысленное преобразование из «функции-примера» в «что-то, что вы на самом деле хотели бы сделать».

Частичное применение функции

Частичное применение берет функцию с N параметрами и значение для одного из этих параметров и возвращает функцию с N-1 параметрами, такую, что, будучи вызванной, она соберет все необходимые значения (первый аргумент, переданный самой функции частичного применения, и остальные N-1 аргументы переданы возвращаемой функции). Таким образом, эти два вызова должны быть эквивалентны нашему методу с тремя параметрами:

// обычный вызов
string result1 = function(1, 2, 3);

// вызов через частичное применение
Func<int, int, string> partialFunction = ApplyPartial(function, 1); 
string result2 = partialFunction(2, 3);

В данном случае, я реализовал частичное применение с единственным параметром, первым по счету — вы можете написать ApplyPartial, которая будет принимать большее число аргументов или будет подставлять их в другие позиции в окончательном выполнении функции. По видимому, сбор параметров по одному, начиная с начала — самый обычный подход.

Спасибо анонимным функциям (в данном случае лямбда-выражению, но анонимный метод не был бы сильно многословнее), реализация ApplyPartial проста:

static Func<T2, T3, TResult> ApplyPartial<T1, T2, T3, TResult>
    (Func<T1, T2, T3, TResult> function, T1 arg1) 
{ 
    return (b, c) => function(arg1, b, c); 
}

Обобщения заставляют этот метод выглядеть сложнее, чем он есть на самом деле. Обратите внимание, что отсутствие типов высшего порядка (higher order types) в C# означает, что вам необходима реализация этого метода для каждого делегата, который вы хотите использовать — если вам необходима версия для функции с четырьмя параметрами, вам необходим метод ApplyPartial<T1, T2, T3, T4, TResult> и т.д. Вам, вероятно, так же понадобиться набор методов для семейства делегатов Action.

Последнее, что необходимо отметить — имея все эти методы, мы можем выполнять частичное применение вновь, даже потенциально до результирующей функции без параметров, если захотим:

Func<int, int, string> partial1 = ApplyPartial(function, 1); 
Func<int, string> partial2 = ApplyPartial(partial1, 2); 
Func<string> partial3 = ApplyPartial(partial2, 3); 
string result = partial3();

Опять же, только последняя строчка вызовет исходную функцию.

Ок, это и есть частичное применение функции. Оно относительно простое. Карринг, на мой взгляд, немного сложнее для понимания.

Карринг

В то время как частичное применение преобразует функцию с N параметрами в функцию с N-1 параметрами, применяя один аргумент, карринг декомпозирует функцию на функции от одного аргумента. Мы не передаем никаких дополнительных аргументов в метод Curry, кроме преобразуемой функции:

• Curry(f) возвращает функцию f1, такую что...
• f1(a) возвращает функцию f2, такую что...
• f2(b) возвращает функцию f3, такую что...
• f3(с) вызывает f(a, b, c)

(Опять же, обратите внимание, что это относится только к нашей функции с тремя параметрами — надеюсь, очевидно, как это будет работать с другими сигнатурами.)

Для нашего «эквивалентного» примера, мы можем написать:

// обычный вызов
string result1 = function(1, 2, 3);

// вызов через карринг
Func<int, Func<int, Func<int, string>>> f1 = Curry(function); 
Func<int, Func<int, string>> f2 = f1(1); 
Func<int, string> f3 = f2(2); 
string result2 = f3(3);

// или соберем все вызовы вместе...
var curried = Curry(function); 
string result3 = curried(1)(2)(3); 

Различие между последними примерами показывает причину того, почему в функциональных языках зачастую есть хороший вывод типов и компактное представление типов функций: объявление f1 очень страшное.

Теперь, когда мы знаем, что должен делать метод Curry, его реализация удивительно проста. На самом деле, всё, что нам нужно сделать это транслировать пункты выше в лямбда выражения. Красота:

static Func<T1, Func<T2, Func<T3, TResult>>> Curry<T1, T2, T3, TResult> 
    (Func<T1, T2, T3, TResult> function) 
{ 
    return a => b => c => function(a, b, c); 
}

Не стесняйтесь добавлять скобки, если хотите сделать код более понятным для себя, лично я думаю, что они только добавят беспорядка. В любом случае, мы получили то, что хотели. (Стоит подумать о том, как утомительно было бы это написать без лямбда-выражений или анонимных методов. Не трудно, просто утомительно.)

Это и есть карринг. Я думаю. Возможно.

Заключение

Я не могу сказать, что я когда либо использовал карринг, тогда как некоторые части парсинга текста для Noda Time ^[4] фактически используют частичное применение. (Если кто-то действительно хочет чтобы я это проверил, я сделаю это.)

Я очень надеюсь, что я показал вам разницу между этими двумя связанными между собой, но, тем не менее весьма различными понятиями. Теперь, когда мы подошли к концу, подумайте о том, как различие между ними проявится для функции с двумя параметрами, и, надеюсь, вы поймете, почему я решил использовать три :)

Мое шестое чувство говорит мне, что карринг является полезной концепцией в академическом контексте, в то время как частичное применение более полезно на практике. Однако это шестое чувство человека, который не использовал функциональные языки по полной. Если я когда-либо начну использовать F#, возможно я напишу дополняющий пост. Теперь, я надеюсь, что мои опытные читатели могут дать полезные мысли в комментариях.

Автор: xkrt