Каррирование: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Строка 197: | Строка 197: | ||
<source lang="scala"> |
<source lang="scala"> |
||
def curry(x: Int)(y: Int) = x + y // curry: (Int)(Int)Int |
def curry(x: Int)(y: Int) = x + y // curry: (Int)(Int)Int |
||
f = curry(4) |
f = curry(4)_ |
||
f(5) // Int = 9 |
f(5) // Int = 9 |
||
</source> |
</source> |
Версия от 14:20, 27 сентября 2013
Каррирование или карринг (англ. 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
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
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 carry(int x) {
return Block_copy(^(int y) {
return x + y;
});
}
int res = carry(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