This is an abridged and modified Russian translation of Functional Programming Jargon with examples in Haskell. Some code examples borrowed from Turkish translation.

Эта статья - сокращенный перевод и переработка публикации Functional Programming Jargon с примерами на Нaskell, часть из которых взята из турецкой версии статьи. Перевод оригинальной статьи с примерами на JavaScript выполнен здесь.

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

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

Содержание

• 1. Функции
  • Определение функции
  • Операции с фукциями
    • Композиция функций
    • Point-free стиль записи
    • Лямбда-функция
    • Лямбда-исчисление
    • Функция высшего порядка (ФВП)
  • Не совсем "правильные" функции
    • Частичная функция
    • Чистота и побочные эффекты
      • Чистота
      • Побочные эффекты
  • Аргументы функции и их обработка
    • Арность функции
    • Каррирование
    • Частичное применение
  • Свойства и виды функций
    • Индемпотентность
    • Предикат
    • Замыкание
  • Аннотация типа
• 2. Типы
  • Тип (данных)
  • Алгебраический тип данных
    • Тип-сумма (sum type)
    • Тип-произведение (product type)
• 3. Общие понятия
  • Cсылочная прозрачность (referential transparency)
  • Эквациональное рассуждение (equational reasoning)
  • Выражение
  • Значение
  • Ленивые вычисления
• Литература
  • Другие англоязычные словари и глоссарии
  • Книги и сайты на русском языке
• Развитие словаря

1. Функции

Определение функции

Function

Функция f :: X -> Y каждому элементу x типа X сопоставляет элемент f x типа Y.

x называется аргументом функции, а f x - значением функции.

Функции, которые соответствуют данному определению, являются:

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

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

Примечание: в программировании функцией может называться и та последовательность операций, которая приводит к побочным эффектам (записи на диск, проведению ввода-вывода, изменению глобальных переменных). Чтобы отличить их от функций в данном определении, такие операции можно называть процедурами.

Операции с фукциями

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

Создание из двух функций f(x) и g(x) третьей функции h, результатом которой является применение функции f к g(x): h(x) = f(g(x)).

В Haskell композиция функций производится оператором . (точка). Такая запись в point-free форме более лаконична, чем запись с аргументом:

-- Предположим, у нас определены две функции 
-- со следующими подписями
even :: Int -> Bool
not :: Bool -> Bool

-- Давайте сдлаем новую функцию, которая проверяет 
-- является ли значение нечетным
myOdd :: Int -> Bool
myOdd x = not (even x)

-- ... или сделаем то же самое с использованием оператора .
myOdd :: Int -> Bool
myOdd = not . even

пример полностью

-- Функция desort создается путем комбинации 
-- сортировки и перечисления списка в обратном порядке
desort = reverse . sort

источник

Point-free стиль записи

Point-free style

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

Сравните:

sum = foldr (+) 0

и

sum' xs = foldr (+) 0 xs

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

Point-free стиль также иногда называется бесточечный стиль.

In Haskell you can simplify function definitions by η-reducing them. For example, instead of writing:

f x = (some expresion) x

you can simply write

f = (some expression)

<источник>

Лямбда-функция

Lambda

Неименованная, анонимная функция.

\x -> x + 1

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

Prelude> map (\x -> x + 1) [1..4]
[2,3,4,5]

-- хотя этот пример можно записать и без лямбды
map (+1) [1..4]

Название дано по 11-й букве греческого алфавита λ (лямбда).

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

Для того, чтобы определить функцию, не обязательно задавать её имя. Для этого можно воспользоваться лямбда-абстракцией \x -> x + 1. Такие функции будем называть анонимными.

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

Lambda calculus

Раздел математики, в котором формализовано и анализируется понятие вычислимости.

Лямбда-исчисление также можно рассматривать как компактный универсальный язык программирования, c помощью которого может быть определена и рассчитана любая вычислимая функция. [1]

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

Ccылки (англ.яз.)

1. Raul Rojas. A Tutorial Introduction to the Lambda Calculus
2. Ben Lynn. Lambda Calculus

Ccылки (рус.яз.)

3. Денис Москвин. Лямбда-исчисление
4. Антон Холомьёв. Лямбда-исчисление

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

Higher-Order Function (HOF)

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

Prelude> let add3 a = a + 3
Prelude> map add3 [1..4]
[4,5,6,7]

Prelude> filter (<4) [1..10]
[1,2,3]

Не совсем "правильные" функции

Частичная функция

Partial function

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

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

Пример запроса несуществующего элемента списка:

[1,2,3] !! 5

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

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

Подробнее см. например здесь.

Чистота и побочные эффекты

Чистота

Purity

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

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

Побочные эффекты

Side effects

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

Таких фукнций на Haskell нет, примеры на JavaScript:

const differentEveryTime = new Date()

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

Аргументы функции и их обработка

Арность функции

Arity

Количество аргументов, которое принимает функция (унарная, бинарная и т.д.)

Prelude> let sum a b = a + b
Prelude> :t sum
sum :: Num a => a -> a -> a

-- Арность функции sum равна 2 

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

Currying

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

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

В примере ниже функция sum обрабатывает кортеж из двух значений (a, b). Функция curry преобразует функцию sum в curriedSum, которая последовательно принимает два аргумента a и b.

Prelude> let sum (a, b) = a + b
Prelude> let curriedSum = curry sum
Prelude> curriedSum 40 2
42

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

Partial Application

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

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

-- Создаем функцию сложения двух элементов
Prelude> let add x y = x + y

-- Создадим функцию для увеличения аргумента на единицу.
-- Частично применим функцию add к значению 1.
-- В результате получилась новая функция,
-- которой мы присвоили имя inc
Prelude> let inc = add 1
Prelude> inc 8
Prelude> 9 

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

Ссылки

• What is the difference between currying and partial application?

Свойства и виды функций

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

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

Indepotent

Функция является идемпотентной, если ее повторное применение не влияет на исходный результат:

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

Prelude> abs (abs (-1))
1

Prelude Data.List> sort (sort [1,4,3,1,5])
[1,1,3,4,5]

Предикат

Predicate

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

Prelude> let predThree a = a < 3
Prelude> filter predThree [1..10]
[1,2]

Замыкание

Closure

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

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

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

Вымученный пример замыкания на Haskell:

-- Переменная x не является аргументом лямбда-функции, 
-- но доступна внутри тела функции f
f x = (\y -> x + y)

-- привычная запись на Haskell
f x y = x + y

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

Аннотация типа

Type signatures

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

В Haskell подпись типа может задаваться напрямую в коде. Например, после определения inc :: Int -> Int компилятор будет ожидать, что под именем inc будет определена функция, которая принимает значение типа Int и выдает результат также типа Int. Если под именем inc будет определна функция с другим поведением, компилятор выдаст ошибку.

В отсутствие заданой подписи типа компилятор сам выводит ее наиболее общий вид:

Prelude> inc x = x + 1
Prelude> :t inc
inc :: Num a => a -> a

inc :: Num a => a -> a - это подпись, выведенная компилятором. Она говорит о том, что имя inc - это функция, которая принимает значение некоторого типа а и выдает значение того же типа a, при этом сам тип а - принадлежит классу типов Num, который объединяет типы, выражающие числа.

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

2. Типы

Тип (данных)

Тип представляет собой набор возможных значений. Например, у типа Bool есть два значения True и False. Тип Int включает в себя все целочисленные значения.

Типы бывают простые и составные. Например, мы можем создать новый составной тип данных Point,объявив, что он состоит из двух значений типа Float.

data Point = Point Float Float

Термины тип и тип данных взаимозаменяемы.

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

Цитата (источник):

... why we should care about types at all: what are they even for? At the lowest level, a computer is concerned with bytes, with barely any additional structure. What a type system gives us is abstraction. A type adds meaning to plain bytes: it lets us say “these bytes are text”, “those bytes are an airline reservation”, and so on. Usually, a type system goes beyond this to prevent us from accidentally mixing types up: for example, a type system usually won't let us treat a hotel reservation as a car rental receipt.

Ссылки

• What do haskell data constructors construct?
• What is Hindley-Milner?

Алгебраический тип данных

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

Тип-сумма (sum type)

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

Булевский тип данных "правда-ложь" является самым простым типом-суммой:

data Bool = False | True

Три цвета светофора также тип-сумма:

data TrafficLight = Red | Yellow | Green

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

data Move = Stop | Ahead Int | Back Int

Шаги робота теперь можно описать с помощью списка типа [Move], например, [Ahead 1, Stop, Stop, Back -2] (шаг вперед, два назад).

Типы Maybe и Either, использующиеся для управлениями эффектами вычислений, также являются типами-суммой.

Тип-произведение (product type)

Тип-произведение объединяет элементы таким образом, что количество новых значений представляет собой произведение возможных количеств входящих значений.

В большинстве языков программирования есть тип кортеж (tuple), который является самым простым типом-произведением. Например, кортеж из трех булевых значений типа (Bool, Bool, Bool) имеет 2*2*2 = 8 значений.

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

data Person = Person {name:String , age::Int}
Person "LittleBaby" 2

Место точки на плоскости соcтоит их двух координат, которые можно выразить типом-произведением двух значений типа Float:

data Position = Position Float Float
Position 1.5 2.8

Ссылки:

• Теория множеств
• Бывают ли алгебраические типы данных вне типа-суммы и произведения?

3. Общие понятия

Cсылочная прозрачность (referential transparency)

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

Cсылочная прозрачность упрощает понимание и изменение кода программ.

Ссылки:

• Referential Transparency - UseNet

Эквациональное рассуждение (equational reasoning)

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

Упорощенно, эквациональное рассуждение - это процесс интерпретации или доказательства свойств программы путем подстановки равных выражений.

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

Ссылки:

• Haskell for all - Equational reasoning

Выражение

Expression

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

Примеры выражений: 2+3, fst ("this_"++"a", "that_"++"b"), fmap (+1) (Just 5).

Значение

Value

1. Результат вычисления выражения.

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

Примеры значений: 5, "this_a", Just 6.

Ленивые вычисления

Lazy evaluation

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

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

Prelude> let xs = [1..]
Prelude> take 5 xs
[1,2,3,4,5]

Литература

Другие англоязычные словари и глоссарии

• http://degoes.net/articles/fp-glossary
• https://blog.lelonek.me/functional-programming-dictionary-with-ruby-38e39b3ddcba
• https://wiki.haskell.org/Category:Glossary

Книги и сайты на русском языке

• https://anton-k.github.io/ru-haskell-book/book/home.html
• https://www.ibm.com/developerworks/ru/library/l-haskell/index.html?ca=drs-
• http://fprog.ru/2009/issue3/eugene-kirpichov-elements-of-functional-languages/
• https://www.ohaskell.guide
• https://ruhaskell.org

Выступления

I've been asked about the famous talk of Rich Hickey "Simple made Easy" (aka "Simplicity Matters").

Absolutely a must-watch for every developer who wants to call himself a qualified senior or architect.https://t.co/ouFIdjCOxC https://t.co/HFAZkoXx0s

— Alexander Granin (@graninas) January 15, 2020

<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

(infoq transcript)

Развитие словаря

Что можно сделать в этом словаре лучше? Конечно, это решать читателям. Вы можете дать комментарий в issues этого проекта, или написать переводчику.