Функциональное программирование

Введение

Функциональное программирование (ФП, 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

Ссылки: