Каррінг (інформатика)

Каррування або каррінг (англ. currying) в інформатиці — метод обчислення функції від багатьох аргументів, перетворенням її в послідовність функцій одного аргумента. Це перетворення було введено Мойсеєм Шейнфінкелем і отримало свою назву від свого поширювача, Гаскеля Каррі.

Операція каррування є функцією вищого порядку, оскільки, вона приймає і повертає функцію.

Карровані функції можуть використовуватись у всіх мовах програмування, що підтримують замикання. Хоча не карровані функції обчислюються швидше, оскільки не потребують часткового застосування та створення замикання.

Визначення[ред. | ред. код]

Для функції двох змінних ${\displaystyle \scriptstyle f\colon (X\times Y)\to Z}$, каррування — це операція ${\displaystyle \scriptstyle {\text{curry}}(f)\colon X\to (Y\to Z)}$.

Тобто, ${\displaystyle \scriptstyle {\text{curry}}(f)}$ має аргумент ${\displaystyle \scriptstyle X}$ і повертає функцію однієї змінної ${\displaystyle \scriptstyle Y\to Z}$.

Часткове застосування функції[ред. | ред. код]

Каррування — це не є зменшення кількості аргументів функції за допомогою їх фіксації, це побудова послідовності функцій одного аргумента, кожна з яких повертає наступну.

Для функції ${\displaystyle \scriptstyle f\colon (X\times Y\times Z)\to N}$, каррування — це послідовність функцій ${\displaystyle \scriptstyle {\text{curry}}(f)\colon X\to (Y\to (Z\to N))}$.

Знаходження значення функції — це ${\displaystyle \scriptstyle f(1,2,3)}$, а при обчисленні значення каррованої функції ${\displaystyle \scriptstyle f_{\text{curried}}(1)(2)(3)}$, для кожного аргумента, при його підстановці отримуємо нову функцію, в яку підставляємо наступний аргумент і т. д.

Тобто, ${\displaystyle \scriptstyle f_{\text{curried}}(1)}$, повертає функцію одного аргумента (яка в свою чергу теж повертає функцію), а не функцію двох аргументів.

Математична точка зору[ред. | ред. код]

В теоретичній інформатиці є такий аналітичний апарат, як лямбда-числення, який можна застосувати тільки для функцій однієї змінної. З точки зору теорії множин, каррування — це відповідність між множинами ${\displaystyle \scriptstyle C^{A\times B}}$ та ${\displaystyle \scriptstyle \left(C^{B}\right)^{A}}$ …

Приклади[ред. | ред. код]

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 

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 можливий код:

const curry = (fn,x) => (y) => fn(x,y); const add = (x,y) => x+y; curry(add,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 fn, x: lambda y: fn(x, y) add = lambda x, y: x + y curry(add, 4)(5)   # => 9 

Perl[ред. | ред. код]

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

PHP[ред. | ред. код]

Починаючи з PHP 5.3, в якому було додано замикання^[1].

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[ред. | ред. код]

Приклад реалізації з використанням блоків (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 

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[ред. | ред. код]

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

Visual Prolog[ред. | ред. код]

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

SWI Prolog[ред. | ред. код]

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

Див. також[ред. | ред. код]

• Ліниві обчислення

Примітки[ред. | ред. код]

Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки. Матеріал без джерел може бути піддано сумніву та вилучено. (квітень 2020)