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

Автор оригинала: 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, которое имеет тот же тип что и первый аргумент функции. Она вернет функцию, которая принимает остальные аргументы и затем применяет все аргументы к оригинальной функции. Это может быть обобщено в набор функций, которые производят частично примененные функции.
Поделиться публикацией

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 37

    0
    спасибо, статья интересная.
    но вот «частичная аппликация» — не лучше ли все же «частичное применение»?
    так как «аппликация» четко ассоциируется с другим. а вот функцию как-раз таки «применяют».
    или я не прав?
    +2
    Примеры в статье лично меня скорее запутали, чем что-то пояснили, но за ссылку на термин в Википедии спасибо. Всю жизнь говорил прозой, и не знал :-) Давно использую похожие трюки по мере надобности.

    Успехов.
      +1
      Если можно, приведите примеры, как вы это используете. В статье действительно они «нежизненные».
        +1
        Вот, например, helper для Kohana, который я написал для своего проекта.
        Обе функции имеют переменное число параметров.

        Вот не уверен, какое из пониманий верно:

        1. Метод links_Core::get($key, ...) является каррированием для links_Core::get_csrf($csrf_token, $key, ...).

        2. Метод links_Core::get($key, ...) являлся бы каррирование для links_Core::get_csrf($csrf_token, $link), где $link — результат функции links_Core::get($key, ...).

        Хотя в общем-то не важно, какой из вариантов формально верен. Важно, что реализации идеи встречаются на практике.

        class links_Core
        {
            private static $links = array();

            public function get($key)
            {
                if(empty(self::$links))
                    self::$links = Kohana::config('url/my_project.links', false, true);

                if(!isset(self::$links[$key]))
                    return false;

                $args = func_get_args();
                array_shift($args);
                array_unshift($args, self::$links[$key]);

                return url::base().call_user_func_array('sprintf', $args);
            }

            public function get_csrf($csrf_token, $key)
            {
                $args = func_get_args();
                array_shift($args);
                $link = call_user_func_array(array('self', 'get'), $args);

                if(strpos($link, '?') !== false)
                    return $link.'&csrf='.$csrf_token;
                else
                    return $link.'?csrf='.$csrf_token;
            }
        }


        * This source code was highlighted with Source Code Highlighter.
        0
        Конкретно мне такие статьи позволяют лучше ориентироваться в функциональном стиле кодирования. Кроме того, если бы речь шла не о сложении, а о более сложном алгоритме, то каррированием, как я понимаю, можно упростить реализацию, тестирование и использование.

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

        С другой стороны, вот все кто с LINQ работал должны знать такой метод:

        msdn.microsoft.com/ru-ru/library/bb548658.aspx

        Жесть, правда? А надо както с этим работать. Вот, умение преобразовывать функции тут как раз помогает. В том числе и понимание карринга.
          +1
          можно посмотреть на F#

          например, там можно делать композицию функций:

          readFile «c:\test.txt» |> addToEachLine «1» |> writeFile «c:\test2.txt»

          операция оператор |> берет две функции и применяет результат первой ко второй

          благодаря каррированию writeFile превращается из функции с двумя аргументами в функцию с одним аргументом и ее можно подвать на вход |>

          В F# большинство встроенных функций для работы со списками, например, сначала бедур дополнительные аргументы а потом сам список. В результате из них легко каррированием получаются функции обработки с одним аргуметом «список»
          Или последовательность.

          Например seq.map берет функцию и список и последовательность, применяет функию ко всем аргументам последовательности и возвращает последовательность результатов.

          тогда Seq.map (fun x -> x + 1) вернет функцию, которя к заданной последовательности прибавит единицу.

          И такие функции удобно выстраивать в цепочкит типа

          [1; 2; 3] |> List.filter (fun x -> x % 2 = 0) |> List.map (fun x-> x + 1)
            0
            Композиция это разве не оператор >>?
            +2
            Предлагаю заспамить авторов F# требованием добавить возможность перегрузки по возвращаемому значению. Без этого каррированными функциями полноценно не попользоваться.
              0
              это как? чем щас не нравится?
                0
                type Vector = { X: int; Y: int; }

                static member Add x y = x + y
                static member Add x y = { X = x.X + y.X; Y = x.Y + y.Y; }

                Сейчас так не работает, т.к. здесь перегрузка по типу возвращаемого значения (каждое Add по сути — пара свойств, одно типа int -> int -> int, другое — Vector -> Vector -> Vector). В CLR так можно, но из всех языков разрешено вроде только в MSIL asm.
                  0
                  1) при чем тут карррирование
                  2) почему Add int -> int -> int должен быть членом Vector
                  3) как будет работать вывод типов
                    0
                    1) Add — curried function
                    2) Это просто пример того, что не работает.
                    3) Не вижу сложности вывести тип для обоих Add как обычно.
                      +1
                      все равно не понимаю, при чем тут карринг? по-моему это совершенно ортогонально каррингу — не вижу ни какого частичного применения здесь.

            +1
            В stl есть хелперы bind1st и bind2nd, которые выполняют частичное применение функции 2х аргументов, позволяя вернуть функтор-замыкание уже с одним аргументом. Используется достаточно часто
              0
              Ну а в Boost есть boost::bind ;)
          0
          Я правильно понял, что основная область применения карри-функций — это функции с переменным числом параметров?
            0
            Я понял также. Не знаю правильно или нет. )
              +3
              Каждый что-то понял, но никто не уверен, то понял ли он именно то, что имелось кем-то в виду. Вопрос в том, имел ли кто-то что-то в виду или что-то тут действительно не так :-p

              PS: Откаррируйте-ка мой комментарий, а? :-)
              +1
              Не совсем «с переменным».

              Допустим есть некая универсальная функция с кучей параметров, которая делает сложное действие А (в примерах — сложение двух чисел).

              int Sum(int a, int b){ return a+b; }

              А вам нужна вот в данный конкретный момент функция-частный случай первой (в примере — «увеличение на 1» — это частный случай сложения).

              Нужна она вам, что передать её в качестве параметра в другую функцию:

              void SomeOtherFunction(Func<int, int>);

              Эта функция требует, чтобы ей передали ф-ю, принимающую один параметр int.

              Вы можете объявить её вручную:

              int Inc (int a) { return Sum(a, 1); }

              а потом передавать Inc:

              SomeOtherFunction(var1, var2, Inc);

              Но вместо этого вы лучше просто скаррируете Sum: «Sum.Partial(1)», тем самым избавляясь от ненужного описания функции Inc, и получите вот такой вызов:

              SomeOtherFunction(var1, var2, Sum.Partial(1));
                +1
                то есть, переменное кол-во параметров не в смысле, что одна и та же функция имеет переменное количество параметров, а в том, что вы создаёте новые функции, отличные от изначальной количеством параметров
                  0
                  А, въехал? спасибо.
                  Мысленно плюсую.
              0
              Спасибо за статью. Я так понимаю это ваша реализация, а то я замучился искать упоминание в MSDN? :)
                0
                Нет, не моя. Это перевод )
                +1
                да, каррирование в C# — это уже как-то немного неожиданно, хотя в принципе после введения лямбд ничего странного вроде и нет.
                хм, а написать Y-комбинатор-то получается тоже возможно, или я путаю…
                так что дело за монадами ;))
                  +1
                  лямбды тут не причем. это все можно было писать еще и в C# 2.0 с анонимными методами
                  монады аналогично. как только появились генерики можно было писать. только вот использовать не совсем удобно было потому как не было сахара

                  p.s. наслаждайтесь:

                  delegate Func<T,R> RecFunc<T,R>(RecFunc<T,R> f);

                  Func<T, R> Y<T, R>(Func<Func<T, R>, Func<T, R>> f)
                  {
                  RecFunc<T, R> recFunc = r => t => f(r®)(t);
                  return recFunc(recFunc);
                  }
                    +1
                    RecFunc<T, R> recFunc = r => t => f(r( r ))(t);
                      0
                      да, все верно. и все-таки после прочтения остается ощущение что пусть каждый язык занимается тем, для чего предназначен. богу богову, кесарю кесарево.
                  0
                  Интересно, почему на русском это назвали каррирование… ведь на англ. яз. вроде это произносится как «кёрриинг». :)
                    +2
                    Сахар это конечно хорошо, но нужно не забывать, что при применении выражений типа a => b => f(a,b), передача значения 'a' в место вызова f(a, b) происходит через поле автоматически сгенерированного класса. Т.е. выполнение этого выражения влечет за собой создание временного объекта в куче. И хотя затраты на выделение памяти в CLR сведены к минимуму, количество объектов все же может отрицательно повлиять на производительность. Другими словами, злоупотреблять сахаром не стоит — можно нажить диабет :)
                      0
                      Вот этому как-то мало уделяют внимания, когда говорят о новых фишечках языка. Может память действительно более не ограниченный ресурс, но все таки…
                        0
                        Да, каждая медаль имеет две стороны. Это как шаблоны C++ в свое время — все очень удобно и круто, но экзешник распухает капитально (а под досом это имело значение...)

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое