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

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Каррінг)
Перейти до: навігація, пошук

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

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

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

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

Для функції двох змінних , каррування — це операція .

Тобто, має аргумент і повертає функцію однієї змінної .

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

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

Для функції , каррування — це послідовність функцій .

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

Тобто, , повертає функцію одного аргумента (яка в свою чергу теж повертає функцію), а не функцію двох аргументів.

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

В теоретичні інформатиці є такий аналітичний апарат як лямбда-числення, який можна застосувати тільки для функцій однієї змінної. З точки зору теорії множин, каррування це відповідність між множинами та

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

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

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, в якому було додано замикання[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

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

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

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

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