Каррирование

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Каррирование или карринг (англ. currying) в информатике — преобразование функции от многих аргументов в функцию, берущую свои аргументы по одному. Это преобразование было введено М. Шейнфинкелем и Г. Фреге и получило свое название в честь Х. Карри.

Определение[править | править вики-текст]

Для функции h типа h : (A × B) → C оператор каррирования Λ выполняет преобразование Λ(h) : A → (B → C). Таким образом, Λ(h) берет аргумент типа A и возвращает функцию типа B → C. С интуитивной точки зрения, каррирование функции позволяет фиксировать ее некоторый аргумент, возвращая функцию от остальных аргументов. Таким образом, Λ представляет собой функцию типа Λ : (A × B → C) → (A → (B → C)).

Декаррирование вводится как обратное преобразование.

В другом смысле, преобразование ε, противоположное каррированию, восстанавливает каррированный аргумент. Для функции k типа k : A → (B → C) оператор ε типа ε: (U → V) × U → V для произвольных a: A, U = A, V = B → C выполняет преобразование ε[k, a]: B → C. Остаётся положить k = Λ(h), и для ε: (A →(B → C)) × A → (B → C) записываем ε[Λ(h), a]: B → C и ε[k, a] = ε[Λ(h), a], что устанавливает связь между каррированой и некаррированной записью функции[1].

На практике каррирование позволяет рассматривать функцию, которая получила один из аргументов, но не все. Оператор каррирования встроен в некоторые языки программирования, что позволяет многоместные функции приводить к каррированному представлению. Примером служат языки ML и Haskell. Все языки, поддерживающие замыкание, позволяют записывать каррированные функции.

Математическая точка зрения[править | править вики-текст]

В теоретической информатике каррирование предоставляет способ изучения функций нескольких аргументов в рамках очень простых теоретических систем, таких как лямбда-исчисление. В рамках теории множеств, каррирование — это соответствие между множествами \scriptstyle A^{B\times C} и \scriptstyle\left(A^C\right)^B. В теории категорий каррирование появляется благодаря универсальному свойству экспоненциала; в ситуации декартово замкнутой категории это приводит к следующему соответствию. Существует биекция между множествами морфизмов из бинарного произведения \scriptstyle f \colon (X \times Y) \to Z и морфизмами в экспоненциал \scriptstyle g \colon X \to Z^Y , которая естественна по X и по Z. Это утверждение эквивалентно тому, что функтор произведения и функтор Hom — сопряженные функторы.

Это является ключевым свойством декартово замкнутой категории, или, более общо, замкнутой моноидальной категории. Первой вполне достаточно для классической логики, однако вторая является удобной теоретической основой для квантовых вычислений. Различие состоит в том, что декартово произведение содержит только информацию о паре двух объектов, тогда как тензорное произведение, используемое в определении моноидальной категории, подходит для описания запутанных состояний[2].

Примеры[править | править вики-текст]

C++[править | править вики-текст]

Требует наличие библиотек Boost.

#include <boost/function.hpp>
#include <boost/lambda/lambda.hpp>
 
boost::function<int(int)> curry(int a) {
  return (a + boost::lambda::_1);
}
int a = curry(4)(5); // 9

Впрочем, в относительно простых (тривиальных) случаях достаточно Стандартной библиотеки С++ (STL).

#include <functional>
 
std::binder1st<std::plus<int> > curry(int a) {
  return std::bind1st(std::plus<int>(), a);
}
int a = curry(4)(5); // 9

Того же эффекта можно добиться и на чистых классах.

class curry {
private:
  int m_x;
public:
  curry(int x): m_x(x) {}
  int operator() (int y) { return m_x + y; }
};
int a = curry(4)(5); // 9

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

class curry {
private:
  int m_total;
public:
  curry(int x): m_total(x) {}
  curry& operator() (int y) { m_total += y; return *this; }
  operator int(void) { return m_total; }
};
int a1 = curry(4)(5); // 9
int a2 = curry(4)(5)(6); // 15
int a3 = curry(4)(5)(6)(7); // 22

C++11[править | править вики-текст]

#include<functional>
auto curry = ([](int x)->std::function<int(int)>{
       return [x](int y)->int {
          return x+y;
       };
});
int a = curry(4)(5); // 9
auto curry_4 = curry(4);
int b = curry_4(5); // 9

C# (3.0)[править | править вики-текст]

Func<int, Func<int, int>> curry = (x => (y => x + y));
curry(4)(5); // 9

Delphi (2009)[править | править вики-текст]

type
  TIntFunc = reference to function(x: Integer): Integer;
 
 
function Curry(x: Integer): TIntFunc;
begin
  Result := function(y: Integer): Integer
    begin
      Result := x + y;
    end;
end;
 
begin
  Curry(4)(5); // 9
end.

Erlang[править | править вики-текст]

Curry = fun(A) -> fun(B) -> A + B end end.
(Curry(3))(4). % => 7

F#[править | править вики-текст]

let add a b = a + b //'a -> 'a -> 'a
let addOne = add 1 //'a -> 'a
let x = addOne 10 // 11

Common Lisp[править | править вики-текст]

(defun curry(x)
  (lambda (y) (+ x y)))
((curry 2) 3) ; вернёт 5
; из-за особенностей семантики вернет ошибку(в отличие от Scheme)...
(funcall (curry 2) 3) ; вернет 5

Haskell[править | править вики-текст]

curry x = (\y -> x + y) -- также можно написать curry = (+)
curry 2 3 -- вернет 5

Hope[править | править вики-текст]

! curry - turn a binary function into a function producing a function.
!	(Named after Haskell B. Curry)
! e.g. curry f x y = f(x, y)
dec curry : (alpha # beta -> gamma) -> alpha -> beta -> gamma;
--- curry f <= lambda x => lambda y => f(x, y);
curry (+) 1;
>> lambda y => 1 + y: num->num
(curry (+) 1) 2;
>>3: num

JavaScript[править | править вики-текст]

function curry(x){
    return function(y){
        return x + y;
    }
}
curry(4)(5); // вернёт 9

Начиная с версии ECMAScript 5 возможен также следующий код:

function curry(x){
    return function(x, y){
        return x + y;
    }.bind(null /* значение this */, x)
}
curry(4)(5); // вернёт 9

Lisp Scheme[править | править вики-текст]

; определение
(define (curry x)
  (lambda (y)
    (+ x y)))
; вызов
(let ((curr (curry 4)))
  (curr 5)) ;результат 9
; или так
((curry 4) 5)

OCaml[править | править вики-текст]

let curry x = function y -> x + y;;   (* val curry : int -> int -> int = <fun> *)
let a = curry 4 5;;   (* - : int = 9 *)

OCaml является языком из семейства ML, как писалось выше, в языках этого семейства приведение многоместной функции к каррированному представлению выполняется автоматически. Поэтому можно написать так:

let curry x y = x + y;;   (* val curry : int -> int -> int = <fun> *)
let a = curry 4;;   (* val a : int -> int = <fun> *)
a 5;;   (* - : int = 9 *)

Python[править | править вики-текст]

curry = lambda x: lambda y: x + y
curry(4)(5)   # => 9

Perl[править | править вики-текст]

sub curry
{
    my $x = shift;
    return sub { return $x + shift }
}
curry(4)->(5);  # 9

PHP[править | править вики-текст]

Работает начиная с PHP 5.3, в котором были добавлены замыкания[3].

function curry($x) {
    return function ($y) use ($x) {
               return $x + $y;
           };
}
$a = curry(5);
$b = $a(10); // 15

Ruby[править | править вики-текст]

def curry(x)
  Proc.new{|y| x + y}
end
curry(1).call(2) # => 3

Scala[править | править вики-текст]

def curry(x: Int)(y: Int) = x + y // curry: (Int)(Int)Int
f = curry(4)_
f(5) // Int = 9

Objective-C[править | править вики-текст]

Пример реализации каррирования в Objective-C с использованием блоков (blocks):

typedef int (^Add)(int y);
 
Add curry(int x) {	
	return  Block_copy(^(int y) {	
		return x + y;
	});
}
 
int res = curry(5)(6);
NSLog(@"%i",res);
>>11

Google Go[править | править вики-текст]

Пример реализации каррирования в Google Go:

package main
 
func main() {
  curry := func(x int) func(int) int {
    return func(y int) int {
      return x+y
    }
  }
  print(curry(2)(3)) // 5
}

MATLAB[править | править вики-текст]

Пример реализации каррирования в MATLAB:

curry = @(x)@(y)x+y;
 
a = curry(5);
disp(a(6)); % 11

Visual Prolog[править | править вики-текст]

Пример реализации каррирования в Visual Prolog:

F = {(Y) = {(X)=X+Y}},
write(F(2)(3)),    % 5

SWI Prolog[править | править вики-текст]

Пример реализации каррирования в SWI Prolog[4]ː

t(A, B):- A > B, !.
call(call(t, 3), 0). % true

Примечания[править | править вики-текст]

  1. Wolfengagen, V.E. Combinatory logic in programming. Computations with objects through examples and exercises. — 2-nd ed. — M.: «Center JurInfoR» Ltd., 2003. — x+337 с. ISBN 5-89158-101-9.
  2. John c. Baez and Mike Stay, «Physics, Topology, Logic and Computation: A Rosetta Stone», (2009) ArXiv 0903.0340 in New Structures for Physics, ed. Bob Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 95-174.
  3. Currying in PHP
  4. 2.2 Каррирование в SWI Prolog

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]