Функциональное мышление

Часть 1. Функциональные возможности Groovy

Исследование возможностей Groovy

Comments

Серия контента:

Этот контент является частью # из серии # статей: Функциональное мышление

Следите за выходом новых статей этой серии.

Этот контент является частью серии:Функциональное мышление

Следите за выходом новых статей этой серии.

Признаюсь, мне никогда не хотелось вернуться к языкам программирования, в которых отсутствует автоматическая "уборка мусора". Я долгие годы проработал с языком C++ и ему подобными, и не собираюсь отказываться от удобств, предлагаемых современными языками. В этом и заключается история прогресса в области разработки ПО. Мы создаем уровни абстракции, чтобы обрабатывать (и скрывать) низкоуровневые подробности реализации. По мере роста вычислительной мощности компьютеров мы перекладываем все больше задач на языки программирования и среды исполнения. Всего десять лет назад разработчики избегали интерпретируемых языков, так как они считались слишком «медленными» для промышленных приложений, а сейчас использование подобных языков стало стандартной практикой. Многие возможности функциональных языков десять лет назад работали крайне медленно, но сегодня их использование имеет смысл, так как они оптимизируют время и усилия, затрачиваемые разработчиками.

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

Функциональные списки в Groovy

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

Альтернативный взгляд на списки

Если ваша основная работа связана с языком программирования С или ему подобными (включая Java), то, вы, скорее всего, представляете списки в виде индексированных коллекций. Подобная точка зрения упрощает итерирование по коллекции, даже если для этого индекс явно и не используется, как показано в Groovy-коде в листинге 1.

Листинг 1. Просмотр списка со скрытым использованием индексов
def perfectNumbers = [6, 28, 496, 8128]

def iterateList(listOfNums) {
  listOfNums.each { n ->
    println "${n}"
  }
}

iterateList(perfectNumbers)

В Groovy также имеется блок-итератор eachWithIndex(), который предоставляет индекс элемента в качестве параметра для вложенного блока кода в тех случаях, когда требуется прямой доступ к элементу. Хотя я и не использовал индекс в методе iterateList(), приведенном в листинге 1, я все равно рассматриваю список как упорядоченную коллекцию ячеек, как показано на рисунке 1.

Рисунок 1. Список как набор упорядоченных ячеек
Рисунок 1. Список как набор упорядоченных ячеек
Рисунок 1. Список как набор упорядоченных ячеек

В большинстве функциональных языков списки рассматриваются иначе, и, к счастью, Groovy также разделяет эту точку зрения. Вместо того чтобы рассматривать список как набор упорядоченных ячеек, представим его как комбинацию первого элемента списка ("начало" – head) и остальной части списка ("остаток" – tail), как показано на рисунке 2.

Рисунок 2. Список, состоящий из "начала" и "остальной части"
Рисунок 2. Список, состоящий из начала и остальной части
Рисунок 2. Список, состоящий из начала и остальной части

Если посмотреть на список с такого угла, то можно организовать итерирование по нему с помощью рекурсии, как показано в листинге 2.

Листинг 2. Просмотр списка с помощью рекурсии
def recurseList(listOfNums) {
  if (listOfNums.size == 0) return;
    println "${listOfNums.head()}"
    recurseList(listOfNums.tail())
}

recurseList(perfectNumbers)

В методе recurseList() в листинге 2 я сначала проверяю, что список, переданный в качестве параметра, не является пустым. Если список пустой (в нем нет элементов), то работа закончена и можно выполнить возврат. Если же в списке содержатся значения, то сначала я вывожу первый элемент списка (с помощью Groovy-метода head()), а затем рекурсивно вызываю метод recurseList() для оставшейся части списка.

У рекурсии существуют определенные технические ограничения, встроенные в платформу (см. раздел "Ресурсы"), так что подобное решение помогает не во всех ситуациях. Но оно вполне подходит для списков с небольшим числом элементов. Меня больше интересует влияние такого подхода, на структуру кода, в ожидании того момента, когда эти ограничения ослабеют или исчезнут вообще. С учетом этих недостатков преимущества рекурсивного подхода в первом приближении могут показаться неочевидными. Чтобы опровергнуть это представление, рассмотрим проблему фильтрации списка. В листинге 3 приведен пример фильтрующего метода, который принимает на вход список и предикат (булевское условие), определяющей принадлежность элемента к списку.

Листинг 3. Императивная фильтрация в Groovy
def filter(list, p) {
  def new_list = []
  list.each { i -> 
    if (p(i))
      new_list << i
  }
  new_list
}

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

l = filter(1..20, modBy2)

Код в листинге 3 не должен вызвать вопросов. Я создал промежуточную переменную для хранения отобранных элементов, выполнил итерирование по списку, проверяя каждый элемент на соответствие указанному предикату, а в конце вернул список с отфильтрованными элементами. При вызове метода filter() я указал блок кода, содержащий критерий фильтрации.

В листинге 4 приведена рекурсивная реализация метода filter() из листинга 3.

Листинг 4. Рекурсивная фильтрация в Groovy
def filter(list, p) {
  if (list.size() == 0) return list
  if (p(list.head()))
    [] + list.head() + filter(list.tail(), p)
  else 
    filter(list.tail(), p)
}

l = filter(1..20, {n-> n % 2 == 0})

В методе filter() в листинге 4 сначала проверяется размер переданного списка, и если он пустой, то выполняется выход из метода. Затем я проверяю первый элемент списка на соответствие фильтрующему предикату, и если он соответствует условию, я добавляю его в список с результатами (этот список изначально пуст, чтобы гарантировать, что будут возвращаться только подходящие значения). После этого я рекурсивно вызываю метод filter(), передавая в качестве параметра остальную часть списка.

Разница между кодом из листингов 3 и 4 заключается в ответе на вопрос: «кто отвечает за сохранение состояния?» В императивной версии это обязанность ложится на меня. Я должен создать новую переменную new_list и добавлять в неё элементы, а затем вернуть после завершения метода. В рекурсивной версии язык программирования берет на себя обработку возвращаемого значения, строя его на основе стека по мере возвращения значений из рекурсивно вызванных методов. Отметим, что при выходе из метода filter() в листинге 4 вызывается команда return, которая используется для создания промежуточного значения на основе стека.

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

Изменив свою точку зрения относительно списков, мы сможем по-новому взглянуть и на такие аспекты, как размер списка и его область видимости.

Списки с отложенной загрузкой элементов в Groovy

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

В листинге 5 приведен пример использования «ленивого» списка в Groovy, а затем мы посмотрим, как он реализуется.

Листинг 5. Использование "ленивого" списка в Groovy
def prepend(val, closure) { new LazyList(val, closure) }

def integers(n) { prepend(n, { integers(n + 1) }) }

@Test
public void lazy_list_acts_like_a_list() {
  def naturalNumbers = integers(1)
  assertEquals('1 2 3 4 5 6 7 8 9 10', 
      naturalNumbers.getHead(10).join(' '))
  def evenNumbers = naturalNumbers.filter { it % 2 == 0 }
  assertEquals('2 4 6 8 10 12 14 16 18 20', 
      evenNumbers.getHead(10).join(' '))
}

Первый метод prepend() в листинге 5 создает новый объект типа LazyList, позволяя добавлять в него значения. Следующий метод integers() возвращает список с целыми числами, созданный с помощью метода prepend(). В метод prepend() передаются два параметра: исходное состояние списка и блок кода, использующийся для генерации следующего значения. Метод integers() действует как "фабрика", создающая "ленивый" список, содержащий целые числа, используя первое значение в списке для вычисления последующих значений.

Для извлечения значений из списка я вызываю метод getHead(), который возвращает указанное число значений с начала списка. В листинге 5 переменная naturalNumbers – это "бесконечная" последовательность всех целых чисел. Чтобы получить некоторые из них, я вызываю метод getHead() и указываю, сколько элементов необходимо вернуть. Как видно из проверки, мне возвращается список из первых десяти натуральных чисел (от 1 до 10). С помощью метода filter() я получаю "бесконечный" список, содержащий только четные числа, и использую метод getHead(), чтобы получить первые десять четных чисел.

В листинге 6 приведен исходный код класса LazyList.

Листинг 6. Реализация класса LazyList
class LazyList {
  private head, tail

  LazyList(head, tail) {
    this.head = head;
    this.tail = tail
  }

  def LazyList getTail() { tail ? tail() : null }

  def List getHead(n) {
    def valuesFromHead = [];
    def current = this
    n.times {
      valuesFromHead << current.head
      current = current.tail
    }
    valuesFromHead
  }

  def LazyList filter(Closure p) {
    if (p(head))
      p.owner.prepend(head, { getTail().filter(p) })
    else
      getTail().filter(p)
  }
}

Данный список содержит атрибуты head ("начало") и tail ("остаток"), устанавливаемые в конструкторе. Метод getTail() проверяет, что значение атрибута tail() не равно null, и, если это так, выполняет код, содержащийся в данном атрибуте. Метод getHead() по одному собирает элементы, которые необходимо вернуть, извлекая существующий элемент из "начала" списка (атрибут head) и заставляя "остаток" (атрибут tail) сгенерировать следующее значение. Вызов n.times {} повторяет эту операцию столько раз, сколько было запрошено элементов, и в конце метод getHead() возвращает собранные значения.

В методе filter() в листинге 5 используется такой же рекурсивный подход, как и в листинге 4, но в данном случае он реализован в виде составной части списка, а не самостоятельной функции.

Списки с отложенным созданием элементов существуют и в Java (см. раздел "Ресурсы"), но в языках, изначально обладающих функциональными возможностями, создавать их гораздо проще. Подобные списки отлично подходят для ситуаций, когда создание ресурсов связано со значительными расходами, как, например, при создании списка совершенных чисел.

Список с отложенным созданием элементов, содержащий совершенные числа

Если вы читали предыдущие статьи из этой серии, то наверняка помните мой любимый пример — программу для поиска совершенных чисел (см. статью "Функциональное мышление. Часть 1"). Одним из недостатков всех представленных ранее версий этой программы была необходимость явного указания числа, тип которого нужно было определить. Теперь я хочу создать список, который будет создавать и возвращать совершенные числа по мере необходимости. Для этого я написал компактную программу в функциональном стиле для поиска совершенных чисел с поддержкой списков с отложенным созданием элементов, исходный код которой приведен в листинге 7.

Листинг 7. Упрощенная версия классификатора чисел, содержащая метод nextPerfectNumberFrom
class NumberClassifier {
  static def factorsOf(number) {
      (1..number).findAll { i -> number % i == 0 }
  }

  static def isPerfect(number) {
      factorsOf(number).inject(0, {i, j -> i + j}) == 2 * number
  }

  static def nextPerfectNumberFrom(n) {
    while (! isPerfect(++n)) ;
    n
  }
}

Если код в методах factorsOf() и isPerfect() кажется вам непонятным, вы можете найти пояснения по этим методам в предыдущей статье. Новый метод nextPerfectNumber() использует метод isPerfect() для поиска следующего совершенного числа, которое должно быть больше значения, переданного в качестве параметра. На выполнение этого метода уйдет много времени даже для маленьких значений (особенно если учесть, что код не оптимизирован), так как совершенных чисел существует не так уж и много.

Используя эту новую версию классификатора чисел, я могу создать "ленивый" список совершенных чисел, как показано в листинге 8.

Листинг 8. Список совершенных чисел с отложенным созданием элементов
def perfectNumbers(n) { 
  prepend(n, 
    { perfectNumbers(nextPerfectNumberFrom(n)) }) };

@Test
public void infinite_perfect_number_sequence() {
  def perfectNumbers = perfectNumbers(nextPerfectNumberFrom(1))
  assertEquals([6, 28, 496], perfectNumbers.getHead(3))
}

С помощью метода prepend(), объявленного в листинге 5, я создаю список совершенных чисел, используя исходное значение в качестве "начала" и блок кода с функциональностью для вычисления следующего совершенного числа в качестве "остатка". Я инициализирую список первым совершенным числом после единицы (метод NumberClassifier.nextPerfectNumberFrom() можно легко вызвать напрямую благодаря конструкции static import). В конце я вызываю метод getHead(), чтобы получить три первых совершенных числа.

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

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

Заключение

Одним из способов радикально повысить продуктивность разработчиков является построение эффективных абстракций, скрывающих ненужные детали. Мы бы не смогли достичь текущего уровня развития в разработке ПО, если бы по-прежнему писали код в терминах двоичных "нолей" и "единиц". Одним из основных аспектов функциональных языков является стремление абстрагировать разработчика от низкоуровневых подробностей реализации. Современные динамические языки на основе JVM уже обладают подобными возможностями. В этой статье было показано, как изменение точки зрения на принцип организации списков позволяет переложить сохранение состояния в процессе итерации на язык программирования. А когда вы научитесь думать о списках в терминах "начала" и "остальной части", то сможете использовать такие подходы, как списки с отложенным созданием элементов и бесконечные последовательности.

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


Ресурсы для скачивания


Похожие темы


Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=828180
ArticleTitle=Функциональное мышление: Часть 1. Функциональные возможности Groovy
publish-date=07302012