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

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

Изменение переменной
Изменение структуры данных на месте
Установка поля на объекте
Генерация исключения или остановка с ошибкой
Печать на консоль или чтение пользовательского ввода
Чтение или запись в файл
Рисование на экране

Рассмотрим основное отличие императивного программирования - IP от FP на примере вычислении суммы коллекции чисел.

В IP подходе сумма чисел вычислялась бы так:

def sum(ints: List[Int]): Int =
  var sum = 0
  for i <- ints do sum += i
  sum
sum(List(1, 2, 3))
// res0: Int = 6

Этот код изменяет поле var в цикле for - использует изменяемое состояние.

Подход FP может выглядеть так:

def sum(xs: List[Int]): Int =
  xs match
    case Nil => 0
    case x :: tail => x + sum(tail)
sum(List(1, 2, 3))
// res2: Int = 6

В FP подходе не используется изменяемое состояние.

В FP на Scala следует придерживаться следующих правил:

не использовать null
использовать только чистые функции
использовать только val переменные
не использовать class-ы, инкапсулирующие данные и поведение
использовать if только в качестве выражений, а не операторов

Более формальное определение чистой функции:

Функция f с типом ввода A и типом вывода B (записанная на Scala как один тип: A => B) — это вычисление, которое связывает каждое значение a типа A ровно с одним значением b типа B, которое определено исключительно по значению a. Любое изменение состояния внутреннего или внешнего процесса не имеет отношения к вычислению результата f(a).

Функция высшего порядка

Функция высшего порядка (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)
// res3: String = "The absolute value of -42 is 42."
formatResult("factorial", 7, factorial)  
// res4: String = "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)
// res5: Int = 1

Синтаксис (x: Int) => x == 9 представляет собой литерал функции или анонимную функцию.

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

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

Примеры каррирования, раскаррирования и композиции:

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)

def compose[A, B, C](f: B => C, g: A => B): A => C =
  a => f(g(a))

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

Композиция двух функций f и g — это функция h такая, что h(x) = f(g(x)).

type A
type B
type C

def f: A => B = ???
def g: B => C = ???
def h: A => C = f andThen g

Функциональная композиция берет функцию типа A => B, функцию типа B => C и возвращает функцию типа A => C. Функциональная композиция является ассоциативной операцией. Имеем: ((f andThen g) andThen h) = f andThen (g andThen h) для всех функций f, g и h. Соответственно, нет необходимости ставить скобки при записи последовательностей композиций.

Ссылки: