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

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

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

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

Визначення

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

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

Часткове застосування функції

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

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

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

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

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

В теоретичній інформатиці є такий аналітичний апарат, як лямбда-числення, який можна застосувати тільки для функцій однієї змінної. З точки зору теорії множин, каррування — це відповідність між множинами $\scriptstyle C^{A\times B}$ та $\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, в якому було додано замикання.

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

Див. також

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