27 November 2009

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

.NET
Translation
Original author: Wes Dyer
Когда я впервые услышал термин Каррирование, я сразу же представил себе вкусные тайскую и индийскую кухни. К моему удивлению, я обнаружил, что разговор шел не о прекрасных специях, а о преобразовании функции, принимающей n аргументов в функцию, которая принимает один аргумент и возвращает каррированую функцию, которая принимает n — 1 аргументов. Где бы это могло быть полезным?

С теоретической точки зрения, это интересно, потому что в лямбда исчислении проще оперировать функциями, имеющими один аргумент. С практической стороны, это дает программисту возможность создать из базовой функции семейство функций фиксируя первые k аргументов. Это похоже на то, как мы крепим что-то к стене и нам для этого требуется две шпильки. Пока мы не воткнули ни одной шпильки, объект свободно может двигаться где угодно по поверхности; однако перемещение ограничивается как только мы пришпилили его одной шпилькой. И наконец, когда вторая шпилька воткнута в этот объект, свободы движения у объекта больше нет. Похожим образом, когда программист каррирует функцию из двух аргументов и применяет ее к первому аргументу, функциональность ограничена одним измерением. Наконец, когда он применяет новую функцию ко второму аргументу, вычисляется конечное значение.

В C# это означает, что если у меня есть делегат типа Func<A,B,R> (делегат с двумя аргументами типов A и B соответственно и возвращающий тип R), то я могу создать делегат, который имеет тип Func<A,Func<B,R>>. Обратите внимание что каррированый делегат принимает только один аргумент, но возвращает делегат, который принимает второй аргумент исходной функции и в конечном счете возвращает значение.

Рассмотрим создание таких функций на примере функции сложения.

Func<int,int,int> add = (x,y) => x + y;

Мы можем каррировать сложение применяя функцию Curry к add.
Func<int,Func<int,int>>curriedAdd = add.Curry();

На самом деле, эта каррированая функция add создает функции, которые прибавляют к n, где n — это аргумент каррированной функции add. Например, мы можем создать функцию инкремента применяя каррированную функцию add к значению 1.

Func<int,int> inc = curriedAdd(1);

Инкрементирующая функция при вызове теперь возвращает единицу плюс значение ее аргумента. Теперь мы можем использовать наши функции для разных форм сложения.

Console.WriteLine(add(3,4)); // 7<br>
Console.WriteLine(curriedAdd(3)(5)); // 8<br>
Console.WriteLine(inc(2)); // 3

Так как же выглядит эта функция Curry? На самом деле она весьма проста.

public static Func<A, Func<B, R>> Curry<A, B, R>(this Func<A, B, R> f)<br/>
{<br/>
return a => b => f(a, b);<br/>
}


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

Давайте рассмотрим что происходит когда мы создаем каждую из этих функций. Сначала мы создали функцию add, которая выглядит так:
(x, y) => x + y
После того как мы каррировали add, функция принимает вид:
x => y => x + y
Мы создали inc вызвав каррированый add со значением 1. Это создает, в сущности, такую функцию:
y => 1 + y

Идея каррирования функции и последующей фиксации первых n аргументов оригинальной функции может быть обобщена в концепцию называемую частичным применением функции. К примеру, если взять нашу функцию add из предыдущего примера, мы можем напрямую создать инкремент из add не создавая перед этим curriedAdd.

Func<int,int> inc = add.Partial(1);

Где функция Partial написана как:

public static Func<B, R> Partial<A, B, R>(this
Func<A, B, R> f, A a)<br>
{<br>
return b => f(a, b);<br>
}

Обратите внимание как функция принимает функцию и значение a, которое имеет тот же тип что и первый аргумент функции. Она вернет функцию, которая принимает остальные аргументы и затем применяет все аргументы к оригинальной функции. Это может быть обобщено в набор функций, которые производят частично примененные функции.
Tags:functional programming
Hubs: .NET
+13
22.3k 32
Comments 37
Popular right now
Рефакторинг кода .NET
December 7, 202030,200 ₽Luxoft Training
Профессия iOS-разработчик
December 7, 202090,000 ₽SkillFactory
SEO-специалист
December 7, 202064,900 ₽Нетология
Курс по аналитике данных
December 7, 202064,200 ₽SkillFactory