Объекты и функции первого класса
Функции высшего порядка
Композиция функций
Мемоизация
Каррирование

Объекты и функции первого класса

Объект называется объектом первого класса (First-class Object/Entity/Citizen), если он

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

Остальные объекты считаются объектами второго класса (Second-class Objects).

Функции, являющиеся объектами первого класса, называют функциями первого класса (First-class Function).

Во многих языках программирования понятие функции первого класса ассоциируется с понятием анонимной функции (anonymous functions).

В JavaScript все функции являются функциями первого класса.

// 1., 2. и 3.
const createLogger = log => (...args) => log(...args);

// 3.
const log = createLogger(console.log);
log('qq'); // "qq"

// 4.
const speaker = {
  hello: () => log('hello'),
}

Функции высшего порядка

Функция высшего порядка (Higher-order Function) — функция, принимающая другую функцию в качестве аргумента или возвращающая функцию в качестве результата своего выполнения.

JavaScript является событийно-ориентированным (Event-driven) языком. Многие действия выполняются по наступлению определённых событий или выполняются строго после других действий. Функции высшего порядка, принимающие в качестве параметра другие функции, помогают добиться такого поведения. Функции-параметры называют функциями обратного вызова.

const callback = () => console.log('done');

document.addEventListener('onClick', callback);

setTimeout(callback, 1000);

const p = new Promise(res => res());
p.then(callback);

const calculate = (cb) => {
  const result = 1 + 2;
  cb();
  return result;
};
calculate(callback);

Пример функции высшего порядка, реализующей замыкание. Она замыкает переменную count и возвращает другую функцию, изменяющую замкнутую переменную.

/* счётчик */
const createCounter = () => {
  let count = 0;
  return () => count += 1;
}

const counter = createCounter();
console.log(counter()); // 1
console.log(counter()); // 2

const anotherCounter = createCounter();
console.log(anotherCounter()); // 1

Пример функции высшего порядка, реализующей каррирование. Она возвращает другую функцию, использующую свой параметр y и параметр функции высшего порядка x, доступный из замыкания.

/* конкатенация двух строк */
const concat = x => y => `${x} ${y}`;

console.log(concat('Simple')('notes')); // "Simple notes"

Пример функции высшего подярка, принимающей и возвращающей React-компонент (компоненты в React являются функциями), которая называется компонентом высшего порядка (Higher-order Component, HOC).

const user = { name: 'Max' };

const withUser = Component => props => (
  <Component {...props} user={user} />
);

const Article = withUser(props => <div>{props.user.name}</div>);

const createConditionalComponent => condition => Component => props => (
  condition ? <Component {...props} /> : null;
);

const Text = () => (<span>Notes</span>);

const AlwayRenderingText = createConditionalComponent(true)(Text);
const NeverRenderingText = createConditionalComponent(false)(Text);

Композиция функций

Композиция функций (Function Composition) — применение одной функции к результату другой.

Функция h — композиция функций g и f, если h(x) = g(f(x)). Обозначение: h(x) = (g ∘ f)(x).

const increment = val => val + 1;
const decrement = val => val - 1;

const foo = decrement(increment(0)); // композиция
console.log(foo); // 0
const bar = increment(increment(0)); // композиция
console.log(bar); // 2

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

const divide = (value, divider) => value / divider;
const pow = (value, power) => value ** power;
divide(pow(3, pow(2, 2)), 3); // 27 = (3 ^ (2 * 2)) / 3

Если в композиции участвует слишком много функций, то её код становится трудно читаемым. Для таких случаев можно использовать функцию compose, которая принимает несколько функции и составляет из них композицию справа налево (начинает с последней и заканчивает первой).

const compose = (...fns) => initialValue => fns.reduceRight((value, fn) => fn(value), initialValue);

console.log(compose(
  increment,
  increment,
  decrement,
  increment,
  increment,
)(4)); // 7

/* массив из 10 функций increment */
const fns = Array(10).fill(increment); // [ƒ, ƒ, ƒ, ƒ, ƒ, ƒ, ƒ, ƒ, ƒ, ƒ]
console.log(compose(...fns)(0)); // 10

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

divide(pow(3, pow(2, 2)), 3); // 27 = (3 ^ (2 * 2)) / 3
/* преобразуется в */
compose(
  value => divide(value, 3),
  value => pow(3, value),
  () => pow(2, 2),
)();

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

compose(
  value => divide(value, 3),
  value => pow(3, value),
  ([value, power]) => pow(value, power),
)([2, 2]);

Стоит ещё раз отметить, что функция compose начинается с последней переданной функции, а не с первой.

Pipe

Функция pipe работает аналогично функции compose, но составляет композицию из своих функций-аргументов слева направо.

const pipe = (...fns) => initialValue => fns.reduce((value, fn) => fn(value), initialValue);

Её использование выглядит более естественным.

pipe(
  ([value, power]) => pow(value, power),
  value => pow(3, value),
  value => divide(value, 3),
)([2, 2]);

Несколько аргументов

Можно переписать compose и pipe таким образом, чтобы первая функция принимала несколько аргументов.

const compose = (...fns) => fns.reduceRight((f, g) => (...args) => g(f(...args)));
const pipe = (...fns) => fns.reduce((f, g) => (...args) => g(f(...args)));
/* или */
const compose = (...fns) => fns.reduce((f, g) => (...args) => f(g(...args)));
const pipe = (...fns) => fns.reduceRight((f, g) => (...args) => f(g(...args)));

pipe(
  (value, power) => pow(value, power),
  value => pow(3, value),
  value => divide(value, 3),
)(2, 2);

Промежуточные функции по-прежнему не смогут принять больше одного параметра.

Описание работы функции compose по шагам. Метод reduce при отсутствии начального значения кладёт первый элемент массива первым параметром, второй - вторым параметром.

const compose = (...fns) => fns.reduce((f, g) => (...args) => f(g(...args)));
/* далее псевдокод */
compose(a, b, c, d)(1, 3)
/* I */
(a, b) => args => a(b(args)) := k
/* II */
(k, c) => args => k(c(args)) := m
/* III */
(m, d) => args => m(d(args)) := n
/* IV */
n := args => a(b(c(d(args)));
/* V */
n(1, 3) := a(b(c(d(1, 3)))

Мемоизация

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

Мемоизация подразумевает проведение проверки перед каждым вызовом мемоизируемой функции:

если функция вызывалась ранее с такими же параметрами, как сейчас, — вернуть результат из памяти,
иначе — вычислить и записать в память.

Напишем простую функцию инкремента.

const inc = val => val + 1;
console.log(inc(5)); // 6

Мемоизируем её.

let memory = {};

const incMemo = (val) => {
  if (memory[val] === void 0) {
    memory[val] = inc(val);
  } else {
    console.log('took from memory!');
  }
  return memory[val];
};

console.log(incMemo(5)); // 6
console.log(memory); // { 5: 6 }
console.log(incMemo(5)); // 'took from memory!', 6

Обобщение для любой функции одного аргумента

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

let memory = {};

const memo = fn => (val) => {
  if (memory[val] === void 0) {
    memory[val] = fn(val);
  } else {
    console.log('took from memory!');
  }
  return memory[val];
};

const dec = memo(val => val - 1);

console.log(dec(6)); // 5
console.log(dec(6)); // 'took from memory!', 5

Когда использовать мемоизацию?

Мемоизация экономит время, но при этом использует память.

Простейшие арифметические операции +, -, *, / выполняются слишком быстро, чтобы сохранять их в памяти. Поиск по ключу в хранилище не выполнится быстрее (и это не считая затрат памяти).

Обычно мемоизируют только чистые функции (вызов с определённым набором параметров всегда вернёт один и тот же результат). Нет смысла мемоизировать функцию, генерирующую рандомные значения: проще положить результат её выполнения в переменную и использовать её. Нет смысла мемоизировать запрос к серверу, так как на сервере данные могут изменяться: намного важнее показывать пользователю последнюю версию.

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

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

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

Несколько аргументов

Перепишем функцию memo таким образом, чтобы она могла принимать несколько аргументов.

let memory = {};

const memo = fn => (...args) => {
  const key = args.toString();
  if (memory[key] === void 0) {
    memory[key] = fn(...args);
  } else {
    console.log('took from memory!');
  }
  return memory[key];
};

const mulFn = (a, b) => a * b;
const mul = memo(mulFn);

console.log(mul(3, 7)); // 21
console.log(memory); // { "3, 7": 21 }
console.log(mul(3, 7)); // 'took from memory!', 21

Отдельное хранилище для каждой функции

В примерах выше используется общее хранилище для всех мемоизируемых функций. Перепишем функцию memo таким образом, чтобы у каждой функции fn было своё хранилище.

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

console.log(mulFn); // "(a, b) => a * b"

Будем использовать это представление в качестве ключа в хранилище memory. Этому ключу будет соответствовать хранилище для конкретной функции fn.

let memory = {};

const memo = fn => (...args) => {
  const fnKey = fn.toString();
  memory[fnKey] = memory[fnKey] || {};
  const argsKey = args.toString();
  if (memory[fnKey][argsKey] === void 0) {
    memory[fnKey][argsKey] = fn(...args);
  } else {
    console.log('took from memory!');
  }
  return memory[fnKey][argsKey];
};

const divideFn = (a, b) => a / b;
const divide = memo(divideFn);

console.log(divide(21, 7)); // 3
console.log(memory); // { "(a, b) => a * b": { "3,7": 21 } }
console.log(memory[divideFn.toString()]); // { "3,7": 21 }
console.log(divide(21, 7)); // 'took from memory!', 3

Очистка хранилищ

Сейчас хранилище memory очищается только вручную: результаты вычислений остаются даже тогда, когда функция больше не используется.

let sumFn = (...args) => args.reduce((acc, val) => acc + val, 0);
const sumKey = sumFn.toString();

const sum = memo(sum);
console.log(sum(1, 2, 3)); // 6
console.log(sum(1, 2, 3)); // 'took from memory!', 6

sumFn = null; // удаляем функцию
console.log(memory[sumKey]); // { "1,2,3": 6 } (данные о sum остались)

Если бы мы использовали в качестве fnKey не строковое представление функции, а саму функцию, то результат был бы тем же: любое значение (в том числе непримитивное), используемое как ключ, приводится к стровокому значению. Будем использовать WeakMap, принимающий объект в качестве ключа и очищающий ячейку хранилища, когда этот объект удаляется (как вручную, так и сборщиком мусора).

let memory = new WeakMap();

const memo = fn => (...args) => {
  if (!memory.has(fn)) {
    memory.set(fn, {});
  }
  const argsKey = args.toString();
  if (memory.get(fn)[argsKey] === void 0) {
     memory.get(fn)[argsKey] = fn(...args);
  } else {
    console.log('took from memory!');
  }
  return memory.get(fn)[argsKey];
};

let sumFn = (...args) => args.reduce((acc, val) => acc + val, 0);

const sum = memo(sumFn);

console.log(sum(1, 2, 3)); // 6
console.log(sum(1, 2, 3)); // 'took from memory!', 6
console.log(memory.get(sumFn)); // { "1,2,3": 6 }
sumFn = null;
console.log(memory.get(sumFn)); // undefined

Гибкая генерация ключей

Что, если аргументами функции fn будут являться объекты, массивы, другие функции?

/* объекты */
let args = [{ foo: 1 }, { bar: 2 }];
console.log(args.toString()); // "[object Object],[object Object]"
/* массивы */
args = [[1], [2, 3]];
console.log(args.toString()); // "1,2,3"
args = [1, 2, 3];
console.log(args.toString()); // "1,2,3"
/* другие функции */
args = [() => 1, () => 2];
console.log(args.toString()); // "() => 1,() => 2"

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

let memory = new WeakMap();

const defaultKeyGenerator = args => args.toString();

const memo = (fn, keyGerenator) => (...args) => {
  if (!memory.has(fn)) {
    memory.set(fn, {});
  }
  const argsKey = keyGerenator ? keyGerenator(args) : defaultKeyGenerator(args);
  if (memory.get(fn)[argsKey] === void 0) {
     memory.get(fn)[argsKey] = fn(...args);
  } else {
    console.log('took from memory!');
  }
  return memory.get(fn)[argsKey];
};

Для объектов можно использовать их JSON-представления.

import equal from 'deep-equal';

const keyGenerator = args => args.map(item => JSON.stringify(item)).join('__');

const deepEqual = memo(equal, arrayKeyGenerator);

const foo = { a: { b: 1 } };
const bar = { a: { b: 1 } };

console.log(deepEqual(foo, bar)); // true
console.log(deepEqual(foo, bar)); // took from memory!, true
console.log(memory.get(equal)); // { '{"a":{"b":1}}__{"a":{"b":1}}': true }

Для массивов можно использовать join(separator) вместо стандартного toString().

Каррирование

Каррирование, карринг (currying) — преобразование функции несокольких аргументов в цепочку функций одного аргумента.

const sum = (x, y) => x + y;
sum(1, 3); // 4

const curriedSum = x => y => x + y;
curriedSum(1)(3); // 4

Каждый вызов преобразованной функции возвращает новую функцию, в которой один параметр фиксируется. Такая функция называется частичной, частично применённой.

const tmp = curriedSum(1); //  y => 1 + y
tmp(3); // 4

Функцию преобразования можно написать следующим образом.

const curry = (fn) => { 
 const curried = (...args) => { 
   if (args.length === fn.length) { 
     return fn(...args); 
   } else { 
     return nextArg => curried(...args, nextArg); 
   } 
 }; 
 return curried; 
}

Или ещё короче.

const curry = fn => curried = (...args) => 
  args.length === fn.length
   ? fn(...args)
   : nextArg => curried(...args, nextArg);

Когда использовать каррирование?

Когда можно удачно переиспользовать частично применённые функции.

const error => type => message = { /* ... */ };

const authError = error("Auth"); // частично применённая функция (фиксируем аргумент)

/* несколько вариантов развития событий */
authError("Incorrect password");
authError("Banned user");

Когда при решении поставленной задачи можно использовать только функции одного аргумента (например, при работе с lambda-функциями).

Thunk

https://en.wikipedia.org/wiki/Thunk

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FunctionalProgramming.md

FunctionalProgramming.md

Объекты и функции первого класса

Функции высшего порядка

Композиция функций

Pipe

Несколько аргументов

Мемоизация

Обобщение для любой функции одного аргумента

Когда использовать мемоизацию?

Несколько аргументов

Отдельное хранилище для каждой функции

Очистка хранилищ

Гибкая генерация ключей

Каррирование

Когда использовать каррирование?

Thunk

Files

FunctionalProgramming.md

Latest commit

History

FunctionalProgramming.md

File metadata and controls

Объекты и функции первого класса

Функции высшего порядка

Композиция функций

Pipe

Несколько аргументов

Мемоизация

Обобщение для любой функции одного аргумента

Когда использовать мемоизацию?

Несколько аргументов

Отдельное хранилище для каждой функции

Очистка хранилищ

Гибкая генерация ключей

Каррирование

Когда использовать каррирование?

Thunk