itmo_conspects

Функциональное программирование. Трек Холопова Д. С.

Лекция 1. Введение

Сейчас самой распространенной парадигмой программирования в бизнес-разработке является объектно-ориентированное программирование (ООП), которое строится вокруг 4 ключевых принципов:

  1. Абстрагирование сущностей для выделения существенных характеристик
  2. Инкапсуляция, то есть отделение друг от друга элементов объекта, которые определяют его устройство и поведение
  3. Наследование, что позволяет объекту одного класса иметь общие свойства с объектом другого класса, но при этом расширять или изменять структуру или поведение
  4. Модульность системы

Парадигма ООП имеет множество преимуществ, но иногда не подходит под некоторые задачи

Так, например, в ООП у объекта есть внутреннее изменяемое состояние, от которого неявно зависит поведение функции. Например, в этом примере, функция изменяет переданный объект (а именно удаляет запись в нем):

class Validator {
    static void validate(Map<String, User> users) {
        if (users.containsKey("admin") && !users.get("admin").isActive()) {
            users.remove("admin"); // валидация мутирует входные данные
        }
    }
}

Map<String, User> users = new HashMap<>();
users.put("admin", new User("Alice", false));
Validator.validate(users);
User admin = users.get("admin"); // admin == null

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

users = [("admin", User ("Alice", False))]
users' = validate users

result1 = lookup "admin" users' -- "admin" не найдется
result2 = lookup "admin" users -- найдется объект "Alice"

Также функции в ООП зачастую имеют побочные эффекты. Это значит, что результат их выполнения зависит не только от аргументов, но и от внутреннего состояния других объектов, например, базы данных:

double withdraw(BankAccount account, double amount) {
    if (amount > account.getBalance()) {
        logger.error("Not enough money for account {}", account.getId());
        throw new IllegalStateException("Insufficient funds");
    }

    account.setBalance(account. getBalance() - amount);
    logger.info("Withdraw {} from {}", amount, account.getId());
    auditService. save(account);
    return account.getBalance();
}

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

Также чистые функции позволяют выполнять ленивые вычисления. Например, такой код на Java:

public int firstArgument(int a, int b) {
    return a;
}

firstArgument(1, 1/0); // ArithmeticException

запустится в ошибкой ArithmeticException, так как сначала нужно вычислить значения параметров 1 и 1/0, а затем вызвать функцию, несмотря на то, что второй аргумент не применяется. В функциональном языке с ленивыми вычислениями второй аргумент не вычисляется, из-за чего программа выполняется:

firstArgument a b = a
result = firstArgument (1) (1/0) -- ok

Подытожим ключевые идеи функциональной парадигмы:

  1. Иммутабельность
  2. Чистые функции
  3. Ленивые вычисления (поддерживаются не всеми языками, например, в Haskell ленивые вычисления применяются по умолчанию, а в Clojure, по умолчанию, нет)
  4. Функции высших порядков - функции, которые принимают другие функции как аргументы или возвращают их
  5. Алгебраические типы данных - способ моделирования данных (есть не во всех языках)

Сейчас самым распространенным функциональным языком программирования является Haskell, появившийся в конце 1980-ых

Язык Haskell имеет компилятор GHC (от Glasgow Haskell Compiler) ghc и интерактивный интерпретатор GHCi ghci. Интерпретатор (он же REPL, от Read-Eval-Print Loop) имеет свои команды:

В качестве системы сборки и пакетных менеджеров применяются два варианта:

Раньше Cabal имел проблему с зависимостями, из-за чего на диске сохранялась только одна версия конкретного пакета, в ответ на что был создан Stack. Но с приходом Cabal версии 2 проблема исчезла. Сейчас Cabal используется по умолчанию

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

Лекция 2. Синтаксис языка Haskell

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

Одними из базовых типов в Haskell являются:

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

Операция Обозначение в языке Пример Результат
Сложение + 2 + 3 5
Вычитание - 5 - 2 3
Умножение * 4 * 3 12
Деление / 7 / 2 3.5
Целочисленное деление (применимо только к целым числам) `div` 7 `div` 2 3
Деление по модулю (применимо только к целым числам) `mod` 7 `mod` 2 1
Возведение в степень (показатель степени должен быть неотрицательным) ^ 2 ^ 3 8
Меньше < 2 < 3 True
Больше > 2 > 3 False
Меньше или равно <= 2 <= 2 True
Больше или равно >= 3 >= 2 True
Равно == 2 == 2 True
Не равно /= 2 /= 3 True
Логическое И && True && False False
Логическое ИЛИ \|\| True \|\| False True
Логическое НЕ not not True False
Отрицание числа negate negate 5 -5

Единственным отличием является использование /= в качестве оператора “не равно” вместо привычного !=

Комментарии в коде обозначаются так:

-- однострочный комментарий

{-
    многострочный
    комментарий
-}

В дальнейших примерах будет представлен код и вывод интерпретатора ghci
Строка с ghci> обозначает вводимый код, а код без ghci> обозначает результирующее значение

Вызов функции осуществляется так:

ghci> min 5 8
5

Здесь min - это название функции, а 5 и 8 - аргументы, перечисленные через пробел

Если аргумент содержит в себе пробелы, то аргумент нужно обернуть в скобки. Например:

ghci> min (3) (8)
3
ghci> min 3 (max 8 1)
3
ghci> max 3 max 8 1
-- ошибка GHC-39999, нельзя вызвать `max` как функцию 4 аргументов
ghci> (min 3 max) 8 1
-- ошибка GHC-39999, второй аргумент в функции `min` не может иметь тип функции

Такой способ вызова функции называется префиксный. Другим способом является инфиксный вызов:

ghci> (+) 2 3
5
ghci> 2 + 3
5
ghci> div 2 3
0
ghci> 2 `div` 3
0
ghci> mod 2 3
2
ghci> 2 `mod` 3
2

Здесь (+) 2 3 является префиксной формой, а 2 + 3 - инфиксной. Как можно заметить, операторы в Haskell - это тоже функции. Если функция состоит из специальных символом, то в префиксной форме он должен быть обернутым в скобки ((+) 2 3), а если из букв, то в инфиксной форме в обратные кавычки (2 `mod` 3)

Помимо этого у операторов есть две характеристики: тип ассоциативности и приоритет выполнения

Такую информацию об операторе можно узнать в интерпретаторе с помощью инструкции :info или :i:

ghci> :i +
type Num :: * -> Constraint
class Num a where
  (+) :: a -> a -> a
  ...
        -- Defined in `GHC.Internal.Num'
infixl 6 +

В Haskell можно сделать свой оператор, например:

(|-|) :: Int -> Int -> Int
(|-|) a b = abs (a - b)

В первой строчке определен тип оператора, а именно Int -> Int -> Int. Последний тип в этой цепочке определяет тип возврата, а предыдущие - типы аргументов. Вторая строка определяет реализацию оператора

Важно заметить, что объявление оператор нельзя указать в интерпретаторе

Далее оператор можно будет применить:

ghci> (|-|) 4 5
1
ghci> 4 |-| 5  
1

По умолчанию, такой оператор будет левоассоциативным и иметь приоритет 9

Чтобы изменить тип ассоциативности и приоритет, нужно применить соответствующее ключевое слово (infix, infixl или infixr):

(|-|) :: Int -> Int -> Int
(|-|) a b = abs (a - b)
infixl 6 |-|

Обозначение оператора может состоять из таких символов: !, #, $, %, &, *, +, ., /, <, =, >, ?, @, \, ^, |, -, ~, :. Если оператор начинается с :, то он является конструктором

Функции объявляются таким же образом:

mod :: Int -> Int -> Int
mod a b = a - b * a `div` b

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

Такое определение функции называется явным или точечным (pointful). Однако есть еще бесточечный (pointfree) стиль:

-- Явный
plus5 :: Int -> Int
plus5 a = a + 5

-- Бесточечный
plus5 = (+) 5
-- или так
plus5 = (+5)

Можно также применять в функциях с несколькими аргументами (но такое ухудшает читаемость):

-- Pointful
pentaSum a b c d e = a + b + c + d + e
-- Pointfree
pentaSum = ((((((+) .). (+)) .). (+)) .). (+)

Сервис позволяет переводить функции из точечного стиля в бесточечный

Рассмотрим конструкции языка:

В Haskell можно определить функцию используя соответствие шаблону:

isZero :: Integer -> Bool
isZero 0 = True
isZero _ = False

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

isZero :: Integer -> Bool
isZero _ = False
isZero 0 = True

Другой пример - вычисление значений последовательности a_1 = 1, a_2 = 2, a_k = a_{k - 1} + 3 * a_{k - 2}:

someSequence :: Integer -> Integer
someSequence n = calcHelper n 1 2 where
    calcHelper 1 a1 _ = a1
    calcHelper 2 _ a2 = a2
    calcHelper k x y = calcHelper (k - 1) y (y + 3 * x)

Здесь в блоке where объявляется вспомогательная функция calcHelper

Тип функции можно узнать с помощью инструкции :t или :type:

ghci> :type not
not :: Bool -> Bool

При этом есть особые функции:

Такие функции не определяют явно типы, поэтому они соблюдают параметрический полиморфизм

Помимо этого в Haskell есть перегрузка функций (или Ad-hoc полиморфизм):

ghci> :t (+)
(+) :: Num a => a -> a -> a
ghci> :t (==)
(==) :: Eq a => a -> a -> Bool

Здесь для операторов на тип a наложены ограничения: для оператора + это то, что a должен быть числом, а для == - что a должен быть сравниваемым

Haskell поддерживает композицию функций. В математике композиция функций g ○ f определена так, что (g ○ f)(x) = g(f(x))

В Haskell композиция функций осуществляется через оператор .:

f :: Integer -> Integer
f x = x ^ 2
g :: Integer -> Integer
g x = x + 1

-- (f ○ g)(x) = f(g(x))
example -: Integer -> Integer
example x = (f . g) x

-- или так
example = (f . g)

Так как . - это оператор, значит это функция, и у нее такой тип:

ghci> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

Как можно заметить . - это функция от 3 аргументов: функции b -> c, функции a -> b и значения a

Реализовать . можно так:

(.) f g x = f (g (x))

Другой оператор $ выглядит таким образом:

($) :: (a -> b) -> a -> b
f $ x = f x

Как можно заметить, оператор $ применяет функцию f с аргументом x. В отличие от обычного применения оператор $ имеет приоритет 0 и правоассоциативен

Например, так можно представить оператор .:

(.) f g x = f $ g x

Или так можно возвести в квадрат несколько раз:

f :: Integer -> Integer
f = (^2)

ghci> f . f $ 2
16
ghci> f . f . f $ 2
256

Или упростить еще сильнее:

ghci> (^2) . (^2) $ 2
16
ghci> (^2) . (^2) . (^2) $ 2
256

Такая форма не засоряет пространство имен, но ухудшает читаемость

This site is open source. Improve this page.