Привет! Ранее мы познакомились с основными понятиями и моделью вычислений функционального программирования. В этой статье мы научимся работать с такими инструментами как функции высшего порядка и каррирование, а в заключении рассмотрим замечательную идею объектно-ориентированного программирования - инкапсуляцию. А еще будет много примеров с кодом.

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

Напомню, что функции в ФП - это полноправные объекты, которые могут выступать в роли результата вычисления функции и передаваться в функцию качестве аргументов (функции - это объекты первого класса, если проще). Функции, работающие с другими функциями имеют специальное название. Итак, важное определение:

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

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

def sumInts(a: Int, b: Int): Int = 
	if (a > b) 0 else a + sumInts(a + 1, b)

Код суммирования кубов чисел:

def cube(x: Int): Int = x * x * x
	
def sumCubes(a: Int, b: Int): Int = 
	if (a > b) 0 else cube(a) + sumCubes(a + 1, b)
		

Код суммирования факториалов:

def fact(a: Int): Int =
	if (a == 0) 1 else a * fact(a - 1)

def sumFactorials(a: Int, b: Int): Int =
	if (a > b) 0 else fact(a) + sumFactorials(a + 1, b)
		

Все примеры очень похожи и являются частными случаями выражения .

Здесь f(x) - произвольная функция. Давайте теперь попробуем записать эту формулу на Scala:

def sum(f: Int => Int, a: Int, b: Int): Int =
	if (a > b) 0 else f(a) + sum(f, a + 1, b)
		

Мы только что определили функцию высшего порядка, принимающую в качестве аргумента функцию-преобразователь и границы отрезка суммирования. Тип Int => Int означает тип функции от целого аргумента, которая возвращает целое число. В общем A => B означает тип функции, принимающий аргумент типа A и возвращающей результат типа B.

Теперь определим функции-преобразователи:

def id(x: Int): Int = x
def cube(x: Int): Int = x * x * x
def fact(x: Int): Int = if (x == 0) 1 else x * fact(x - 1)
	

Перепишем наш первоначальный код суммирования с использованием функций-преобразователей:

def sumInts(a: Int, b: Int) = sum(id, a, b)
def sumCubes(a: Int, b: Int) = sum(cube, a, b)
def sumFactorials(a: Int, b: Int) = sum(fact, a, b)
	

Код стал понятнее.

Анонимные функции

Функции высшего порядка сделали код понятнее. Но есть возможность еще улучшить код. В нашем примере функции id, cube, fact логически не значимы, дав этим функциям имена мы расширили количество логических примитивов и усложнили программу. Передача функций в качестве параметров ведет к подобным проблемам. Чтобы еще лучше продемонстрировать суть проблемы, давайте сравним функции со строками и представим что для объявления каждого строкового литерала мы должны использовать def.

def str = "abc"; println(str)
	

Слава богу, вместо этого обычно пишут println("abc").

Мы используем строковые литералы, не назначая им имен. Во всех известных мне функциональных языках также можно работать с функциями. Функции без имени предсказуемо называются анонимными функциями.

Продемонстрируем синтаксис анонимных функций в Scala на примере cube:

(x: Int) => x * x * x

Тип возвращаемого результата может быть выведен компилятором автоматически и обычно опускается. (x: Int) - список параметров функции, x * x * x - тело функции. Функция от нескольких аргументов задается так: (x: Int, y: Int) => x + y.

По своей сути анонимные функции в Scala - синтаксический сахар (не обязательная лексическая конструкция, введенная для удобства). Давайте посмотрим как можно выразить анонимную функцию (x1: T1, ... , xn: Tn) => E через обычную.

{
	def f(x1: T1, ..., xn: Tn) = E; 
	f
}

Блок вернет объект функции (последняя вычисленная строка f), имя f будет недоступно вне блока.

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

def sum(f: Int => Int, a: Int, b: Int): Int =
	if (a > b) 0 else f(a) + sum(f, a + 1, b)

def sumInts(a: Int, b: Int) = sum(x => x, a, b)
def sumCubes(a: Int, b: Int) = sum(x => x*x*x, a, b)
	

А вот функцию fact мы переписать все-таки не сможем из-за ее рекурсивной природы. Без имени fact мы не сможем описать саму функцию. Точнее сможем через комбинатор неподвижной точки, но это способ не для слабонервных (спасибо Ivan Yurchenko за подсказку). Еще можно написать такой код:

def sumFactorials(a: Int, b: Int) = sum ({
	def fact(x: Int): Int = if (x == 0) 1 else x * fact(x - 1)
	fact
}, a, b)

Но такая запиь дело вкуса.

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

Давайте вернемся к примеру с функцией sum из предыдущего раздела. Перепишем код следующим образом:

def sum(f: Int => Int): (Int, Int) => Int = {
	def sumFunc(a: Int, b: Int): Int =
		if (a > b) 0 else f(a) + sumFunc(a + 1, b)
			
	sumFunc
}
	

Теперь функция sum принимает функцию-преобразователь и возвращает анонимную функцию от границ отрезка. Эта функция будет выполнять суммирование и преобразование одновременно! Далее мы можем переписать нашу реализацию суммы, суммы кубов и факториалов более компактно:

def sumInts = sum(x => x)
def sumCubes = sum(x => x * x * x)
def sumFactorials = sum(fact)
	

Мы можем использовать эти функции так же, как и прежде:

sumCubes(1, 5) + sumFactorials(10, 15)
	

На мой взгляд код стал более естественным и лаконичным. Но можно сделать код еще лучше. Давайте вернем имена нашим анонимным функциям id, cube, fact и запишем предидущий код так:

sum(cube)(1,5) + sum(fact)(10, 15)
	

Тут sum(cube), например, вернет анонимную функцию, аналогичную sumCubes. Далее эта функция будет рассчитана для аргументов (1,5). Вообще в Scala применение функции ассоциативно слева:

sum(cube)(1,5) == (sum(cube))(1,5)
	

Таким образом мы можем сделать анонимными функции sumInts, sumCubes, sumFactorials.

Возврат функции в качестве результата очень распространенное в ФП явление, поэтому для этих целей в Scala существует синтаксический сахар:

def sum(f: Int => Int)(a: Int, b: Int): Int =
	if (a > b) 0 else f(a) + sum(f)(a + 1, b)
		

Это определение sum полностью аналогично предыдущему, за исключением более удобной записи. Мы можем использовать столько списков аргументов, сколько нужно.

Типы ассоциативны справа, тут sum имеет тип:

(Int => Int) => (Int, Int) => Int == (Int => Int) => ((Int, Int) => Int)

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

def f(a1, ..., an) = E
	
def f = (a1 => (a2 => ... (an => E)...))
	

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

Примеры

Далее мы рассмотрим два примера, которые призваны продемонстрировать мощь функций высшего порядка.

MapReduce

Давайте решим следующие задачи:

  • напишем функцию product, работающую аналогично sum
  • выразим factorial через product
  • попробуем обобщить product и sum в виде функции mapReduce

И так, код product, factorial, mapReduce, умножение и сложение в терминах mapReduce:

def product(f: Int => Int)(a: Int, b: Int): Int =
	if (a > b) 1 else f(a) * product(f)(a + 1, b)
		
def factorial(n: Int) = product(x => x)(1, n)
	
def mapReduce(map: Int => Int, reduce: (Int, Int) => Int, 
	zero: Int)(a: Int, b: Int): Int =
	if (a > b) zero
	else reduce(map(a), mapReduce(map, reduce, zero)(a + 1, b))
		
def product_2(f: Int => Int)(a: Int, b: Int): Int =
	mapReduce(f, (x, y) => x * y, 1)(a, b)
		
def sum_2(f: Int => Int)(a: Int, b: Int): Int =
	mapReduce(f, (x, y) => x + y, 0)(a, b)
	

mapReduce демонстрирует одноименный паттерн программирования. Суть его заключается в том, что задача разбивается на подзадачи, которые обрабатываются отдельно функцией map, а затем результат комбинируется с помощью функции reduce. map может вычисляться параллельно и, возможно, на разных машинах. Функция reduce должна быть коммутативна (перестановка параметров не влияет на результат) и ассоциативна (порядок вызовов не важен). MapReduce очень мощный паттерн параллельной обработки данных.

Расчет квадратного корня

Фиксированной точкой функции f(x) называют такое a, что f(a) = a. Задачу расчета квадратного корня числа можно свести к задаче поиска фиксированной точки:

Очевидно что фиксированная точка f(x) = y/x и есть .

Фиксированную точку некоторых функции можно рассчитать с заданной точностью с помощью итеративного процесса вида: f(f(f(...f(x)...))). Вычисления завершаются когда изменения функции за шаг становятся меньше определенного порога точности. Напишем первую версию программы для вычисления :

val tolerance = 0.0001	//val - оптимизированный def.
			//Значение рассчитывается
			//один раз и связывается с
			//именем. Далее при вызове
			//сразу используется это значение.
			//Расчета тела функции не происходит

def isCloseEnough(x: Double, y: Double) = 
	abs((x - y) / x) / x < tolerance
		
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
	def iterate(guess: Double): Double = {
		val next = f(guess)		
		if (isCloseEnough(guess, next)) next 
		else iterate(next)
	}
		
	iterate(firstGuess)
}
	
def sqrt(y: Double) = fixedPoint(x => y/x)(1)
	
sqrt(2) 
	

Посмотрите и поймите этот красивый код. Потом можете запустить его на выполнение и убедиться что он зацикливается. Дело в том, что мы получим бесконечные осцилляции вокруг решения ~1.4142 (abs((x - y) / x) / x будет каждую итерацию принимать значения 1, 2, 1, 2), но ошибка никогда не станет меньше tolerance. Для устранения этой проблемы достаточно предотвратить слишком большие изменения в каждой итерации. Этого можно достичь взяв среднюю, по первоначальной формуле, оценку x на следующем шаге:

def sqrt(x: Double) = fixedPoint(x => (x + y/x) / 2)(1)
	

Мы получили формулу Герона. Теперь все работает. Оцените глубину изменений и простоту, с которой они были сделаны.

Организация данных

Сейчас миром правит объектно-ориентированное программирование (ООП), кто-то даже называет ООП парадигмой. В предыдущей статье я упомянул, что идеями ООП можно дополнить функциональное программирование. Давайте поговорим об этом.

Как известно, сила ООП заключается в трех словах: полиморфизм, наследование, инкапсуляция. В этот раз мы поговорим об инкапсуляции, наиболее здравой и полезной, на мой взгляд, идее.

ООП на примере

Начнем с примера. Мы хотим разработать математическую библиотеку для работы с рациональными числами. Рациональные числа, как известно, представимы в виде

x называется числитель (numerator), y - знаменатель (denomintaor). Давайте попробуем объявить функции для работы с рациональными числами:

def addRationalNumerator(n1: Int, d1: Int, n2: Int, d2: Int): Int
def addRationalDenominator(n1: Int, d1: Int, n2: Int, d2: Int): Int

Нам придется в программе хранить отдельно числители и знаменатели дробей. Лучшим решением было бы объединение числителя и знаменателя в одной структуре данных. К сожалению чистое функциональное программирование не позволяет ничего подобного. К счастью в Scala есть поддержка ООП и мы можем написать такой код:

class Rational(x: Int, y: Int) {
	def numerator = x
	def denominator = y
}
	

Тут мы видим две новых концепции:

  • Новый тип данных с именем Rational
  • функцию-конструктор с именем Rational, создающую элемент типа Rational

Тип данных в языках программирования можно рассматривать как множество элементов, отнесенных к этому типу. Элемент типа принято называть объектом класса, а тип данных классом. Стоит отметить что имя класса совпадает с именем конструктора. Конфликтов имен не происходит, так как в Scala имена типов и значений хранятся в различных пространствах имен.

Для создания объекта перед вызовом конструктора пишут ключевое слово new, например:

	new Rational(1, 2)
	

Для доступа к элементам объекта традиционно используется .:

val x = new Rational(1, 2)
x.numerator		// 1
x.denominator	// 2
	

Функции, объявленные в классе называются методами. В теле метода доступны все методы, объявленные в классе.

Инкапсуляция

Одной из важнейших концепций ООП является инкапсуляция. Эта концепция позволяет упростить программу посредством сокрытия не важных для пользователя класса данных. Другими словами инкапсуляция отделяет интерфейс (все что важно для пользователя) от реализации этого интерфейса (все что пользователю знать не нужно) и делает реализацию невидимой для пользователя. Без инкапсуляции невозможно построение больших программ.

Продемонстрируем инкапсуляцию данных на примере свойств numerator, denominator и функции toString:

	def toString = numerator + "/" + denominator
	

Видно, что numerator и denominator скрыты от пользователя метода toString.

Если внимательно посмотреть на наш класс, то можно увидеть что рациональные числа представляются не лучшим образом. Числитель и знаменатель могут быть не взаимно простыми числами. Чтобы исправить этот недостаток можно разделить числитель и знаменатель на их НОД:

class Rational(x: Int, y: Int) {
	require(y != 0, "denominator can't be 0") // Встроенная функция
						// В случае не выполнения утверждения
						// бросает IllegalArgumentException
	
	private def gcd(a: Int, b: Int): Int = 
		if (b == 0) a else gcd(b, a % b)
	
	def numerator = x / this.gcd(x, y) //this означает текущий объект
	def denominator = y / gcd(x, y) //this можно опускать
}
	

Функция gcd объявлена как private и будет доступна только внутри класса. На этом примере видна инкапсуляция поведения. Теперь мы можем воспользоваться плюсами инкапсуляции и поменять, например, тело numerator без изменения кода пользователя класса. Еще стоит отметить ключевое слово this. Для доступа к методу нужно указать имя объекта. Внутри объекта this означает собственное имя объекта, обычно это слово подразумевается и его можно опускать.

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

Сложение на Scala:

def add(that: Rational): Rational =
	new Rational(numerator * that.denominator + that.numerator * denominator,
		denominator * that.denominator)
	

Представьте реализацию подобной функции без механизмов инкапсуляции и оцените пользу от этой концепции.

ООП в функциональном программировании

Пришло время определить место ООП в функциональном программировании более формально и посмотреть как в нашей модели вычислений происходит создание объектов и вызов методов.

Для начала ответим на вопрос как работает new C(e1, ..., en). Конструктор с аргументами e1, ..., en вычисляется как обычная функция. Конструктор вычисляется и определяет методы. Код new C(e1, ..., en) превращается в объект. Тут мы видим что к термам кроме функций и элементарных типов относятся и объекты. Объекты можно рассматривать как именованную группу функций, имеющих общие аргументы. Для понимания давайте разберемся как происходит вызов метода. Пусть у нас есть класс:

	class C(x1, ..., xm) { ... def f(y1, ..., yn) = b ... }
	

где x1, ..., xm - аргументы класса, f(y1, ..., yn) - метод с n аргументами. Рассмотрим, что происходит в модели подстановок с кодом

new C(v1, ..., vm).f(w1, ..., wn)
->
[v1/x1, ..., vm/xm][w1/y1, ..., wn/yn][new C(v1, ..., vm)/this]b

тут происходит три подстановки в b:

  • подстановка аргументов класса v1, ..., vm вместо x1, ..., xm
  • подстановка аргументов функции w1, ..., wn вместо y1, ..., yn
  • подстановка объекта new C(v1, ..., vm) вместо this

Пару слов о последнем пункте. В императивных языках объект new C(v1, ..., vm) может содержать переменные и таким образом иметь состояние. Поэтому выполнять последнюю подстановку нельзя. В ФП объекты без состояния, поэтому проблем с последним пунктом нет.

Закрепим понимание места ООП в модели вычислений примером:

class Rational(x: Int, y: Int) {
	def numerator = x
	def denominator = y
		
	def add(that: Rational): Rational =
		new Rational(numerator * that.denominator + that.numerator * denominator,
			denominator * that.denominator)
}
	
new Rational(1, 2).sum(new Rational(2, 3))
-> [1/x, 2/y][new Rational(2, 3)/that][new Rational(1, 2)/this]
-> new Rational(
	new Rational(1, 2).numerator * new Rational(2, 3).denominator +
	new Rational(2, 3).numerator * new Rational(1, 2).denominator,
	new Rational(1, 2).denominator * new Rational(2, 3).denominator
)
-> new Rational(1 * 3 + 2 * 2, 2 * 3)
-> new Rational(7, 6)

Таким образом для поддержки инкапсуляции достаточно добавить объекты в наш словарь терминов (к уже введенным ранее функциям, числам и строкам).

Заключение

В этот раз мы расширили наш список инструментов для организации программ тремя новыми понятиями: функциями высшего порядка, каррированием и инкапсуляцией. Мы на практике попробовали построить несколько программ в функциональном стиле и, надеюсь, убедились в мощи ФП. Кроме того, для обеспечения инкапсуляции, мы ввели базовые сущности ООП - классы и объекты. В следующей статье мы продолжим знакомство с ООП в функциональном программировании и рассмотрим полиморфизм и наследование.