4 Каррирование, мемоизация и стандартные функции в функциональном программировании

Привет, Вы узнаете о том , что такое каррирование, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое каррирование, мемоизация, декаррирование , настоятельно рекомендую прочитать все из категории Функциональное программирование.

Сейчас в JavaScript приносят много техник из функционального программирования. Преимущество в использовании функциональных подходов в JS является лаконичная реализация в пару строк кода и уменшение дублирования. Из этого следует и минусы. Например, в виде читаемости и понимании. Особенно если незнакомы как работает функциональное программирование.

Понятие каррирование

В прошлой главе у нас была проблема, из-за которой нам не удавалось скомпоновать функции mult5 и add, является тот факт, что mult5 принимает один параметр, а add — целых два.

Мы можем очень легко решить эту проблему, уменьшив количество входных данных до одного для всех функций.

Поверьте мне. Это не так плохо, как звучит.

Мы просто пишем функцию сложения, использующую два входных параметра, но принимающую один за раз. Каррированные функции позволяют нам сделать это.

Каррированная функция— это функция, принимающая один аргумент за раз.

Каррирование – это трансформация функций таким образом, чтобы они принимали аргументы не как f(a, b, c) , а как f(a)(b)(c).

Каррирование не вызывает функцию, оно просто трансформирует ее.

Каррирование (от англ. currying, иногда — карринг) — преобразование функции от многих аргументов в набор функций, каждая из которых является функцией от одного аргумента. Возможность такого преобразования впервые отмечена в трудах Готтлоба Фреге, систематически изучена Моисеем Шейнфинкелем в 1920-е годы, а наименование получило по имени Хаскелла Карри — разработчика комбинаторной логики, в которой сведение к функциям одного аргумента носит основополагающий характер.

Определение каррирования

Для функции двух аргументов оператор каррирования выполняет преобразование — берет аргумент типа и возвращает функцию типа . С интуитивной точки зрения, каррирование функции позволяет фиксировать ее некоторый аргумент, возвращая функцию от остальных аргументов. Таким образом, — функция типа .

декаррирование (англ. uncurring) вводится как обратное преобразование — восстанавливающее каррированный аргумент: для функции оператор декаррирования выполняет преобразование ; тип оператора декаррирования — .

На практике каррирование позволяет рассматривать функцию, которая получила не все из предусмотренных аргументов. Оператор каррирования встроен в некоторые языки программирования, что позволяет многоместные функции приводить к каррированному представлению, наиболее характерные примеры таких языков — ML и Haskell. Все языки, поддерживающие замыкание, позволяют записывать каррированные функции.

ЧАСТИЧНОЕ ПРИМЕНЕНИЕ, КАРРИНГ

Фиксацией некоторых аргументов из функции получается новая функция с меньшим числом аргументов.

У термина «карринг» есть три взаимосвязанных значения

1. Фиксация несколько первых аргументов

2. Каррирование f: X*Y -> Z, есть построение f`: X -> (Y -> Z)

3. Применение каррированной функции к аргументам g = f`(x) 25

частный случай частичного применения, при котором фиксируется несколько первых аргументов функции

add :: Integer -> Integer -> Integer
add x y = x + y
inc :: Integer -> Integer
inc = add 1  

Превращение функции F над 2-местным кортежем (парой с типами компонентов X и Y ) в функцию над X, возвращающую функцию над Y (такая функция называется «каррированной» версией F)

matchesRegexpUncurried :: (String,String) -> Bool
matchesRegexpUncurried = ...
matchesRegexpCurried :: String -> (String -> Bool)
matchesRegexpCurried pattern = matcher
  where matcher s = matchesRegexpUncurried (pattern,s) 

Применение каррированной функции к аргументам:

isNumber = matchesRegexpCurried ”−?[0−9]+”

В таком случае говорят, что процедура isNumber получена каррированием процедуры matchesRegexpCurried

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

В теоретической информатике каррирование предоставляет способ изучения функций нескольких аргументов в рамках очень простых теоретических систем, таких как лямбда-исчисление. В рамках теории множеств каррирование — это соответствие между множествами и . В теории категорий каррирование появляется благодаря универсальному свойству экспоненциала; в ситуации декартово замкнутой категории это приводит к следующему соответствию. Существует биекция между множествами морфизмов из бинарного произведения и морфизмами в экспоненциал , которая естественна по и по . Это утверждение эквивалентно тому, что функтор произведения и функтор Hom — сопряженные функторы.

Это является ключевым свойством декартово замкнутой категории, или, более общей, замкнутой моноидальной категории. Первой вполне достаточно для классической логики, однако вторая является удобной теоретической основой для квантовых вычислений. Различие состоит в том, что декартово произведение содержит только информацию о паре двух объектов, тогда как тензорное произведение, используемое в определении моноидальной категории, подходит для описания запутанных состояний .

С точки зрения соответствия Карри — Ховарда существование функций каррирования (обитаемость типа и декаррирования (обитаемость типа ) эквивалентно логическому утверждению (тип-произведение соответствует конъюнкции, а функциональный тип — импликации). Функции каррирования и декаррирования непрерывны по Скотту.

Каррирование с точки зрения программирования

Каррирование широко используется в языках программирования, прежде всего, поддерживающих парадигму функционального программирования. В некоторых языках функции каррированы по умолчанию, то есть, многоместные функции реализуются как одноместные функции высших порядков, а применение аргументов к ним — как последовательность частичных применений.

В языках программирования с функциями первого класса обычно определены операции curry (переводящая функцию сигнатуры вида A, B -> C в функцию сигнатуры A -> B -> C) и uncurry (осуществляющее обратное преобразование — ставящая в соответствие функции сигнатуры вида A -> B -> C двуместную функцию вида A, B -> C). В этих случаях прозрачна связь с операцией частичного применения papply: curry papply = curry.

Итак С их(функций) помощью мы передадим в add первый параметр перед тем, как скомпонуем ее с mult5. Затем, когда mult5AfterAdd10 будет вызвана, add получит свой второй параметр.

В JavaScript мы можем реализовать эту идею, переписав add:

var add = x => y => x + y;

Этот вариант add — функция, принимающая один параметр сразу и второй — позже.

Более детально, функция add принимает отдельный параметр, x, и возвращает функцию, принимающую следующий отдельный параметр, y, который, в конечном счете, будет возвращать результат сложения x и y.

Теперь мы можем использовать новый add, чтобы написать исправный вариант mult5AfterAdd10:

var compose = (f, g) => x => f(g(x));
var mult5AfterAdd10 = compose(mult5, add(10));

Функция компоновки (compose) получает на вход два параметра: f и g. После чего она возвращает функцию, принимающую один параметр, x, с вызовом которой композиция функций f после g осуществится с аргументом x.

Так что же мы на самом деле сделали? Что ж, мы конвертировали нашу простую старую функцию add в ее каррированный вариант. Это сделало add более гибкой, поскольку первый параметр, 10, может быть передан перед непосредственным выполнением функции, а второй — когда mult5AfterAdd10 будет вызвана.

Здесь вам, наверное, должно быть интересно, как же переписать функцию сложения для Elm. Оказывается, делать этого не нужно. В Elm и в других языках функционального программирования все функции автоматически каррированные.

Так что функция add остается неизменной:

add x y =
    x + y

А вот как должна была быть написана mult5AfterAdd10, возвращаясь к Части 3:

mult5AfterAdd10 =
    (mult5 << add 10)

Говоря о синтаксисе, Elm одерживает верх над такими императивными языками, как JavaScript, поскольку он изначально оптимизирован для различных задач функционального программирования, например, каррирования или композиции функций.

Каррирование и рефакторинг

Другой случай, когда каррирование способно показать себя во всей красе — процесс рефакторинга, во время которого вы создаете универсальный вариант функции со множеством параметров, а потом используете ее для создания более адаптированного варианта, но уже с меньшим количеством входных данных.

Допустим, для примера, что у нас есть следующие функции, обрамляющие строку одинарными и двойными скобками:

bracket str =
    "{" ++ str ++ "}"doubleBracket str =
    "{{" ++ str ++ "}}"

И вот, как мы их используем:

bracketedJoe =
    bracket "Joe"doubleBracketedJoe =
    doubleBracket "Joe"

Мы можем обобщить bracket и doubleBracket:

generalBracket prefix str suffix =
    prefix ++ str ++ suffix

Но теперь при каждом вызове generalBracket мы должны передавать сами скобки входными значениями:

bracketedJoe =
    generalBracket "{" "Joe" "}"doubleBracketedJoe =
    generalBracket "{{" "Joe" "}}"

Мы же в действительности хотим взять лучшее из обоих миров.

Если мы перегруппируем входные параметры в generalBracket, мы сможем создать bracket и doubleBracket, выгодно используя факт каррированных функций:

generalBracket prefix suffix str =
    prefix ++ str ++ suffixbracket =
    generalBracket "{" "}"doubleBracket =
    generalBracket "{{" "}}"

Заметьте, что располагая статические параметры первыми, то есть prefix и suffix, а изменяемые параметры — последними, то есть str, мы можем легко создавать адаптированные варианты generalBracket.

Порядок входных параметров очень важен для наиболее выгодного использования каррирования.

Кроме того заметьте, что функции bracket и doubleBracket написаны в бесточечном стиле, то есть аргумент str только предполагается. Обе функции — bracket и doubleBracket — ожидают свой последний параметр.

Теперь мы можем использовать их так, как и хотели:

bracketedJoe =
    bracket "Joe"doubleBracketedJoe =
    doubleBracket "Joe"

Но только теперь мы используем общую функцию каррирования — generalBracket.

Пример вычисления объема тела без каррирования

если какието переменные не изменяются то можно использовать каррирование разіми способами - через bind, через вложенные функции, через стрелочные функции.

Пример каррирования (currying) на JS с использованием bind

Пример каррирования (currying) на JS с использованием вложенных фунуций

Пример каррирования (currying) на JS ES6

const getBrickVolume = width => length => height => width * length * height;

let brickVolumeWithWidthAndLength = getBrickVolume(10)(20)

volume1 = brickVolumeWithWidthAndLength(8);
volume2 = brickVolumeWithWidthAndLength(12);
volume3 = brickVolumeWithWidthAndLength(15);

console.log(volume1,volume2,volume3)

выведет

1600 2400 3000

Примеры

C ++ 11 [ ред. Об этом говорит сайт https://intellect.icu . | ред. код ]

#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

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

ФУНКЦИИ ВМЕСТО ОБЪЕКТОВ связь Замыкания и Каррирование

Замыкание и Каррирование связывают данные и функции аналогично объектам

мемоизация как прием функционального программирования

Мемоизация - это прием, который реализует сохранение результатов выполнения функций для избежания повторных вычислений. Суть достаточна проста - перед каждым вызовом функции происходит проверка вывоза этой функции с такими же аргументами ранее. Если она вызывалась, то возвращается сохраненый результат, иначе происходит вычисление ответа. Далее полученый результат сохраняется и возвращается.

Мемоизация (запоминание, от англ. memoization) — в программировании сохранение результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ. Перед вызовом функции проверяется, вызывалась ли функция ранее:

• если не вызывалась, то функция вызывается, и результат ее выполнения сохраняется;
• если вызывалась, то используется сохраненный результат.

Мемоизация может использоваться не только для увеличения скорости работы программы. Например, она используется при простом взаимно-рекурсивном нисходящем синтаксическом разборе в обобщенном алгоритме нисходящего синтаксического анализа ].

Несмотря на связь с кешированием, мемоизация является особым видом оптимизации, отличающимся от таких способов кеширования, как буферизация и подмена страниц.

В рамках языков логического программирования мемоизация известна под названием «табулирования».

Универсальная функция для создания мемоизованной функции достаточно проста:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function memo(fn) {
    const cache = {};
    const slice = Array.prototype.slice;
    
    return function () {
        const args = slice.call(arguments);
        const key = JSON.stringify(args);
        
        if (cache[key]) {
            return cache[key]; 
        }
        
        const result = fn.apply(null, args);
        cache[key] = result;
        
        return result;
    };
}

Где это можно применить? К примеру, в тех случаях когда нам нужно выполнить сложные и продолжительные и или многократные вычисления.

Стандартные функции функционального программирования

Давайте рассмотрим три стандартные функции, использующиеся в языках функционального программирования.

Но для начала обратим внимание на следующий JavaScript-код:

for (var i = 0; i < something.length; ++i) {
    // do stuff
}

Этот код содержит одну существенную вредную особенность. И это не ошибка. Проблема в том, что это шаблонный код, то есть код, использующийся снова и снова.

Если вы пишете на императивном языке, как Java, C#, JavaScript, PHP, Python и так далее, вы найдете у себя этот шаблон повторяющимся чаще, чем любой другой.

Именно это с этим кодом и не так.

Так избавимся же от него. Давайте обернем его в функцию (или несколько функций) и никогда больше не будет писать цикл for снова. Ну, то есть почти никогда; по крайней мере, до тех пор, пока полностью не перейдем на функциональное программирование.

var things = [1, 2, 3, 4];
for (var i = 0; i < things.length; ++i) {
    things[i] = things[i] * 10; // ТРЕВОГА: ИЗМЕНЕНИЕ ДАННЫХ !!!!
}
console.log(things); // [10, 20, 30, 40]

Вот черт! Изменяемость!

Попробуем-ка еще раз. В этот раз мы не будем изменять things:

var things = [1, 2, 3, 4];
var newThings = [];for (var i = 0; i < things.length; ++i) {
    newThings[i] = things[i] * 10;
}
console.log(newThings); // [10, 20, 30, 40]

Так, ладно, мы не изменили things, но технически мы изменили newThings. Пока что пропустим это мимо глаз. Все-таки мы в мире JavaScript. Однажды коснувшись идей функционального программирования, нам больше не хочется прибегать к изменяемости.

На данном этапе важно понять, как эти функции работают и помогают нам уменьшить «шум» в нашем коде.

Давайте возьмем этот код и положим его в функцию. Мы назовем нашу первую стандартную функцию map (прим. пер., английский глагол «наносить на карту»), так как она переносит каждое значение из старого массива в новое значение в новом массиве:

var map = (f, array) => {
    var newArray = [];    for (var i = 0; i < array.length; ++i) {
        newArray[i] = f(array[i]);
    }
    return newArray;
};

Обратите внимание, что функция, f, передается вовнутрь, и это позволяет нашей функции map делать все, что нам захочется с каждым элементом массива.

Теперь мы можем переписать предыдущий код, используя map:

var things = [1, 2, 3, 4];
var newThings = map(v => v * 10, things);

«Мама, мама, посмотри, я написал код без цикла for!». Теперь его легче читать и, следовательно, анализировать.

Что ж, технически, цикл for все еще есть в функции map. Но зато теперь мы свободны от постоянного повторения этого шаблонный кода.

Теперь давайте напишем другую стандартную функцию, фильтрующую объекты в массиве:

var filter = (pred, array) => {
    var newArray = [];for (var i = 0; i < array.length; ++i) {
        if (pred(array[i]))
            newArray[newArray.length] = array[i];
    }
    return newArray;
};

Заметьте, что если функция-предикат, pred, возвращает TRUE, мы сохраняем элемент, а если FALSE — выбрасываем его.

Вот как можно применить filter для фильтрации нечетных чисел:

var isOdd = x => x % 2 !== 0;
var numbers = [1, 2, 3, 4, 5];
var oddNumbers = filter(isOdd, numbers);
console.log(oddNumbers); // [1, 3, 5]

Использовать наш новый filter гораздо проще, чем вручную постоянно переписывать его с помощью цикла for.

Последняя стандартная функция называется reduce (прим. пер., английский глагол «уменьшать»). Как правило, она используется, когда надо взять список и свести его к одному значению, но, на самом деле, ее возможности куда шире.

Обычно в функциональных языках эта функция носит название fold (прим. пер., английский глагол «свертывать» или «складывать»).

var reduce = (f, start, array) => {
    var acc = start;
    for (var i = 0; i < array.length; ++i)
        acc = f(array[i], acc); // f() принимает 2 аргумента
    return acc;
});

Функция reduce принимает функцию свертки, f, исходное значение, start, и array.

Имейте в виду, что функция свертки, f, принимает два параметра: текущий элемент массива array и аккумуляторacc. Она будет использовать эти параметры для обновления аккумулятора каждую новую итерацию. Значение аккумулятора в момент последней итерации будет возвращено из функции.

Вот пример, который поможет нам понять, как это работает:

var add = (x, y) => x + y;
var values = [1, 2, 3, 4, 5];
var sumOfValues = reduce(add, 0, values);
console.log(sumOfValues); // 15

Заметьте, что функция add принимает два параметра и складывает их. Наша функция reduce как раз ожидает функцию, принимающую два параметра, так что они хорошо сработаются вместе.

Мы начинаем со значения start, равного нулю, и шаг за шагом суммируем значения нашего массива values. С каждой новой итерацией сумма внутри функции reduce увеличивается. И, в конце концов, накопленное значение возвращается как sumOfValues.

Каждая из этих функций, map, filter и reduce, упрощает нам работу с массивами и освобождает от скучного повторения шаблонных циклов for.

Но в функциональном программировании они еще более ценны, поскольку в случаях, когда требуется прибегнуть к цикличности, сложно ограничиться одними рекурсиями. Итеративные функции не просто чрезвычайно полезны. Они просто необходимы.

Вау!! 😲 Ты еще не читал? Это зря!

• Понижение силы операций — оптимизация , заменяющая дорогостоящие операции более дешевыми эквивалентами.
• Таблица поиска — ключевая структура данных, используемая при мемоизации.
• Приспособленец ( шаблон проектирования ) — шаблон, использующий мемоизацию.
• Динамическое программирование — приложения техник мемоизации.
• Отложенные вычисления.
• ленивые вычисления

Исследование, описанное в статье про каррирование, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое каррирование, мемоизация, декаррирование и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Функциональное программирование