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

Каррування або каррінг (англ. 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}}$ …

Приклади

#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 

! 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 

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

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

Див. також

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

Примітки

1. . Архів оригіналу за 7 жовтня 2014. Процитовано 3 жовтня 2014.