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

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

В примерах используется JavaScript ES2015). (Почему JavaScript?)

Работа над материалом продолжается; присылайте свои пулл-реквесты в оригинальный репозиторий на английском языке.

В документе используются термины из спецификации Fantasy Land spec по мере необходимости.

Arity (арность)

Количество аргументов функции. От слов унарный, бинарный, тернарный (unary, binary, ternary) и так далее. Это необычное слово, потому что состоит из двух суффиксов: "-ary" и "-ity.". Сложение, к примеру, принимает два аргумента, поэтому это бинарная функция, или функция, у которой арность равна двум. Ино��да используют термин "диадный" (dyadic), если предпочитают греческие корни вместо латинских. Функция, которая принимает произвольное количество аргументов называется, соответственно, вариативной (variadic). Но бинарная функция может принимать два и только два аргумента, без учета каррирования или частичного применения.

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

const arity = sum.length
console.log(arity) // 2

// The arity of sum is 2

Higher-Order Functions (функции высокого порядка)

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

const filter = (predicate, xs) => {
  const result = []
  for (let idx = 0; idx < xs.length; idx++) {
    if (predicate(xs[idx])) {
      result.push(xs[idx])
    }
  }
  return result
}

const is = (type) => (x) => Object(x) instanceof type

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

Partial Application (частичное применение)

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

// Helper to create partially applied functions
// Takes a function and some arguments
const partial = (f, ...args) =>
  // returns a function that takes the rest of the arguments
  (...moreArgs) =>
    // and calls the original function with all of them
    f(...args, ...moreArgs)

// Something to apply
const add3 = (a, b, c) => a + b + c

// Partially applying `2` and `3` to `add3` gives you a one-argument function
const fivePlus = partial(add3, 2, 3) // (c) => 2 + 3 + c

fivePlus(4) // 9

Также в JS можно использовать 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 (автоматическое каррирование)

Трансформация функции, которая принимает несколько аргументов, в новую функцию. Если в новую функцию передать меньшее чем предусмотрено количество аргументов, то она вернет функцию, которая принимает оставшиеся аргументы. Когда функция получает правильное количество аргументов, то она исполняется.

В Underscore, lodash и ramda есть функция curry.

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

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

Дополнительные материалы

• Favoring Curry
• Hey Underscore, You're Doing It Wrong!

Function Composition (композиция функций)

Соединение двух функций для формирования новой функции, в которой вывод первой функции является вводом второй.

const compose = (f, g) => (a) => f(g(a)) // Definition
const floorAndToString = compose((val) => val.toString(), Math.floor) // Usage
floorAndToString(121.212121) // '121'

Purity (чистота)

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

const greet = (name) => 'Hi, ' + name

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

В отличие от:

let greeting

const greet = () => {
  greeting = 'Hi, ' + window.name
}

greet() // "Hi, Brianne"

Side effects (побочные эффекты)

У функции есть побочные эффекты если кроме возврата значения она взаимодействует (читает или пишет) с внешним изменяемым состоянием.

const differentEveryTime = new Date()

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

Idempotent (идемпотентность)

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

f(f(x)) ≍ f(x)

Math.abs(Math.abs(10))

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

Point-Free Style (бесточечная нотация)

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

// Given
const map = (fn) => (list) => list.map(fn)
const add = (a) => (b) => a + b

// Then

// Not points-free - `numbers` is an explicit argument
const incrementAll = (numbers) => map(add(1))(numbers)

// Points-free - The list is an implicit argument
const incrementAll2 = map(add(1))

Функция incrementAll определяет и использует параметр numbers, так что она не использует бесточечную нотацию. incrementAll2 просто комбинирует функции и значения, не упоминая аргументов. Она использует бесточечную нотацию.

Определения с бесточечной нотацией выглядят как обычные присваивания без function или =>.

Predicate (предикат)

Предикат — это функция, которая возвращает true или false в зависимости от переданного знач��ния. Распространенный случай использования предиката — функция обратного вызова (callback) для фильтра массива.

const predicate = (a) => a > 2

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

Categories (категории)

Объекты с функциями, которые подчиняются определенным правилам. Например, моноиды.

Value (значение)

Все, что может быть присвоено переменной.

5
Object.freeze({name: 'John', age: 30}) // The `freeze` function enforces immutability.
;(a) => a
;[1]
undefined

Constant (константа)

Переменная, которую нельзя переназначить после определения.

const five = 5
const john = {name: 'John', age: 30}

Константы обладают референциальной прозрачностью или прозрачностью ссылок (referential transparency). То есть, их можно заменить значениями, которые они представляют, и это не повлияет на результат.

С константами из предыдущего листинга следующее выражение выше всегда будет возвращать true.

john.age + five === ({name: 'John', age: 30}).age + (5)

Functor (функтор)

Объект, который реализует функцию map, которая при проходе по всем значениям в объекте создает новый объект, и подчиняется двум правилам:

// сохраняет нейтральный элемент (identity)
object.map(x => x) === object

и

// поддерживает композицию
object.map(x => f(g(x))) === object.map(g).map(f)

(f, g — произвольные функции)

В JavaScript есть функтор Array, потому что он подчиняется эти правилам:

[1, 2, 3].map(x => x) // = [1, 2, 3]

и

const f = x => x + 1
const g = x => x * 2

;[1, 2, 3].map(x => f(g(x))) // = [3, 5, 7]
;[1, 2, 3].map(g).map(f)     // = [3, 5, 7]

Pointed Functor (указывающий функтор)

Объект с функцией of с любым значением. В ES2015 есть Array.of, что делает массивы указывающим функтором.

Array.of(1) // [1]

Lift

Lifting — это когда значение помещается в объект вроде функтора. Если "поднять" (lift) функцию в аппликативный функтор, то можно заставить ее работать со значениями, которые также присутствуют в функторе.

В некоторых реализациях есть функция lift или liftA2, которые используются для упрощения запуска функций на функторах.

const liftA2 = (f) => (a, b) => a.map(f).ap(b)

const mult = a => b => a * b

const liftedMult = liftA2(mult) // this function now works on functors like array

liftedMult([1, 2], [3]) // [3, 6]
liftA2((a, b) => a + b)([1, 2], [3, 4]) // [4, 5, 5, 6]

Подъем функции с одним аргументом и её применение выполняет то же самое, что и map.

const increment = (x) => x + 1

lift(increment)([2]) // [3]
;[2].map(increment) // [3]

Referential Transparency (прозрачность ссылок)

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

Например, есть функция greet:

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

Любой вызов greet() можно заменить на Hello World!, так что эта функция является прозрачной (referentially transparent).

Lambda (лямбда)

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

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

;(a) => a + 1

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

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

Лямбду можно присвоить переменной.

const add1 = (a) => a + 1

Lambda Calculus (лямбда-исчисление)

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

Lazy evaluation (ленивые вычисления)

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

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

const randIter = rand()
randIter.next() // Каждый вызов дает случайное значение, выражение исполняется при необходимости.

Monoid (моноид)

Объект с функцией, которая "комбинирует" объект с другим объектом того же типа. Простой пример моноида это сложение чисел:

1 + 1 // 2

В этом случае число — это объект, а + это функция.

Должен существовать нейтральный элемент (identity), так, чтобы комбинирование значения с ним не изменяло значение. В случае сложения таким элементом является 0.

1 + 0 // 1

Также необходимо, чтобы группировка операций не влияла на результат (ассоциативность):

1 + (2 + 3) === (1 + 2) + 3 // true

Конкатенация массивов — это тоже моноид:

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

Нейтральный элемент — это пустой массив []

;[1, 2].concat([]) // [1, 2]

Если существуют функции нейтрального элемента и композиции, то функции в целом формируют моноид:

const identity = (a) => a
const compose = (f, g) => (x) => f(g(x))

foo — это любая функция с одним аргументом.

compose(foo, identity) ≍ compose(identity, foo) ≍ foo

Monad (монада)

Монада — это объект с функциями of и chain. chain похож на map, но он производит разложение вложенных объектов в результате.

// Implementation
Array.prototype.chain = function (f) {
  return this.reduce((acc, it) => acc.concat(f(it)), [])
}

// Usage
;Array.of('cat,dog', 'fish,bird').chain((a) => a.split(',')) // ['cat', 'dog', 'fish', 'bird']

// Contrast to map
;Array.of('cat,dog', 'fish,bird').map((a) => a.split(',')) // [['cat', 'dog'], ['fish', 'bird']]

of также известен как return в других функциональных языках.
chain также известен как flatmap и bind в других языках.

Comonad (комонада)

Объект с функциями extract и extend.

const CoIdentity = (v) => ({
  val: v,
  extract () {
    return this.val
  },
  extend (f) {
    return CoIdentity(f(this))
  }
})

Extract берет значение из функтора.

CoIdentity(1).extract() // 1

Extend выполняет функцию на комонаде. Функция должна вернуть тот же тип, что комонада.

CoIdentity(1).extend((co) => co.extract() + 1) // CoIdentity(2)

Applicative Functor (аппликативный функтор)

Объект с функцией ap. ap применяет функцию в объекте к значению в другом объекте того же типа.

// Implementation
Array.prototype.ap = function (xs) {
  return this.reduce((acc, f) => acc.concat(xs.map(f)), [])
}

// Example usage
;[(a) => a + 1].ap([1]) // [2]

Это полезно, когда есть два объекта, и нужно применить бинарную операцию на их содержимом.

// Arrays that you want to combine
const arg1 = [1, 3]
const arg2 = [4, 5]

// combining function - must be curried for this to work
const add = (x) => (y) => x + y

const partiallyAppliedAdds = [add].ap(arg1) // [(y) => 1 + y, (y) => 3 + y]

В итоге получим массив функций, которые можно вызвать с ap чтобы получить результат:

partiallyAppliedAdds.ap(arg2) // [5, 6, 7, 8]

Morphism (морфизм)

Функция трансформации.

Endomorphism (эндоморфизм)

Функция, у которой ввод и вывод — одного типа.

// uppercase :: String -> String
const uppercase = (str) => str.toUpperCase()

// decrement :: Number -> Number
const decrement = (x) => x - 1

Isomorphism (изоморфизм)

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

Например, двумерные координаты можно хранить в массиве [2,3] или объекте {x: 2, y: 3}.

// Providing functions to convert in both directions makes them isomorphic.
const pairToCoords = (pair) => ({x: pair[0], y: pair[1]})

const coordsToPair = (coords) => [coords.x, coords.y]

coordsToPair(pairToCoords([1, 2])) // [1, 2]

pairToCoords(coordsToPair({x: 1, y: 2})) // {x: 1, y: 2}

Setoid

Объект, у которого есть функция equals, которую можно использовать для сравнения объектов одного типа.

Сделать массив сетоидом:

Array.prototype.equals = (arr) => {
  const len = this.length
  if (len !== arr.length) {
    return false
  }
  for (let i = 0; i < len; i++) {
    if (this[i] !== arr[i]) {
      return false
    }
  }
  return true
}

;[1, 2].equals([1, 2]) // true
;[1, 2].equals([0]) // false

Semigroup (полугруппа)

Объект с функцией concat, которая комбинирует его с другим объектом того же типа.

;[1].concat([2]) // [1, 2]

Foldable

Объект, в котором есть функция reduce, которая трансформирует объект в другой тип.

const sum = (list) => list.reduce((acc, val) => acc + val, 0)
sum([1, 2, 3]) // 6

Type Signatures (сигнатуры типа)

Часто функции в JavaScript содержат комментарии с указанием типов их аргументов и возвращаемых значений. В сообществе существуют разные подходы, но они все схожи:

// functionName :: firstArgType -> secondArgType -> returnType

// add :: Number -> Number -> Number
const add = (x) => (y) => x + y

// increment :: Number -> Number
const increment = (x) => x + 1

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

// call :: (a -> b) -> a -> b
const call = (f) => (x) => f(x)

Символы a, b, c, d показывают, что аргументы могут быть любого типа. Следующая версия функции map принимает:

1. функцию, которая трансформирует значение типа a в другой тип b
2. массив значений типа a,

и возвращает массив значений типа b.

// map :: (a -> b) -> [a] -> [b]
const map = (f) => (list) => list.map(f)

Дополнительные материалы

• Ramda's type signatures
• Mostly Adequate Guide
• What is Hindley-Milner? на Stack Overflow

Union type (тип-объединение)

Комбинация двух типов в один, новый тип.

В JavaScript нет статических типов, но давайте представим, что мы изобрели тип NumOrString, который является сложением String и Number.

Операция + в JavaScript работает со строками и числами, так что можно использовать наш новый тип для описания его ввода и вывода:

// add :: (NumOrString, NumOrString) -> NumOrString
const add = (a, b) => a + b

add(1, 2) // Возвращает число 3
add('Foo', 2) // Возвращает строку "Foo2"
add('Foo', 'Bar') // Возвращает строку "FooBar"

Тип-объединение также известно как алгебраический тип, размеченное объединение и тип-сумма.

Существует пара библиотек в JavaScript для определения и использования таких типов.

Product type (тип-произведение)

Тип-произведение комбинирует типы таким способом, который вам скорее всего знаком:

// point :: (Number, Number) -> {x: Number, y: Number}
const point = (x, y) => ({x: x, y: y})

Его называют произведением, потому что возможное значение структуры данных это произведение (product) разных значений.

См. также: теория множеств.

Option (опцион)

Тип-объединение с двумя случаями: Some и None. Полезно для композиции функций, которые могут не возвращать значения.

// Naive definition

const Some = (v) => ({
  val: v,
  map (f) {
    return Some(f(this.val))
  },
  chain (f) {
    return f(this.val)
  }
})

const None = () => ({
  map (f) {
    return this
  },
  chain (f) {
    return this
  }
})

// maybeProp :: (String, {a}) -> Option a
const maybeProp = (key, obj) => typeof obj[key] === 'undefined' ? None() : Some(obj[key])

Используйте chain для построения последовательности функций, которые возвращают Option.

// getItem :: Cart -> Option CartItem
const getItem = (cart) => maybeProp('item', cart)

// getPrice :: Item -> Option Number
const getPrice = (item) => maybeProp('price', item)

// getNestedPrice :: cart -> Option a
const getNestedPrice = (cart) => getItem(obj).chain(getPrice)

getNestedPrice({}) // None()
getNestedPrice({item: {foo: 1}}) // None()
getNestedPrice({item: {price: 9.99}}) // Some(9.99)

Option также известен как Maybe. Some иногда называют Just. None иногда называют Nothing.

Библиотеки функционального программирования в JavaScript

• Ramda
• Folktale
• lodash
• Underscore.js
• Lazy.js
• maryamyriameliamurphies.js
• Haskell in ES6