Предлагаю читателям «Хабрахабра» перевод статьи «16 Months of Functional Programming». Все мои замечания будут выделены курсивом.
В этой статье я хочу поделиться с вами моим опытом в функциональном программировании. Я чувствую, что в целом за прошедшие 16 месяцев стал лучше разбираться в информатике и компьютерах, чем за предыдущие 10 лет и всё это благодаря моему погружению в Scala и мир функционального программирования. Причина по которой функциональное программирование побуждает вас к постоянному развитию заключается в том, что каждую задачу необходимо переосмысливать заново. Порой невозможно поверить в то, что большинство стандартных задач могут быть решены иным путём и — бум! — функциональный подход предлагает лучшее решение и это шокирует.
Так что же случилось со мной за эти 16 месяцев? Закрыв свой стартап, я стал подыскивать интересный проект для работы. Получил временную подработку консультантом в 2lemetry, что позднее вылилось в полный рабочий день с погружением в функциональное программирование, работу с MQTT брокерами и распределёнными системами. Во время работы в 2lemetry Scala оказала на меня сильнейшее влияние. Приходилось отбрасывать свои представления о программировании и обучаться всему с нуля.
В этой статье я хочу рассказать о некоторых концепциях функционального программирования, которые меня впечатлили. Моя цель — зажечь искру в умах программистов, которые уже имеют опыт работы с такими языками как Java, Ruby и Python. Не беспокойтесь о том, что некоторый код на Scala, который я привожу в этой статье, может быть вам непонятен. Цель этого кода — продемонстрировать концепции функционального программирования в общих чертах. Так же стоит упомянуть, что Scala — это не чистый функциональный язык, т.е. некоторые вещи могут показатся неудобными при смешивании их с ООП. Я постараюсь указывать на такие моменты.
Содержание:
- Неизменяемое состояние
- Функции
- Тип Option и сопоставление с образцом
- Однострочники и for-генераторы
- Система типов
- Ленивые вычисления и бесконечные структуры данных
- Что дальше?
Неизменяемое состояние
Мой первый опыт работы со Scala был достаточно типичным: я начал работать над большим проектом с ощущением того, что Scala — это как Java с некоторыми крутыми дополнениями и некоторыми возможностями из Ruby. Как же сильно я ошибался! Мой код содержал изменяемое состояние везде, где это только возможно и я не понимал для чего могут пригодиться неизменяемые списки и переменные. Как изменить значения в неизменяемых списках? Как изменить значения в неизменяемых отображениях (map)? Как работать с неизменяемым состоянием в циклах?
Для демонстрации преимущества от неизменямого состояния я покажу две версии одной и той же программы, одна на Java, другая на Scala. Следующий код на Java фильтрует список пользователей по флагу активности, сортирует его по ID, затем получает список имён у этих отфильтрованных пользователей:
public class User {
private final int id;
private final String firstName;
private final String lastName;
private final Boolean active;
// Для краткости я пропустил конструкторы, геттеры и сеттеры
}
public static List<String> activeById(List<User> us) {
List<User> users = new ArrayList<User>();
for (User u: us) {
if (u.getActive()) users.add(u);
}
Collections.sort(users, new Comparator<User>() {
public int compare(User a, User b) {
return a.getId() - b.getId();
}
});
List<String> finalUsers = new ArrayList<String>();
for (User u: users) {
finalUsers.add(u.getLastname());
}
return finalUsers;
}
List<User> inputUsers = new ArrayList<User>();
inputUsers.add(new User(11, "Nick", "Smith", false));
inputUsers.add(new User(89, "Ken", "Pratt", true));
inputUsers.add(new User(23, "Jack", "Sparrow", true));
List<User> activeUsersById = activeById(inputUsers)
Автору оригинальной статьи в комментариях указали, что на Java 8 этот код был бы проще. Он ответил, что его задача показать общепринятый императивный подход при работе с данными.
Это типичный код для Java до 8-ой версии: каждая коллекция изменяется некоторым набором действий. Кроме того, весь код несколько многословен, в каждой части кода activeById вы говорите компьютеру что вы хотите, чтобы он сделал с данными вместо того, чтобы описать как данные должны быть обработаны от начала и до конца. Вот та же самая программа написанная в функциональном стиле:
case class User(id: Int, firstname: String, lastname: String, active: Boolean)
def activeById(us: Seq[User]) = us.filter(_.active).sortBy(_.id).map(_.lastname)
val activeUsersById = activeById(Seq(
User(11, "Nick", "Smith", false),
User(89, "Ken", "Pratt", true),
User(23, "Jack", "Sparrow", true)
))
В отличие от примера на Java, код приведён полностью, т.е. можно его запускать в таком виде и он будет работать.
Код выглядит чище и короче по сравнению с императивным подходом, потому что здесь нет состояния которое надо отслеживать. Функция activeById принимает один аргумент (список пользователей) и пропускает его через цепочку функций, которые являются часть языка. Важно отметить, что функции filter, sortBy и map выбраны не случайно. Эти функции отлично описаны и изучены приверженцами функционального программирования.
Рубисты должны были заметить, что этот пример кода очень похож на то, что они пишут на Ruby. Да, этот код может выглядеть похоже, но механизм неизменного состояния, лежащий в основе, сильно отличается. Проблема Ruby в том, что он не поддерживает неизменное состояние. Каждая переменная и структура данных потенциально может быть изменена и это приводит к тому, что нельзя ничему доверять. В Scala есть vals (read-only переменные) и неизменяемые коллекции, которые действительно неизменны.
В итоге, что даёт нам неизменяемость? С практической точки зрения ваш код будет чище, будет меньше подвержен ошибкам (вы всегда знаете что находится в ваших коллекциях и read-only переменных) и лучше абстрагируемым. Другая большая выгода от неизменности состояния заключается в том, что при написании конкурентных (concurrent) программ вас не будет беспокоить то, что один поток может повредить данные использующиеся в другом потоке.
Функции
Функциональное программирование — это о функциях (сюрприз?). Существуют различные виды функций и техник функциональной композиции, которые используются в функциональном программировании.
Чистые функции являются одним из столпов функционального программирования. Чистая функция — это функция, которая зависит только от её входных параметров. Она возвращает результат без изменения внешнего состояния. Функции sin(x: Double) или md5(s: String) отличные примеры чистых функций, которые зависят только от входных параметров и всегда возвращают ожидаемый результат, т.к. они не полагаются на состояние окружающего мира. Эти факторы делают чистые функции легко тестируемыми и менее склонным к багам.
Очевидно, что не все задачи могут быть реализованы с использованием чистых функций. Например, операции ввода/вывода, логирования, чтения и записи в БД и т.д. В функциональном программировании существуют модели и абстракции, которые позволяют реализовать эти нечистые абстракции в чистом виде, что приводит к более чистому и компонуемому коду.
Функции в Scala являются объектами первого класса. Это означает, что не только методы класса могут быть объявлены и вызваны. Кроме того, они могу использоваться как самостоятельный тип данных. Вы можете передавать функцию в другую функцию и возвращать из функции другую функцию. Вы можете сохранять функцию в переменную или в структуру данных. Вы можете работать с ней, как с литералом без того, чтобы как-то её называть (лямбда-функция). Пример:
val ints = Seq(1, 2, 3, 4, 5)
ints.filter(n => n % 2 == 0)
Посмотрите на n => n % 2 == 0, полная форма (n) => { n % 2 == 0 }, это функция без имени (лямбда-функция), которая проверяет, является ли число чётным. Вы можете передавать лямбда-функции как аргумент другой функции или использовать её как возвращаемое значение.
Функции могут быть вложенными в другие функции. Это полезная возможность, когда вам понадобится рекурсивно вызывать подпрограмму (subroutines), которую вы не хотите помещать в область видимости выходящую за пределы вашей функции.
def toList: List[A] = {
@annotation.tailrec
def go(s: Stream[A], l: List[A]): List[A] = s match {
case Empty => l
case Cons(h, t) => go(t(), h() +: l)
}
go(this, List[A]()).reverse
}
В этом примере мы не хотели бы, чтобы функция go была доступна в той же области видимости, что и функция toList, потому что её реализация необходима только для функции toList и в области видимости, в которой находится функция toList, может оказаться другая функция с названием go.
Каррирование и частичное применение функции — это чисто математическая концепция, которая прекрасно применяется в функциональных языках. Это позволяет нам сохранять частично вызванные функции в переменные и передавать их в другие функции.
trait Resource
case class User(id: Int) extends Resource
case class Record()
case class FormattedRecord()
def loadRecordsFor(r: Resource, since: Long): List[Record] = ???
def formatRecords(f: Long => List[Record], since: Long): List[FormattedRecord] = ???
val userRecordsLoader = loadRecordsFor(User(36), _: Long)
formatRecords(userRecordsLoader, System.currentTimeMillis - 86400000)
??? — означает объявление без определения
В этом примере у нас есть две шаблонные функции loadRecordsFor и formatRecords. Мы частично применили loadRecordsFor для некоторого пользователя и сохранили результат в переменную userRecordsLoader. Затем вызываем formatRecords с параметром userRecordsLoader, т.к. эта переменная соответствует сигнатуре функции formatRecords (т.е. вызываем функцию formatRecords с первым аргументом — частично применённой функцией). Этот вид функциональной композиции достаточно удобен во многих ситуациях и делает код менее жёстким.
Этот пример не очень показательный. Считаю, что тему каррирования автор не раскрыл.
Тип Option и сопоставление с образцом
Тип данных Option — это абстракция, которая представляет опциональные значения. Может показаться, что он не особо необходим, но в повседневной работе это черезвычайно мощный механизм для представления null, empty, битых объектов и переменных значений.
Тип Option — это контейнер, который содержит значение определённого типа, представляемого как Some[T] или ничего не содержащего, представляемого как None. Применение этого типа в нашем коде позволяет забыть о бесчисленных случаях возникновения исключений при обращении к null-указателю (null pointer exceptions) или какую-либо несовместимость типов, всякий раз, когда извлекаются null-значения.
Давайте рассмотрим пример:
case class Project(id: String, name: String, priority: Int, description: Option[String])
object ProjectsAccessor {
find(id: String): Option[Project] = ???
}
val project = ProjectsAccessor.find(123)
Здесь мы пытаемся получить запись о проекте из БД, но мы не знаем существует ли проект с таким ID. Вместо того, чтобы возвращать null или выбрасывать исключение, мы возвращаем Some[Project] или None, т.к. при объявлении метода find мы указали тип возвращаемого значения как Option[Project].
Контейнерные типы позволяют нам использовать другой мощный инструмент — сопоставление с образцом (pattern matching). Сопоставление с образцом — это подход к обработке данных на основе их структуры. Eсли мы захотим обработать результат вызова метода find из примера выше и получить название проекта мы можем сделать что-то вроде:
ProjectsAccessor.find(123) match {
case Some(p) => p.name
case None => ""
}
Мы сопоставляем с образцом результат работы метода find для проверки существования проекта. Если он существует, то возвращается его название, иначе возвращаем пустую строку. На первый взгляд, это может выглядеть как оператор switch-case в Java, но на самом деле они сильно различаются. При сопоставлении с образцом вы можете добавлять нетривиальную логику в шаблоны:
ProjectsAccessor.find(123) match {
case Some(p) if 1 until 5 contains p.priority => p.name
case Some(p) if name == "Default Project" => p.name
case Some(p) => None
case None => ""
}
Так же вы можете сопоставлять результат на основе текущей структуры объекта:
def descriptionWrapper(p: Project) = p match {
case Project(_, _, _, None) => "No description."
case Project(id, _, _, Some(d)) => s"Project $id's description: $d"
}
Этот подход к обработке сложных логических конструкций более компактный и прямолинейный по сравнению с if-операторами и громоздким switch-case.
Однострочники (One-Liners) и for-генераторы
Одна из замечательных возможностей функциональной композиции — это функциональные цепочки. Вместо того, чтобы постоянно повторять однообразные действия над коллекциями с использованием циклов, можно сделать это одним элегантным выражением или однострочником. Например:
case class Participant(name: String, score: Int, active: Boolean)
val ps = Seq(Participant("Jack", 34, true), Participant("Tom", 51, true),
Participant("Bob", 90, false))
ps.filter(_.score < 50).filter(_.active).map(_.copy(active = false))
В этом однострочнике мы собрали всех подписчиков чей результат меньше 50 и которые до сих пор активны, затем мы изменили статус у выбранных подписчиков на false. В конечном итоге мы получили List(Participant(Jack, 34, false)). Есть достаточно большое кол-во ситуаций в которых подобные однострочники сохраняют программистам время и резко сокращают количество кода.
Если однострочник становится слишком непрозрачным, то его всегда можно разбить с помощью for-генератора. Пример выше можно переписать в эквивалентное выражение:
for {
loser <- ps if loser.score < 50
activeLoser <- Some(loser) if activeLoser.active
deactivatedLoser <- Some(activeLoser.copy(active = false))
} yield deactivatedLoser
Это выражение более многословно чем однострочник, но в тех случаях, когда логика становится слишком непрозрачной, это техника действительно помогает улучшить читаемость кода при сохранении всех преимуществ неизменяемости и функциональных цепочек.
В Scala for-генератор – это синтаксический сахар для функциональной композиции.
Система типов
Будучи программистом на Ruby, строгая типизация в Scala ощущалась в начале как бремя, потому что я использовал её как джавист. Я добавлял подробное описание типов везде и не использовал обобщённые generic функции. Излишне сказать, что это был неправильный подход к работе. Некоторые функциональные языки обладают продвинутой системой типов с такими свойствами, которые не используются программистами на популярных языках. Эти свойства позволяют коду быть более гибким и компонуемым. Давайте пройдёмся по некоторым из них.
Вывод типов является способностью компилятора догадаться о типе выражения без явного указания его программистом. В некторых случаях Scala не может догадаться о типе без подсказки. Давайте посмотрим на пример:
// Вы всегда должны указывать типы передаваемых в метод аргументов
def nameStartsWith(ns: Seq[String], n: String): Seq[String] =
// Scala не может вывести тип для обобщённых коллекций, т.е. вы не можете сказать Seq.empty
ns.foldLeft(Seq.empty[String]) {
// Но в лямбда-функции не требуется указыать тип явно
(l, r) => if(r.startsWith(n)) r +: l else l
}
// Вывод типов хорошо работает при создании списков
val names = Seq("Bob", "Alice", "Ann")
nameStartsWith(names, "A") // возвратит List(Ann, Alice)
Этот пример показывает обе стороны вывода типов в Scala: вы обязаны явно указывать типы, но в некоторых случаях, вроде того, когда вы передаёте в функцию лямюда-функцию в качестве аргумента (l, r) => ..., типы можно опускать. В чистых функциональных языках таких, как Haskell, вам вряд ли когда-либо придётся указывать тип в программах (спорное утверждение). Компилятор достаточно умён, чтобы вывести их.
Cтоит отметить, что при объявлении функции не обязательно было указывать тип возвращаемого значения, компилятор Scala выведет его сам.
Ограничение типов — это ещё одна важная концепция в функциональном программировании. В общем случае это означает, что вы можете указать иерархию класса при объявлении обобщенного типа. В Java вы можете использовать обобщения для определния типа во время исполнения и по-прежнему считать свой код типобезопасным. Для примера, чтобы объявить обобщённый список элементов некоторого типа вы должны использовать интерфейс (код на Java): public interface MyList<T>. Если вы хотите объявить список, скажем, содержащий отображения (Map), но при этом вы не знаете какая реализация отображений будет использована, то вам необходимо указать верхнюю границу для типа в вашем интерфейсе public interface MyList<T extends Map>. Теперь вы можете использовать список заполненный такими типами как Hashtable, LinkedHashMap, HashMap и TreeMap или другими словами всех потомков интерфейса Map. При этом никакой другой тип не может быть использован, т.к. обозначена верхняя граница. Вот пример использования верхней границы в Scala:
def convertToInts[T <: AnyVal](es: Seq[T], f: T => Int): Seq[Int] = {
es.map(f(_))
}
AnyVal является родителем таких классов как Double, Float, Int и многих других (скалярных типов). В этой функции мы просто объявили, что тип T будет потомком AnyVal. Так же можно указать нижнюю границу типа, вроде [T >: Int] это будет соответствовать родителям типа Int. Вы так же можете смешивать границы типов для различных обобщений в сигнатуре функции: [T >: Int <: Any].
Одно из важных свойств продвинутой системы типов является ковариантность и контравариантность. В Java, если у вас есть class List<T>, List<Object> и List<String>, то они будут не связанны или инвариантны. С другой стороны существую ковариантные массивы, т.е. String[] это подтип типа Object[]. Так как массивы являются изменяемыми в некоторых случаях вы можете получить исключение ArrayStoreException в рантайме. В Scala массивы инвариантны по-умолчанию и неизменяемые коллекции (или контейнерные типы) ковариантны [+A]. Так как они неизменяемые все потенциальные ошибки будут обнаружены во время компиляции, а не в рантайме. Другая возможность — указать контейнер контрвариантным [-A]. Контрвариантность означает то, что контейнер с родительским типом является подтипом контейнера с дочерним типом. Вот как это работает:
case class InvariantContainer[A]()
case class CovariantContainer[+A]()
case class ContravariantContainer[-A]()
class Person
class User extends Person
class Admin extends User
val inv1: InvariantContainer[User] = InvariantContainer[User] // works
val inv2: InvariantContainer[User] = InvariantContainer[Admin] // doesn't work
val cov1: CovariantContainer[User] = CovariantContainer[User] // works
val cov2: CovariantContainer[User] = CovariantContainer[Admin] // works
val con1: ContravariantContainer[User] = ContravariantContainer[User] // works
val con2: ContravariantContainer[User] = ContravariantContainer[Admin] // doesn't work
val con3: ContravariantContainer[User] = ContravariantContainer[Person] // works
Ковариантность и контрвариантность широко используется в реализации коллекций и хотросплетениях при указании типа функции.
Последняя продвинутая возможность типов, которую я хотел бы затронуть, это границы вида (view bounds). Предположим, что вам нужно выполнить операции над числами, но некоторые из них представлены в виде строк (т.е. «123» или 123). Как вы сделаете это? В простом случае, как этот, вы можете сконвертировать строки в числа вручную или, в более сложных случаях, написать собственный конвертер, а затем явно вызывать его для конвертации данных из одного типа в другой. В слаботипизированных языках, таких как Ruby, интерпретатор будет динамически конвертировать строки в числа. Возможно, вы будете удивлены тем, что в Scala есть способ реализовать подобное поведение без потери типобезопасности.
Насколько я понимаю, автор ошибается с Ruby, например, такой код работать не будет [10, «20»].min. В данном случае корректнее было бы привести в пример PHP.
Чтобы это заработало в Scala (давайте используем стандартную функцию math.min() для примера) всё что необходимо сделать — это определить неявный конвертер для ваших типов:
implicit def strToInt(x: String) = x.toInt
math.min("10", 1)
Тут Scala будет искать неявные преобразования из строки в число. После нахождения функции strToInt, основанной на её сигнатуре, она будет применена ко всем строкам переданным в math.min без явного вызова strToInt. Если вы не объявили неявную конвертацию, то компилятор выкинет исключение. А если объявили и попытаетесь передать строку, которая не является числом, то получите исключение в рантайме.
Что если мы хотим написать магическую функцию, которая найдёт неявную конвертацию для себя самой? Это очень просто! Всё что вам нужно — это объявить границу вида, которая укажет компилятору производить поиск неявной конвертации:
implicit def strToInt(x: String) = x.toInt
def halfIt[A <% Int](x: A) = x / 2
halfIt("20")
Результатом вызова halfIt(«20») будет 10 как и ожидалось. Граница вида [A <% Int] ожидает Int или всё, что может рассматриваться как Int. В нашем случае это строка, которая может быть неявно преобразованна в число.
Ленивые вычисления и бесконечные структуры данных
Концепция ленивых вычислений непосредственно не существует в нефункциональных языках, но её легко уловить. Посмотрите на обычное условие:
def expensiveOperation() = ???
val a = "foo"
val b = "foo"
if ((a == b) || expensiveOperation()) true else false
В большинстве императивных языков оператор || вычисляет предикаты (a == b) и expensiveOperation() лениво, т.е. expensiveOperation() не будет вызван до тех пор пока if (a == b) равен true (т.е. до тех пор, пока a равно b). И expensiveOperation() будет вызван если if (a == b) вернёт false. Ленивые вычисления в Scala позволяют определить подобное поведение в разных конекстах.
Вы можете определить переменные как lazy, т.е. они не будут вычислены до тех пор, пока к ним не обратились в первый раз, в отличие от обычных переменных, которые вычисляются при объявлении. После однократного вычисления ленивая переменная запоминает своё значение.
case class Order(name: String, price: Int)
case class User(id: Int, orders: Seq[Order]) {
lazy val cheapOrders: Seq[Order] = orders.filter(_.price < 50)
lazy val expensiveOrders: Seq[Order] = orders.filter(_.price >= 50)
}В этом примере у нас есть case class для представления пользователя, который содержит в себе списки заказов. В отличие от обычных свойств, cheapOrders и expensiveOrders не будут вычислены в момент инициализации класса (т.е. в момент создания объекта из класса). Они вычисляются, когда мы обратимся к ним напрямую. Почему бы не использовать метод? Проблема в том, что у нас могут быть дорогостоящие вычисления или каждый раз происходить обращения к БД, когда мы вызываем метод. Ленивые переменные сохраняют свой результат при первом обращении, что может привести к эффективным оптимизациям в некоторых случаях.
В других языках используют технику мемоизации, что можно также рассматривать как ленвые вычисления.
Другой пример отложенных вычислений — это передача аргументов по имени (call-by-name). Обычно, аргументы функции вычисляются перед тем, как они будут в неё переданы. Тем не менее, в некоторых случаях бывает полезно вычислять переданный аргумент отложено тогда, когда это потребуется.
trait Person
case class User() extends Person
case class Admin() extends Person
def loadAdminsOrUsers(needAdmins: => Boolean, loadAdmins: => Seq[Admin],
loadUsers: => Seq[User]): Seq[Person] = {
if (needAdmins) loadAdmins
else loadUsers
}
Здесь у нас три параметра by-name с потенцаильно дорогостоящими операциями обращения к БД. Мы не хотели бы, чтобы все они были выполнены до того, как попадут в наш метод. Стрелка => означает, что мы передаём внутрь саму функцию, а но возвращаемое ею значение. Теперь мы можем вызывать её когда нам это потребуется.
Ленивые вычисления и параметры by-name используются для реализации одной из мощнейших конструкций функционального программирования — бесконечных структур данных. В императивном программировании все ваши структуры данных имеют определённый размер, что на самом деле отлично для большинства случаев, но иногда неизвестно какого размера будет структура данных. С отложенными вычислениями есть возможность объявить структуру данных в общем виде без её полного содержимого до тех пор, пока оно вам не потребуется.
Всё это хорошо звучит в теории, но будет ли это работать? Давайте воспользуемся бесконечной структурой данных, называемой stream для генерации простых чисел. В Java для генерации простых чисел можно написать функцию, которая генерировала бы простые числа до некоторого предела. Затем вы могли бы вызвать эту функцию для генерации списка из N простых чисел и передать его куда-нибудь. Если вам понадобится другой список простых чисел, то вам придётся пересчитать свой список с нуля. В Scala мы можем сделать что-то вроде:
val primes: Stream[Int] = {
def generatePrimes (s: Stream[Int]): Stream[Int] =
s.head #:: generatePrimes(s.tail filter (_ % s.head != 0))
generatePrimes(Stream.from(2))
}
Синтаксис может показаться вам непонятным, но в данном случае это не имеет значения. Главное то, что вы можете сделать с этой структурой данных. Скажем, что вам необходимо получить первые 5 простых чисел, больших 100. Это легко, используя наш stream:
primes.filter(_ > 100).take(5).toList
Эта функциональная цепочка вернёт List(101, 103, 107, 109, 113) — как и ожидалось. Крутая вещь заключается в том, что вы можете передавать primes в любые другие функции без необходимости её всякий раз собирать заново. Так же вы можете применять цепочки функций (как filter в примере выше) и передавать уже это выражение без генерации промежуточного результата. Это позволяет нам компоновать абстракции и лепить программы как из пластилина.
Что дальше?
Надеюсь, я заинтересовал вас функциональным программированием. Для меня писать об этом было очень увлекательно. Я признаю, что ещё многое предстоит изучить и усвоить в этой области. Моя цель — начать глубже копать теорию функционального программирования, такую как типизированное лямбда-исчисление, теорию типов и теорию категорий. Я так же хочу изучить Haskell — чистый функциональный язык программирования, и надеюсь что это принесёт плоды.
Всем дочитавшим выражаю благодарность!
Автор: scalavod
