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

в 9:49, , рубрики: монада, моноид, Программирование, ФП, функциональное программирование

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

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

В примерах используется 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

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

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)

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

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

Автор: freetonik

Источник

Поделиться новостью

* - обязательные к заполнению поля