Functional thinking: Thinking functionally, Part 3

В первой и второй частях “Функционального мышления” я рассмотрел некоторые вопросы функционального программирования а также то, как они относятся к Java и связанным с ней языкам. Эта часть продолжит мой обзор, в ней я покажу версию классификатора чисел из предыдущих частей на языке Scala и обсужу некоторые теоретические вопросы, такие как карринг, частичное применение и рекурсия.

Классификатор чисел на Scala

Я приберёг Scala версию напоследок так как она содержит в себе минимум мистического синтаксиса, по крайней мере для Java программистов. (Напоминаю требования к классификатору: Вам нужно классифицировать его как совершенное, избыточное или недостаточное. Совершенным является то число, чьи делители, за исключением его самого, как делителя, в сумме ему равны. Подобно тому, сумма делителей избыточного числа выше его самого, а недостаточного — меньше.)

Листинг 1. Классификатор чисел на Scala

package com.nealford.conf.ft.numberclassifier

object NumberClassifier {

  def isFactor(number: Int, potentialFactor: Int) =
    number % potentialFactor == 0

  def factors(number: Int) =
    (1 to number) filter (number % _ == 0)

  def sum(factors: Seq[Int]) =
    factors.foldLeft(0)(_ + _)

  def isPerfect(number: Int) =
    sum(factors(number)) - number == number

  def isAbundant(number: Int) =
    sum(factors(number)) - number > number

  def isDeficient(number: Int) =
    sum(factors(number)) - number < number
}

Даже если Вы никогда не видели Scala до этого момента, этот код должен быть легко читаем. Как и раньше два интересующих нас метода factors() и sum(). Метод factors() принимает список чисел от 1 до данного числа и применяет к нему стандартный метод библиотеки Scala filter(), используя блок кода справа как критерий фильтрации (иначе называемый предикатом). В блоке кода применяется специальная конструкция — неявные параметры*, которая позволяет использовать символ _ вместо имени параметра, когда в нём нет нужды. Благодаря гибкости синтаксиса Scala Вы можете вызвать метод filter() так же как и оператор. Конструкция (1 to number).filter((number % _ == 0)) тоже сработает, если Вам она покажется более удобной.

Метод sum использует уже знакомую нам операцию левой свёртки (fold left) (реализованную в Scala как метод foldLeft()). Мне не нужны имена для параметров в данном случае, так что я использую символ _ вместо имени, что даёт мне более простой и понятный синтаксис для блока кода. Метод foldLeft() делает то же, что и сходно названный метод из библиотеки Functional Java, который фигурировал в первой части:

1. Берёт начальное значение и комбинирует его с помощью заданной операции с первым элементом списка.
2. Берёт результат и применяет ту же операцию к следующему элементу списка.
3. Продолжает это делать пока список не кончится.

Это обобщённая версия применения такой операции как сложение к списку чисел: начать с 0, добавить первый элемент, взять результат и добавить к нему второй и продолжать до конца списка.

Юнит-тестирование

Несмотря на то, что в предыдущей версии я не показал юнит-тестов, все примеры тестируются. Для Scala доступна удобная библиотека для юнит-тестирования — ScalaTest. Листинг 2 показывает первый тест который я написал для проверки метода isPerfect() из Листинга 1:

Листинг 2. Юнит-тест для классификатора чисел на Scala

@Test def negative_perfection() {
  for (i <- 1 until 10000)
    if (Set(6, 28, 496, 8128).contains(i))
      assertTrue(NumberClassifier.isPerfect(i))
    else
      assertFalse(NumberClassifier.isPerfect(i))
}

Однако, также как и Вы, я пытаюсь научиться мыслить более функционально, так что код из листинга два мне не нравиться по двум причинам. Во-первых, он сам выполняет итерацию, это демонстрирует императивный подход к решению задачи. Во-вторых, мне на самом деле не важна вторая ветка в операторе if. Какую проблему я пытаюсь решить? Я должен быть уверен, что мой классификатор не определяет несовершенное число как совершенное. Листинг 3 показывает решение этой проблемы, но в немного другой формулировке.

Листинг 3. Альтернативный юнит-тест для классификатора чисел на Scala

@Test def alternate_perfection() {
  assertEquals(List(6, 28, 496, 8128),
              (1 until 10000) filter (NumberClassifier.isPerfect(_)))
}

В Листинге 3 проверяется что список чисел от 1 до 100 00 которые признаны совершенными и список известных совершенных чисел равны. Функциональное мышление расширяет не только Ваши подходы к программированию, но и то как Вы тестируете Ваш код.

Частичное применение и карринг

Функциональный подход к фильтрации списков, который я продемонстрировал выше, весьма распространён среди функциональных языков и библиотек. Использование передачи кода как параметра (в методе filter() в Листинге 3) показывает “другой” подход к повторному использованию. Если Вы пришли из старого, определяемого паттернами проектирования, объектно-ориентированного мира, сравните этот подход с паттерном “Шаблонный метод” из книги “Шаблоны проектирования”**. Он определяет заготовку алгоритма в базовом классе, применяя абстрактные методы для того, чтобы отложить определение деталей до момента создания наследников. Функциональный подход позволяет Вам передавать операции как параметры, и применять их надлежащим образом внутри метода.

Ещё один способ добиться повторного использования — это карринг. Названный в честь математика Хаскела Карри (в его честь заодно назван язык программирования Хаскелл), карринг — это трансформация функции многих параметров в цепочку функций одного параметра. Он тесно связан с частичным применением — техникой фиксации значения одного или нескольких аргументов функции ведущей к созданию новой функции меньшей арности. Для того чтобы понять разницу между ними давайте посмотрим на код в Листинге 4, который иллюстрирует карринг.

Листинг 4. Карринг в Groovy

def product = { x, y -> return x * y }

def quadrate = product.curry(4)
def octate = product.curry(8) 

println "4x4: ${quadrate.call(4)}"
println "5x8: ${octate(5)}

В Листинге 4 я определил product как блок кода, принимающий два параметра. С помощью встроенного метода groovy curry(), я использую product как базовый элемент для создания двух новых блоков кода quadrate и octate. Groovy делает вызов кода очень простым: можно или явно вызвать метод call(), или использовать предоставляемый языком синтаксический сахар — пару скобок.

Частичное применение более общая техника, которая повторяет карринг, но не ограничивает получаемую в результате функцию по числу аргументов. Groovy использует метод curry() для реализации обеих техник как показано в Листинге 5:

Листинг 5. Сравнение частичного применения и карринга в Groovy c использованием метода curry

def volume = { h, w, l -> return h * w * l }
def area = volume.curry(1)
def lengthPA = volume.curry(1, 1) //partial application
def lengthC = volume.curry(1).curry(1) // currying

println "The volume of the 2x3x4 rectangular solid is ${volume(2, 3, 4)}"
println "The area of the 3x4 rectangle is ${area(3, 4)}"
println "The length of the 6 line is ${lengthPA(6)}"
println "The length of the 6 line via curried function is ${lengthC(6)}"

Блок кода volume в Листинге 5 вычисляет объём параллелепипеда по хорошо известной формуле. Я создаю блок кода area (который вычисляет площадь прямоугольника) фиксируя первый аргумент volume на 1. Чтобы использовать volume как основу для блока который вернёт длину линии, я могу воспользоваться как частичным применением так и каррингом. lengthPA использует частичное применение фиксируя два первых параметра на значении 1. lengthC дважды применяет карринг для получения того-же результата. Разница очень тонка, а результаты одинаковы, однако если Вы воспользуетесь терминами карринг и частичное применение как синонимами рядом с настоящим функциональным программистом, то вам наверняка укажут на ошибку***.

Функциональное программирование даёт вам новые инструменты для достижение тех же целей, что и императивные языки. Взаимоотношение этих инструментов хорошо изучено. Ранее, я показал пример использования композиции как инструмента повторного использования. Так что Вас не должна удивить возможность сочетания карринга и композиции. Посмотрите на Groovy код в Листинге 6:

Листинг 6. Композиция и частичное применение

def composite = { f, g, x -> return f(g(x)) }
def thirtyTwoer = composite.curry(quadrate, octate)

println "composition of curried functions yields ${thirtyTwoer(2)}"

В Листинге 6 я создаю блок кода composite, который совмещает в себе две функции. С помощью этого блока я создаю thirtyTwoer используя частичное применения для того, чтобы соединить два метода вместе.

Частичное применение и карринг позволяют Вам добиться результатов, похожих на механизмы вроде паттерна Шаблонный метод. Например, Вы можете создать блок кода incrementer просто достраивая блок adder как в показано в Листинге 7:

Листинг 7. Достраивание функций

def adder = { x, y -> return x + y }
def incrementer = adder.curry(1)

println "increment 7: ${incrementer(7)}"

Scala, естественно, поддерживает карринг, как показано в примере из документации, приведённом в Листинге 8:

Листинг 8. Карринг в Scala

object CurryTest extends Application {

  def filter(xs: List[Int], p: Int => Boolean): List[Int] =
    if (xs.isEmpty) xs
    else if (p(xs.head)) xs.head :: filter(xs.tail, p)
    else filter(xs.tail, p)

  def dividesBy(n: Int)(x: Int) = ((x % n) == 0)

  val nums = List(1, 2, 3, 4, 5, 6, 7, 8)
  println(filter(nums, dividesBy(2)))
  println(filter(nums, dividesBy(3)))
}

Код в Листинге 8 демонстрирует как реализовать метод dividesBy() с помощью метода filter(). Я передаю анонимную функцию методу filter(), применяя карринг для того, чтобы зафиксировать первый параметр dividesBy() на значении, использованном при создании этого блока. Когда я передаю число методу dividesBy(), Scala автоматически создаёт новую функцию применяя каррирование.

Фильтрация через рекурсию

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

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

Листинг 9. Фильтрация в Groovy

def filter(list, criteria) {
  def new_list = []
  list.each { i -> 
    if (criteria(i))
      new_list << i
  }
  return new_list
}

modBy2 = { n -> n % 2 == 0 }

l = filter(1..20, modBy2)
println l

Метод filter() в Листинге 9 принимает на вход список и критерий отбора (блок кода). Внутри он перемещается по списоку добавляя в новый список очередной элемент если он соответствует критерию.

Давайте теперь вернёмся к Листингу 8, который является рекурсивной реализацией фильтра на Scala. Он следует стандартному паттерну функциональных языков для работы со списками. Мы рассматриваем список как сочетание двух элементов: значения в начале (головы) и списка остальных элементов. Многие функциональные языки имеют специальные методы для обхода списков с использованием этой идиомы. Метод filter() сначала проверяет является ли список пустым — это необходимое условие для выхода из рекурсии. Если список пуст, то просто выходим из метода, если нет — вычисляем значение условия, переданного в качестве параметра. Если это значение выполнено (что означает, что этот элемент хотят видеть в списке на выходе) — возвращаем новый список состоящий из этого элемента и отфильтрованного списка оставшихся элементов. Если условие не выполнено — то возвращаем отфильтрованный список оставшихся элементов (исключая голову). Оператор создания списка языка Scala обеспечивает нам хорошую читаемость и лёгкое восприятие обоих случаев.

Мне кажется, что Вы сейчас не используете рекурсию в принципе — она вообще не входит в Ваш набор инструментов. Это, однако, вызвано в значительной мере тем, что императивные языки слабо её поддерживают, делая её применение сложнее, чем оно должно быть. Добавляя простой синтаксис и поддержку рекурсии, функциональные языки делают её ещё одним простым способом повторного использования кода.

Заключение

Эта часть завершает мой обзор особенностей мира функционального мышления. По совпадению, большая часть этой статьи была о фильтрации, показывала массу способов её использования и реализации. Но это вполне ожидаемо. Многие функциональные парадигмы построены вокруг списков потому что программирование часто представляет из себя обработку списков объектов. Логично создавать языки и библиотеки имеющие мощные средства работы со списками.

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

Примечания

* — Кажется тут автор допустил ошибку. Конструкция _ вместо имени связанной переменной в замыкании называется синтаксисом заместителя для анонимной финкции (Placeholder Syntax for Anonymous Functions), а не неявным параметром (implicit parameter). Неявный параметр вводится ключевым словом implicit в сигнатуре функции и имеет совершенно другую семантику.

** — Русский перевод формально назывался «Приемы объектно-ориентированного проектирования». Я не стал использовать его в тексте, так как весьма не многие узнают по нему книгу.

*** — Примеры в этом разделе, выглядят немного запутанными. Я советую смотреть на определения терминов карринг и частичное применение в начале раздела, и не воспринимать эти примеры очень серьёзно.

P.S. Спасибо sndl за оказанную помощь при переводе и саму идею заняться этой серией