Функциональное программирование
Введение
Функциональное программирование (ФП, FP) - это парадигма программирования, в которой вычисления осуществляются в виде вычисления значений функций и избегается изменение состояния и использование изменяемых данных.
ФП имеет ряд преимуществ, таких как:
- Легкость в написании и понимании кода, так как функции в ФП обычно короткие и простые.
- Легкость в отладке, так как функции не имеют состояния и не изменяют данные.
- Легкость в параллельном программировании, по той же причине.
В этом разделе мы рассмотрим основные концепции и принципы функционального программирования, такие как чистые функции, рекурсия, функции высшего порядка и другое.
Рассмотрим основное отличие императивного программирования - IP от функционального на примере вычислении суммы коллекции чисел.
В императивном подходе сумма чисел вычислялась бы так:
def sum(ints: List[Int]): Int =
var sum = 0
for i <- ints do sum += i
sum
sum(List(1, 2, 3))
// 6
Этот код изменяет поле var
в цикле for
- использует изменяемое состояние.
Подход ФП может выглядеть так:
def sum(xs: List[Int]): Int =
def loop(xs: List[Int], acc: Int): Int =
xs match
case Nil => acc
case x :: tail => loop(tail, acc + x)
loop(xs, 0)
sum(List(1, 2, 3))
// 6
В функциональном подходе не используется изменяемое состояние.
Пошаговый алгоритм вычисления следующий:
- Внутри функции
sum
определена вспомогательная функцияloop
, которая принимает на вход список целых чиселxs
и аккумуляторacc
и возвращает сумму элементов списка. - В функции
loop
используется сопоставление с шаблоном, проверяющее, является ли списокxs
пустым. Если список пуст, то функция возвращает аккумуляторacc
, в котором хранится сумма чисел. - Если список не пуст, то функция
loop
рекурсивно вызывает саму себя, передавая в качестве аргументов хвост списка и увеличивая аккумулятор на значение заглавного элемента.
Таким образом, функция sum
вычисляет сумму элементов списка целых чисел,
используя рекурсивный подход и неизменяемые переменные.
В функциональном программировании следует придерживаться следующих правил:
- не использовать
null
- использовать только чистые функции
- использовать только неизменяемые (
val
) переменные - не использовать class-ы, инкапсулирующие данные и поведение
- использовать
if
только в качестве выражений, а не операторов
Чистая функция
Чистая функция означает, что вывод функции зависит только от ее входных параметров и она не имеет побочных эффектов. Функция имеет побочный эффект, если она делает что-то кроме простого возврата результата, например:
- Изменение переменной
- Изменение структуры данных на месте
- Установка поля на объекте
- Генерация исключения или остановка с ошибкой
- Печать на консоль или чтение пользовательского ввода
- Чтение или запись в файл
- Рисование на экране
Более формальное определение чистой функции
Функция f
с типом ввода A
и типом вывода B
(записанная на Scala как один тип: A => B
) —
это вычисление, которое связывает каждое значение a
типа A
ровно с одним значением b
типа B
,
которое определено исключительно по значению a
.
Любое изменение состояния внутреннего или внешнего процесса не имеет отношения к вычислению результата f(a)
.
Ссылочная прозрачность
Ссылочная прозрачность - это свойство выражений, при котором их можно заменять соответствующими значениями без изменения поведения программы. Если выражение является ссылочно прозрачным, то результат его вычисления будет одним и тем же для одних и тех же аргументов. Функции, обладающие этим свойством, называют чистыми функциями. В математике все функции считаются ссылочно прозрачными, однако в программировании это не всегда так. Ссылочная прозрачность важна, поскольку она позволяет программисту и компилятору рассуждать о поведении программы как о системе перезаписи, что может помочь в проверке правильности, упрощении алгоритма, модификации кода без его нарушения или оптимизации кода.
Редукция
Процесс сведения выражения к «простейшей эквивалентной форме» называется редукцией или сокращением (reduction).
Можно кратко оценить суть сокращения, рассмотрев вычисление выражения square(3 + 4)
.
Предположим, знак =>
означает «сводится к».
Одна из возможных последовательностей редукции выглядит следующим образом: square(3 + 4) => square(7) => 7 * 7 => 49
.
Выражение 49
не может быть сокращено дальше.
Однако существует другая возможная последовательность сокращения: square(3 + 4) => (3 + 4) * (3 + 4) => 7 * (3 + 4) => 7 * 7 => 49
.
Выражение называется каноническим (или в нормальной форме), если его нельзя сократить.
Рассмотрим пример:
Представьте себе язык выражений для представления целых чисел, определяемый правилами синтаксиса: (i)
zero
— это выражение; (ii) еслиe
— это выражение, то также являются выражениями(succ e)
и(pred e)
. Разработчик сокращает выражения на этом языке, многократно применяя следующие правила до тех пор, пока это возможно:
(succ(pred e)) => e
(pred(succ e)) => e
Упростите выражение
(succ(pred(succ(pred(pred zero)))))
.
Алгоритм упрощения:
- ищем первую последовательность
succ -> pred
илиpred -> succ
- если такой последовательности нет, то редукция завершена
- если последовательность
succ -> pred
илиsucc -> pred
найдена, то сокращаем её - возвращаемся в пункт 1
Результат упрощения:
(succ(pred(succ(pred(pred zero))))) => (succ(pred(pred zero))) => pred zero
Реализация алгоритма:
enum Expr:
self =>
case Zero
case Succ(expr: Expr)
case Pred(expr: Expr)
def normalize: Expr =
self match
case Succ(Pred(e)) => e.normalize
case Pred(Succ(e)) => e.normalize
case Succ(e) => Succ(e.normalize)
case Pred(e) => Pred(e.normalize)
case _ => self
import Expr.*
val expr = Succ(Pred(Succ(Pred(Pred(Zero)))))
expr.normalize // Pred(Zero)
Вот несколько причин, почему редукция применима в функциональном программировании:
- Чистые функции: Функциональный язык программирования опирается на чистые функции, которые не имеют побочных эффектов и возвращают одно и то же значение при одинаковых входных данных. Это делает возможным использование редукции, потому что каждая функция может быть сведена к своему значению независимо от контекста.
- Рефакторинг и оптимизация: Благодаря тому, что функции могут быть сведены к своим значениям, код становится легче рефакторить и оптимизировать. Например, можно заменить сложные выражения простыми значениями, не изменяя поведение программы.
- Простота анализа и проверки корректности: Поскольку каждое выражение может быть сведено к своему значению, анализ программы становится проще. Можно проверить корректность программы, рассматривая каждую функцию отдельно и убеждаясь, что она возвращает правильное значение.
Функция высшего порядка
Функция высшего порядка или Функция первого класса (Higher-Order Function - HOF) часто определяется как функция, которая
- принимает другие функции в качестве входных параметров или
- возвращает функцию в качестве результата.
Рассмотрим пример: допустим, необходимо написать функцию formatResult
,
вычисляющую модуль числа или его факториал и выводящую результат.
def abs(n: Int): Int =
if n < 0 then -n
else n
def factorial(n: Int): Int =
@annotation.tailrec
def go(n: Int, acc: Int): Int =
if n <= 0 then acc
else go(n - 1, n * acc)
go(n, 1)
def formatResult(name: String, n: Int, f: Int => Int): String =
val msg = "The %s of %d is %d."
msg.format(name, n, f(n))
Функция formatResult
— это функция высшего порядка (HOF), которая принимает другую функцию, называемую f
.
f
присваивается тип, как и любому другому параметру.
Её тип, Int => Int
, указывает на то, что f
ожидает целочисленный аргумент и возвращает целое число.
Функция abs
соответствует этому типу. Она принимает Int
и возвращает Int
.
Точно так же factorial
соответствует типу Int => Int
.
Поэтому можно передать abs
или factorial
в качестве аргумента f
в formatResult
:
formatResult("absolute value", -42, abs)
// "The absolute value of -42 is 42."
formatResult("factorial", 7, factorial)
// "The factorial of 7 is 5040."
Анонимная функция
При использовании HOF часто удобно иметь возможность вызывать эти функции с помощью анонимных функций или функциональных литералов, вместо того, чтобы предоставлять какую-либо существующую именованную функцию.
Лямбда-исчисление (также записываемое как λ-исчисление) - это формальная система в математической логике для выражения вычислений, основанных на абстракции функций и применении с использованием привязки переменных и подстановки.
Пример использования анонимных функций:
def findFirst[A](as: Array[A], p: A => Boolean): Int =
@annotation.tailrec
def loop(n: Int): Int =
if n >= as.length then -1
else if p(as(n)) then n
else loop(n + 1)
loop(0)
findFirst(Array(7, 9, 13), (x: Int) => x == 9)
// 1
Синтаксис (x: Int) => x == 9
представляет собой литерал функции или анонимную функцию.
Каррирование
Рассмотрим два определения min
:
def min(x: Int)(y: Int): Int = if x < y then x else y
def min2(x: Int, y: Int): Int = if x < y then x else y
Две функции, min
и min2
, очень тесно связаны, но есть тонкое различие: у них разные типы.
Функция min2
принимает один аргумент, который является структурированным значением, состоящим из пары чисел;
ее тип задается как: (Int, Int) => Int
.
Функция min
, с другой стороны, принимает два аргумента по одному за раз.
Её тип задается как: Int => (Int => Int)
.
Другими словами, min
— это функция, которая принимает число и возвращает функцию (из чисел в числа).
Для каждого значения x
выражение min(x)
обозначает функцию,
которая принимает аргумент y
и возвращает минимум из x
и y
.
Вот еще один пример. Функция add
, определяемая как: def add(x: Int)(y: Int) = x + y
также имеет тип Int => (Int => Int)
.
Для каждого x
функция add(x)
«добавляет x
к переменным».
В частности, add(1)
— это функция-последователь, которая увеличивает свой аргумент на 1
,
а add(0)
— это функция тождественности чисел.
Этот простой прием для замены структурированных аргументов последовательностью простых аргументов известен как «каррирование» в честь американского логика H. B. Curry.
Каррирование - преобразование функции от многих аргументов в набор функций, каждая из которых является функцией от одного аргумента.
Примеры каррирования и декаррирования:
def curry[A, B, C](f: (A, B) => C): A => (B => C) =
a => b => f(a, b)
def uncurry[A, B, C](f: A => B => C): (A, B) => C =
(a, b) => f(a)(b)
Композиция функций
Композиция функций в функциональном программировании (ФП) — это операция, позволяющая объединить две или более функций в одну новую функцию. Эта новая функция применяется последовательно: результат первой функции передается второй функции, результат второй — третьей и так далее. Композиция функций является важным инструментом в ФП, так как она позволяет создавать сложные операции из простых частей, сохраняя чистоту и читаемость кода.
Композиция функций обычно обозначается символом ∘ (кружок) или специальной функцией,
например, compose
в языках программирования.
Основные свойства композиции функций:
- Последовательное применение: Каждая функция выполняется одна за другой, передавая результаты предыдущей функции следующей.
- Неизменяемые данные: Поскольку функции в ФП обычно являются чистыми (не меняют состояние программы), композиция также остается чистой операцией.
- Коммутативность: Порядок выполнения функций важен. Изменение порядка может привести к другому результату.
Основная идея
Если у нас есть две функции:
f: A -> B
g: B -> C
То их композиция g ∘ f
(читается как "g
после f
") — это новая функция A -> C
,
которая сначала применяет f
к аргументу, а затем g
к результату f
.
Функциональная композиция берет функцию типа A => B
, функцию типа B => C
и возвращает функцию типа A => C
.
Функциональная композиция является ассоциативной операцией.
Имеем: ((f andThen g) andThen h) = f andThen (g andThen h)
для всех функций f
, g
и h
.
Соответственно, нет необходимости ставить скобки при записи последовательностей композиций.
Пример
// Определение двух функций
val double: Int => Int = _ * 2
val increment: Int => Int = _ + 1
// Создание новой функции через композицию
val doubleThenIncrement = increment.compose(double)
// Применение составной функции
doubleThenIncrement(5)
// Ожидаемый вывод: 11 = 5 * 2 + 1
Ссылки:
- Не использовать
null
- Харрисон - Введение в функциональное программирование
- A bite of functional programming (in Scala)
- Business benefits of functional programming and how to make it work for your company
- FP vs. OO List Processing
- Functional Programming by Alexander Alvin
- Functional Programming For The Rest of Us by defmacro
- Functional Programming in Scala, Second Edition, Chapter 1-2 by Michael Pilquist, Rúnar Bjarnason, and Paul Chiusano
- Introduction to Functional Programming - Bird, Wadler
- Scala3 book
- Unleashing the Power: The Advantages of Functional Programming in the Digital Age
- What's Functional Programming All About?
- What is Functional Programming? - Alexandru Nedelcu
- What is functional programming and why it matters for your business?
- Wikipedia