Функциональное мышление: Часть 3. Разработка программ в функциональном стиле

Фильтрация, unit-тестирование и другие приемы для повторного использования кода

В серии статей "Функциональное мышление" Нил Форд продолжает знакомить читателей с конструкциями и принципами функционального программирования. В этой статье будет рассмотрена версия классификатора чисел, написанная на языке Scala, и представлено краткое введение в unit-тестирование применительно к функциональному программированию. В статье будут изучены приемы "partial method application" (частичное применение метода) и "curring" (карринг), которые помогают создавать код с возможностью неоднократного использования, а также будет показано, как рекурсия "вписывается" в стиль функционального программирования.

Нил Форд, Архитектор приложений, ThoughtWorks

Нил Форд (Neal Ford) работает архитектором приложений в ThoughtWorks, революционной компании, предоставляющей профессиональные IT-услуги и помогающей талантливым людям по всему миру эффективнее использовать программное обеспечение. Он также является проектировщиком и разработчиком приложений, учебных материалов, журнальных статей, учебных курсов, видео/DVD-презентаций и автором книг "Разработка с Delphi: Объектно-ориентированный подход", "JBuilder 3 Unleashed" и "Искусство разработки Web-приложений на Java". Он специализируется на консультациях по построению широкомасштабных корпоративных приложений. Он также является общепризнанным докладчиком и выступал на многочисленных конференциях разработчиков по всему миру. С ним можно связаться по адресу: nford@thoughtworks.com.



05.05.2012

Об этой серии статей

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

В первой и второй статьях данной серии рассматривались некоторые вопросы функционального программирования и то, как они соотносятся с языком Java™ и близкими к нему языками. В этой статье мы продолжим исследование, представив Scala-версию классификатора чисел из прошлых статей и обсудив такие теоретические вопросы, как "карринг", "частичное применение" и "рекурсия".

Scala-версия классификатора чисел

Мы оставили Scala-версию классификатора чисел напоследок, так как в её синтаксисе меньше всего непонятных моментов, по крайней мере для Java-программистов. (Напомню требования к классификатору чисел: получив любое положительное целое число, большее 1, необходимо определить, является ли оно "совершенным", "избыточным" или "неполным"). Сумма всех делителей совершенного числа (за исключением самого числа) равна этому же числу. Для избыточного числа значение суммы делителей будет больше него, а для неполного числа – меньше. В листинге 1 приведена Scala-версия программы для решения данной задачи.

Листинг 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 до целевого числа и применяет к нему встроенный метод filter(), используя блок кода (указанный справа в круглых скобках) в качестве условия фильтрации (иными словами – предиката). Этот блок кода использует одно из уникальных преимуществ Scala - неявный параметр (implicit parameter), который позволяет использовать безымянный символ-заполнитель ("_") в случаях, когда не требуется создавать именованную переменную. Благодаря гибкости синтаксиса Scala метод filter можно вызвать таким же способом, как и оператор. Или можно воспользоваться другим стилем и вызвать его так:

(1 to number).filter((number % _ == 0))

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

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

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

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

Хотя я и не показывал unit-тесты для предыдущих версий программы, но все представленные примеры снабжены unit-тестами. Для языка Scala имеется библиотека ScalaTest, позволяющая создавать эффективные unit-тесты (см. раздел "Ресурсы"). В листинге 2 представлен первый unit-тест, написанный для проверки метода isPerfect() из листинга 1.

Листинг 2. Unit-тест для 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))
}

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

Листинг 3. Альтернативный тест для классификатора идеальных чисел
@Test def alternate_perfection() {
  assertEquals(List(6, 28, 496, 8128),
              (1 until 10000) filter (NumberClassifier.isPerfect(_)))
}

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


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

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

Другой способ достичь повторного использования кода называется каррингом (curring - в честь математика Хаскелла Карри (Haskell Curry), его имени также обязан своим названием язык программирования Хаскелл). Карринг изменяет функцию с несколькими аргументами таким образом, что её становится возможно вызвать как последовательность функций, каждая их которых принимает на вход единственный аргумент. Сходным приемом является частичное применение (partial application), когда одному или нескольким аргументам функции присваивается фиксированное значение, что порождает другую функцию меньшей арности, т.е. с меньшим количеством аргументов. Чтобы понять разницу между этими подходами, рассмотрим Groovy-код в листинге 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 определяется как блок кода, принимающий на вход два параметра. Применяя метод curry, встроенный в Groovy, я использую product в качестве строительного блока для двух новых блоков кода: quadrate и octate. Groovy позволяет легко вызвать блок кода: можно либо явно выполнить метод call(), либо воспользоваться упрощенным синтаксисом, поместив необходимые параметры в круглые скобки сразу за названием блока кода (например, octate(5)).

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

Листинг 5. Сравнение частичного применения с каррингом (в обоих случаях используется Groovy-метод 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 (который вычисляет площадь прямоугольника), фиксируя при этом один из размеров (h – высоту) равной 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 и использую частичное применение, чтобы объединить два метода в одно целое.

С помощью карринга и частичного применения можно достичь результатов, аналогичных тем, которые получаются при использовании шаблона проектирования Template Method. Например, можно создать блок кода incrementer (инкрементирующий переданное ему значение) поверх блока кода adder (складывающего два значения), как показано в листинге 7.

Листинг 7. Различные блоки кода
def adder = { x, y -> return x + y }
def incrementer = adder.curry(1)

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

Конечно, Scala поддерживает карринг, как показано во фрагменте документации 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() равным значению, использованному для создания блока кода. Когда я передаю блок кода, созданный при передаче целевого числа в качестве параметра, 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. Этот код следует основному шаблону, применяемому в функциональных языках для работы со списками. В данном случае предполагается, что список состоит из двух частей: элемент в начале списка ("голова" - head) и все остальные элементы. Во многих функциональных языках существуют специальные методы для итерирования по спискам, основанные на таком представлении. Метод filter() сначала проверяет, что список не пустой - это критически важное условие выхода для данного метода. Если список пустой, то просто выполняется команда return. В противном случае используется предикат с условием (p), переданный в качестве параметра. Если это условие равно true (т.е. элемент соответствует критерию фильтрации), то я возвращаю новый список, в котором текущий элемент используется в качестве головы списка, а уже отфильтрованные элементы – в качестве остальных элементов списка. Если же условие не выполняется, то возвращается новый список, состоящий только из отфильтрованных элементов (без первого элемента). Операторы для создания списков, присутствующие в Scala, позволяют в обоих случаях сделать условия возврата понятными и удобными для восприятия.

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


Заключение

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

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

Ресурсы

Научиться

Получить продукты и технологии

  • ScalaTest: библиотека для unit-тестирования исходного Java и Scala-кода.

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=813076
ArticleTitle=Функциональное мышление: Часть 3. Разработка программ в функциональном стиле
publish-date=05052012