Каррирование и частичное применение

Наверняка вы уже слышали такие термины как каррирование и частичное применение. Термины эти используются достаточно широко, однако несмотря на это существует определенная путаница, из-за которой некоторые даже считают, что каррирование и частичное применение - это одно и то же. Кто в этом виноват? Наверное, авторы других блогов.

Но я, разумеется, не такой.

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

Ну прежде всего самое время пересмотреть синтаксис. В Си-подобных языках список аргументов для функций помещается в скобки, но зачем нужны скобки, если никакого списка аргументов у нас больше нет, а есть лишь один-единственный аргумент? Сказано - сделано. Но, оказывается, избавившись от скобок, мы придумали себе другую проблему.

Как следует понимать выражение вида:

 sin x * 2

Или, еще хуже:

 sin x + y * 2

Что конкретно выступает в качестве аргумента для функции sin?

Но не все так страшно. Очевидно, что для операции вызова функции попросту требуется приоритет. Какой же приоритет выбрать? Если взять низкий приоритет, то не всегда будет понятно, что же в действительности является аргументом - по сути аргумент будет представлять собой все выражение, следующее после функции, до самого, так сказать, края листа. Это, очевидно, не очень удобно да и как-то не способствует читабельности. Фактически нам придется постоянно заключать вызов функции в скобки. Получается, в одном месте от скобок избавились, а в другом - их придется писать постоянно, т.е. вместо sin(x) будет (sin x). Невелика заслуга.

А что, если присвоить вызову функции самый высокий приоритет? Тогда никаких дополнительных скобок не требуется, и выражение вида sin x * 2 будет полностью эквивалетно sin(x) * 2.

Годится. Идем дальше.

Что мы еще можем сказать о нашей операции вызова функции? Функция всегда идет первой, а аргумент следует сразу ней. Логично, что оператор вызова функции должен быть левоассоциативным (как, например, большинство операторов в C#) и, соответственно, исполняться будет слево направо. А теперь внимание. Кто-то написал на нашем языке такой код:

 sum 2 2

На первый взгляд кажется, что этот кто-то пытается вызвать функцию sum с двумя аргументами. А ведь функций с двумя аргументами в нашем языке нет. Получается, что код ошибочный?

Вовсе нет. Так как вызов функции левоассоциативный, то выражение вида sum 2 2 полностью эквивалентно (sum 2) 2. Т.е. это вовсе не вызов функции с двумя аргументами, как может показаться на первый взгляд. Это два последовательных вызова функции. Мы вызываем sum с аргументом 2 и считаем, что результатом данного вызова является другая функция, которую мы вызываем еще раз. Аналогичный код на C# выглядел бы так:

 sum(2)(2)

Не слишком красиво, правда? А без скобочек все выглядит очень даже прилично.

Итак, начали мы с того, что стали разрабатывать синтаксис для "бесскобочного" вызова функций, а закончили тем, что придумали, как нам обходиться без функций, принимающих более одного аргумента. Все просто - мы будем создавать функции, которые возвращают другие функции! Сделать это несложно и на C#:

 Func<int,int> sum(int x)
{
    return y => x + y;
}

Как вы знаете, лямбды в C# являются замыканиями - внутри тела лямбды можно обращаться к переменным, объявленным в родительской функции, что и происходит в данном случае. Благодаря этому трюку, объявление функции sum не представляет особых проблем.

Но, согласитесь, выглядит такая функция не очень. А что делать, если у нас будет третий параметр:

 Func<int,int> sum(int x)
{
    return z => y => x + y + z;
}

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

 sum x = \z -> \y -> x + y + z

Но ведь на самом деле это не более чем проблема синтаксиса. Почему бы не добавить немного "сахара"? В сущности мы можем объявлять функции, используя тот же синтаксис, что и при вызове:

 sum x y z = x + y + z

А компилятор сам разберется, что ему надо делать. (Фактически, оба наших определения sum полностью равносильны, просто второе избавляет нас от необходимости вручную описывать замыкания).

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

Однако самый главный вопрос пока остался без ответа - а зачем, собственно, нам потребовались все эти ухищрения?

Дело в том, что каррирование открывает одну очень важную для функционального программирования возможность - а именно частичное применение функций. 

Представьте, что у нас есть функция sum вида \x -> y\ -> x + y. Что произойдет, если при вызове этой функции мы укажем лишь один аргумент? Например, вот так: sum 5. А произойдет следующее - мы как бы создадим новую функцию "на лету", которая умеет складывать числа с 5. Конечно, на основе примера с суммированием оценить преимущества этой техники непросто, однако все становится достаточно очевидно, стоит нам взять чуть более сложную функцию - например, foldl.

Функция foldl - это широко распространенная функция высшего порядка, аналоги которой есть в стандартных библиотеках практически всех функциональных языков. Есть она даже в C# - под видом Aggregate. Данная функция принимает список, первоначальное значение для аккумулятора и другую функцию, которую она как бы "обворачивает" вокруг всех элементов списка (отсюда и название - fold). Функция foldl является такой важной, потому что через нее можно выразить множество других операций. Мы уже коснулись этого в предыдущий раз, когда рассматривали различные варианты использования Aggregate.

Попробуем теперь повторить то же самое на Haskell. Для начала - суммирование всех элементов списка, которое вы уже видели:

 sum = foldl (+) 0

Здесь все просто - операторы в Haskell (как и во многих других функциональных языках) так же являются функциями, поэтому нам нет нужды отдельно описывать операцию сложения, ведь это уже сделали до нас. Поэтому просто передаем в качестве первого аргумента функцию (+). Второй аргумент - первоначальное значениие аккумулятора. У нас это 0. А третий аргумент, собственно, список, элементы которого нужно сложить, мы "забыли". Что получается в итоге? Новая функция, принимающая список и складывающая его элементы.

Попробуем теперь описать функции поиска максимального элемента. Писать ее "в лоб" не очень правильно. Ведь эта функция является частным случаем более общей функции - поиска элемента по условию. Поэтому сначала опишем ее:

 elemBy p (x:xs) = foldl (\x y -> if p x y then x else y) x xs

Здесь мы принимаем предикат и список. Странное выражение (x:xs) - это паттерн, "разбивающий" наш список на первый элемент (голову) и все оставшиеся элементы (хвост). Далее все достаточно очевидно. Теперь, с помощью elemBy мы можем реализовать функцию поиска максимального элемента так:

 maximum = elemBy (>)

А минимального - так:

 minimum = elemBy (<)

Не пугайтесь, если какие-либо примеры вам могут быть не до конца понятны - все же изучение Хаскелла в рамки данной заметки не входит. Главное, чтобы был понятен общий принцип.

Кстати, из-за того, как работает частичное применение, основанное на каррированных функциях, порядок аргументов у нас не совсем такой, к какому вы привыкли. Например, если бы на C# вы писали функцию фильтрации списка на основе предиката, первым бы аргументом у вас был бы сам список, а вторым - функция-предикат. Здесь же все наоборот. И благодаря этому вы сможете частично применить функцию фильтрации, например, вот так:

 nat = filter (>0) --выбираем все натуральные числа

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

 flip f x y = f y x

Мы принимаем функцию и два ее аргумента и вызываем эту функцию, передавая аргументы в обратном порядке. А вот пример использования flip:

 reverse xs = foldl (flip (:)) [] xs

Мы создали функцию, которая "переворачивает" элементы списка в обратном порядке на основе foldl. Для конструирования списка мы используем стандартную функцию-конструктор списков (:). Данная функция в качестве первого аргумента принимает элемент, а в качестве второго - список, в голову которого этот элемент добавляется. Здесь же нам нужен обратный порядок, чего мы и добиваемся с помощью flip.

Вот, собственно, и весь секрет.

Таким образом, каррирование - это преобразование функции вида (a -> b) -> c в функцию вида a->b->c или, говоря человеческим языком, обычной, принимающей несколько параметров функции в такую, которая принимает параметры по одному (и представляет собой цепочку вложенных функций). В большинстве функциональных языков все функции как правило уже каррированные, т.е. несмотря на видимую простоту своих объявлений, представляют собой этакие цепочки замыканий. А частичное применение - это вызов фукнции, в котором мы указываем лишь часть ее аргументов. И каррирование представляет собой одну из возможных технологий, с помощью которой мы можем получить механизм для частичного применения.