Каррирование: различия между версиями
[непроверенная версия] | [отпатрулированная версия] |
общо -> обще |
Bezik (обсуждение | вклад) м откат правок 178.124.201.58 (обс) к версии РоманСузи |
||
Строка 18: | Строка 18: | ||
В теоретической информатике каррирование предоставляет способ изучения функций нескольких аргументов в рамках очень простых теоретических систем, таких как [[лямбда-исчисление]]. В рамках [[теория множеств|теории множеств]], каррирование — это соответствие между множествами <math>\scriptstyle A^{B\times C}</math> и <math>\scriptstyle\left(A^C\right)^B</math>. В [[теория категорий|теории категорий]] каррирование появляется благодаря [[универсальное свойство|универсальному свойству]] [[экспоненциал]]а; в ситуации [[декартово замкнутая категория|декартово замкнутой категории]] это приводит к следующему соответствию. Существует биекция между множествами морфизмов из бинарного [[произведение (теория категорий)|произведения]] <math>\scriptstyle f \colon (X \times Y) \to Z </math> и морфизмами в экспоненциал <math>\scriptstyle g \colon X \to Z^Y </math>, которая [[естественное преобразование|естественна]] по X и по Z. Это утверждение эквивалентно тому, что функтор произведения и [[функтор Hom]] — сопряженные функторы. |
В теоретической информатике каррирование предоставляет способ изучения функций нескольких аргументов в рамках очень простых теоретических систем, таких как [[лямбда-исчисление]]. В рамках [[теория множеств|теории множеств]], каррирование — это соответствие между множествами <math>\scriptstyle A^{B\times C}</math> и <math>\scriptstyle\left(A^C\right)^B</math>. В [[теория категорий|теории категорий]] каррирование появляется благодаря [[универсальное свойство|универсальному свойству]] [[экспоненциал]]а; в ситуации [[декартово замкнутая категория|декартово замкнутой категории]] это приводит к следующему соответствию. Существует биекция между множествами морфизмов из бинарного [[произведение (теория категорий)|произведения]] <math>\scriptstyle f \colon (X \times Y) \to Z </math> и морфизмами в экспоненциал <math>\scriptstyle g \colon X \to Z^Y </math>, которая [[естественное преобразование|естественна]] по X и по Z. Это утверждение эквивалентно тому, что функтор произведения и [[функтор Hom]] — сопряженные функторы. |
||
Это является ключевым свойством декартово замкнутой категории, или, более |
Это является ключевым свойством декартово замкнутой категории, или, более общо, [[замкнутая моноидальная категория|замкнутой моноидальной категории]]. Первой вполне достаточно для классической логики, однако вторая является удобной теоретической основой для [[квантовый компьютер|квантовых вычислений]]. Различие состоит в том, что декартово произведение содержит только информацию о паре двух объектов, тогда как тензорное произведение, используемое в определении [[моноидальная категория|моноидальной категории]], подходит для описания [[квантовая запутанность|запутанных состояний]]<ref>John c. Baez and Mike Stay, «[http://math.ucr.edu/home/baez/rosetta/rose3.pdf Physics, Topology, Logic and Computation: A Rosetta Stone]», (2009) [http://arxiv.org/abs/0903.0340/ ArXiv 0903.0340] in ''New Structures for Physics'', ed. Bob Coecke, ''Lecture Notes in Physics'' vol. '''813''', Springer, Berlin, 2011, pp. 95-174.</ref>. |
||
== Примеры == |
== Примеры == |
Версия от 13:58, 7 декабря 2014
Каррирование или карринг (англ. 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. Все языки, поддерживающие замыкание, позволяют записывать каррированные функции.
Математическая точка зрения
В теоретической информатике каррирование предоставляет способ изучения функций нескольких аргументов в рамках очень простых теоретических систем, таких как лямбда-исчисление. В рамках теории множеств, каррирование — это соответствие между множествами и . В теории категорий каррирование появляется благодаря универсальному свойству экспоненциала; в ситуации декартово замкнутой категории это приводит к следующему соответствию. Существует биекция между множествами морфизмов из бинарного произведения и морфизмами в экспоненциал , которая естественна по 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
D
auto curry( int a ){ return (int b){ return a+b; } }
auto val = carry(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
Примечания
- ↑ 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.
- ↑ 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.
- ↑ Currying in PHP
- ↑ 2.2 Каррирование в SWI Prolog