Жаргон ФП: словарь терминов с примерами на JavaScript

Функциональное программирование обросло собственным словарём: функтор, монада, катаморфизм, линза. Слова знакомые, но значения у них точные. Без них чужая статья про ФП превращается в шифр, а код на fp-ts или Effect читается как заклинание.

Этот урок, словарь. В нём собраны термины ФП с короткими примерами на JavaScript (ES2015), от арности и замыкания до свободных монад и оптик. Порядок примерно от простого к сложному, но читать подряд не обязательно. Возвращайся к нужному термину, когда встретишь его в коде, статье или на собеседовании.

Словарь опирается на Functional Programming Jargon Hemanth HM и его русский перевод на Habr. Примеры намеренно короткие: это иллюстрации к определению, а не готовый модуль. Некоторые из них используют условные имена (Some, None, R, _, readFileAsync), чтобы показать форму идеи. Часть терминов уже разобрана в уроках курса, ссылки стоят рядом.

Термины из Fantasy Land spec используются там, где это уместно.

Основы функций

Arity · Арность

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

const sum = (a, b) => a + b
// Арность sum равна 2 (бинарный)
const inc = a => a + 1
// Арность inc равна 1 (унарный)
const zero = () => 0
// Арность zero равна 0 (нульарный)

Higher-Order Function (HOF) · Функция более высокого порядка

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

const filter = (predicate, xs) => xs.filter(predicate)
const is = (type) => (x) => Object(x) instanceof type

filter(is(Number), [0, '1', 2, null]) // [0, 2]

Closure · Замыкание

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

const addTo = x => y => x + y
const addToFive = addTo(5)
addToFive(3) // => 8

Здесь x сохраняется в замыкании addToFive со значением 5. Потом addToFive вызывается с y и складывает оба значения.

Partial Application · Частичное применение

Частичное применение создаёт новую функцию, заранее подставив часть аргументов исходной.

// Утилита для создания частично применённых функций.
// Принимает функцию и аргументы
const partial = (f, ...args) =>
  // Возвращает функцию, которая принимает остальные аргументы
  (...moreArgs) =>
    // и вызывает оригинальную функцию со всеми аргументами
    f(...args, ...moreArgs)

// Функция, к которой применяем аргументы
const add3 = (a, b, c) => a + b + c

// Частичное применение `2` и `3` к `add3` даёт функцию с одним параметром
const fivePlus = partial(add3, 2, 3) // (c) => 2 + 3 + c

fivePlus(4) // 9

В JavaScript для частичного применения есть и Function.prototype.bind:

const add1More = add3.bind(null, 2, 3) // (c) => 2 + 3 + c

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

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

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

const sum = (a, b) => a + b

const curriedSum = (a) => (b) => a + b

curriedSum(40)(2) // 42

const add2 = curriedSum(2) // (b) => 2 + b

add2(10) // 12

Auto Currying · Автокаррирование

Автокаррирование это каррирование по факту: если передать меньше аргументов, чем нужно, функция вернёт новую функцию и будет ждать остальные. Вычисление происходит только после последнего аргумента. curry в Lodash и Ramda работает именно так.

const add = (x, y) => x + y

const curriedAdd = _.curry(add)
curriedAdd(1, 2) // 3
curriedAdd(1) // (y) => 1 + y
curriedAdd(1)(2) // 3

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

Композиция склеивает две функции в одну: результат первой уходит аргументом во вторую. Это одна из главных операций ФП.

const compose = (f, g) => (a) => f(g(a)) // Определение
const floorAndToString = compose((val) => val.toString(), Math.floor) // Использование
floorAndToString(121.212121) // '121'

Подробнее про pipe и compose есть в уроке 05.

Continuation · Продолжение

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

const printAsString = (num) => console.log(`Given ${num}`)

const addOneAndContinue = (num, cc) => {
  const result = num + 1
  cc(result)
}

addOneAndContinue(2, printAsString) // 'Given 3'

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

const continueProgramWith = (data) => {
  // Продолжение выполнения программы с данными
}

readFileAsync('path/to/file', (err, response) => {
  if (err) {
    // Обработка ошибки
    return
  }
  // Передача ответа
  continueProgramWith(response)
})

Тема продолжений разобрана глубже в отдельном уроке.

Lambda · Лямбда

Лямбда это анонимная функция, с которой можно обращаться как со значением.

;(function (a) {
  return a + 1
})

;(a) => a + 1

Лямбды часто передают аргументом в функции более высокого порядка:

;[1, 2].map((a) => a + 1) // [2, 3]

И присваивают переменной:

const add1 = (a) => a + 1

Lambda Calculus · Лямбда-исчисление

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

Functional Combinator · Функциональный комбинатор

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

// Комбинатор "C" принимает каррированную двуаргументную функцию и возвращает
// функцию, которая вызывает оригинальную функцию с аргументами в обратном порядке
const C = (f) => (a) => (b) => f(b)(a)

const divide = (a) => (b) => a / b

const divideBy = C(divide)

const divBy10 = divideBy(10)

divBy10(30) // => 3

Больше комбинаторов в списке функциональных комбинаторов на JavaScript.

Predicate · Предикат

Предикат возвращает true или false для переданного значения. Типичное место работы предиката это колбэк фильтра.

const predicate = (a) => a > 2

;[1, 2, 3, 4].filter(predicate) // [3, 4]

Contract · Контракт

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

// Определяем контракт: int -> boolean
const contract = (input) => {
  if (typeof input === 'number') return true
  throw new Error('Contract violated: expected int -> boolean')
}

const addOne = (num) => contract(num) && num + 1

addOne(2) // 3
addOne('some string') // контракт нарушен: ожидалось int -> boolean

Вычисление, эффекты и чистота

IO

IO это чистая структура данных, которая описывает побочный эффект, но не выполняет его. Операция заворачивается в thunk, и эффект запускается только явным .run(). До запуска с IO можно делать map и chain, как с любым контейнером, и собирать из чистых значений цепочки.

const IO = (run) => ({
  run,
  map: (f) => IO(() => f(run())),
  chain: (f) => IO(() => f(run()).run())
})

// Чистое описание, пока ничего не выполняется
const readTimestamp = IO(() => Date.now())
const formatted = readTimestamp.map((ts) => new Date(ts).toISOString())

// Побочный эффект выполняется только после вызова .run()
formatted.run()

Та же идея в масштабе приложения разобрана в уроке про системы эффектов.

Trampoline · Трамплин

Трамплин позволяет глубокой или взаимно рекурсивной функции работать без переполнения стека. В среде без оптимизации хвостовых вызовов (TCO) рекурсивный шаг возвращает thunk вместо прямого вызова. Трамплин крутит while и разматывает thunk за thunk до финального значения.

const trampoline = (fn) => (...args) => {
  let result = fn(...args)
  while (typeof result === 'function') {
    result = result()
  }
  return result
}

// Без трамплина sumBelow(1000000) выбрасывает "Maximum call stack size exceeded"
const sumBelow = (n, acc = 0) =>
  n === 0
    ? acc
    : () => sumBelow(n - 1, acc + n) // возвращает thunk вместо прямого вызова

const safeSum = trampoline(sumBelow)
safeSum(1000000) // 500000500000

Thunk

Thunk это функция без аргументов, которая оборачивает выражение и откладывает вычисление до вызова. На thunk держатся ленивые вычисления, трамплины и отложенные побочные эффекты.

// Жадное (eager) вычисление выполняется сразу:
// const data = expensiveCalculation()

// Thunk оборачивает выражение в функцию, откладывая выполнение:
const thunk = () => 42 * 2

// Выражение вычисляется только при явном вызове:
thunk() // 84

Algebraic Effects · Алгебраические эффекты

Алгебраические эффекты разделяют выполнение эффекта и его обработку. Функция «выполняет» операцию, например читает состояние, запрашивает конфигурацию или пишет лог. Внешний обработчик перехватывает операцию и решает, что делать: вернуть результат и продолжить вычисление или прервать его. Так исключения, async/await и генераторы оказываются частными случаями одной идеи, и можно обойтись без стека трансформеров монад.

// Генераторы моделируют ограниченные продолжения и алгебраические эффекты:
const perform = (effect) => ({ [Symbol.for('effect')]: true, effect })

// Программа выполняет эффекты, не зная, кто их обрабатывает:
function * fetchUserProfile (userId) {
  const config = yield perform({ type: 'ask_config' })
  yield perform({ type: 'log', message: `Fetching user ${userId} from ${config.apiUrl}` })
  return { id: userId, name: 'Alice' }
}

// Обработчик эффектов перехватывает их и продолжает вычисление:
const handle = (generator, handlers) => {
  const iter = generator()
  const step = (value) => {
    const { done, value: yielded } = iter.next(value)
    if (done) return yielded
    if (yielded && yielded[Symbol.for('effect')]) {
      const { type } = yielded.effect
      if (handlers[type]) {
        return handlers[type](yielded.effect, (resumeVal) => step(resumeVal))
      }
    }
    return step(yielded)
  }
  return step()
}

// Запуск с интерпретатором и обработчиком:
handle(
  () => fetchUserProfile(42),
  {
    ask_config: (effect, resume) => resume({ apiUrl: 'https://api.test.local' }),
    log: (effect, resume) => {
      console.log(effect.message)
      return resume()
    }
  }
)

Pure Function · Чистая функция

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

const greet = (name) => `Hi, ${name}`

greet('Brianne') // 'Hi, Brianne'

Примеры нечистых функций:

window.name = 'Brianne'

const greet = () => `Hi, ${window.name}`

greet() // "Hi, Brianne"

Здесь результат зависит от данных за пределами функции.

let greeting

const greet = (name) => {
  greeting = `Hi, ${name}`
}

greet('Brianne')
greeting // "Hi, Brianne"

Здесь функция меняет состояние, которое ей не принадлежит.

Side effects · Побочные эффекты

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

const differentEveryTime = new Date()

console.log('IO is a side effect!')

Idempotence · Идемпотентность

Идемпотентная операция даёт один и тот же результат при повторном применении.

Math.abs(Math.abs(10))

sort(sort(sort([2, 1])))

Point-Free Style · Бесточечный стиль

Бесточечный стиль (point-free, tacit programming) это определение функции без явного упоминания её аргументов. Обычно он требует каррирования и функций более высокого порядка. В русских переводах встречается и название «беспараметрический стиль».

// Дано
const map = (fn) => (list) => list.map(fn)
const add = (a) => (b) => a + b

// Не бесточечный стиль: `numbers` это явный аргумент
const incrementAll = (numbers) => map(add(1))(numbers)

// Бесточечный стиль: `list` это неявный аргумент
const incrementAll2 = map(add(1))

Такие определения выглядят как обычные присваивания без function и =>. Бесточечный стиль не всегда лучше: в сложных случаях функцию без явных аргументов труднее читать.

Referential Transparency · Ссылочная прозрачность

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

const greet = () => 'Hello World!'

Любой вызов greet() можно заменить на 'Hello World!', поэтому greet обладает ссылочной прозрачностью. Свойство нарушилось бы, если бы greet зависела от внешнего состояния: конфигурации, базы данных или текущего времени. См. также чистые функции и рассуждение на основе равенств.

Equational Reasoning · Рассуждение на основе равенств

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

const grainToDogs = compose(chickenIntoDogs, grainIntoChicken)
const grainToCats = compose(dogsIntoCats, grainToDogs)

Если chickenIntoDogs и grainIntoChicken чистые, то и композиция чистая. Этот подход развивается дальше, когда известны свойства функций: ассоциативность, коммутативность, идемпотентность.

Memoization · Мемоизация

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

const memoize = (fn) => {
  const cache = new Map()
  return (arg) => {
    if (!cache.has(arg)) {
      cache.set(arg, fn(arg))
    }
    return cache.get(arg)
  }
}

const factorial = memoize((n) => (n <= 1 ? 1 : n * factorial(n - 1)))
factorial(5) // вычислено: 120
factorial(5) // извлечено из кэша: 120

Lazy evaluation · Ленивое вычисление

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

const rand = function * () {
  while (1 < 2) {
    yield Math.random()
  }
}

const randIter = rand()
randIter.next() // каждое выполнение даёт произвольное значение