Каррирование: различия между версиями

Интерактивная навигация по истории

(Показать все непатрулированные изменения)

[непроверенная версия]

← Предыдущая правка Следующая правка →

Содержимое удалено Содержимое добавлено

ВизуальныйВики-текст

Линейный

Версия от 02:54, 26 октября 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. Все языки, поддерживающие замыкание, позволяют записывать каррированные функции.

Математическая точка зрения

В теоретической информатике каррирование предоставляет способ изучения функций нескольких аргументов в рамках очень простых теоретических систем, таких как лямбда-исчисление. В рамках теории множеств, каррирование — это соответствие между множествами $\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

D

auto curry( int a ){ return (int b){ return a+b; } }
auto curry_4 = curry(4);
auto val = carry_4(5); // val == 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

См. также

Переопределение функции

Ссылки

[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

[1]

[2]

[3]

[4]

Каррирование: различия между версиями

Версия от 02:54, 26 октября 2014

Содержание

Определение

Математическая точка зрения

Примеры

C++

C++11

C# (3.0)

D

Delphi (2009)

Erlang

F#

Common Lisp

Haskell

Hope

JavaScript

Lisp Scheme

OCaml

Python

Perl

PHP

Ruby

Scala

Objective-C

Google Go

MATLAB

Visual Prolog

SWI Prolog

Примечания

См. также

Ссылки

Навигация

Каррирование: различия между версиями

Версия от 02:54, 26 октября 2014

Определение

Математическая точка зрения

Примеры

C# (3.0)

Delphi (2009)

Lisp Scheme

Примечания

См. также

Ссылки

Навигация

Поиск