Функциональное мышление: Различные подходы к выполнению стандартных преобразований

Одни и те же операции могут называться по-разному в разных языках и инфраструктурах

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

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

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



25.04.2013

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

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

Подход к повторному использованию кода в функциональных языках программирования отличается от используемого в объектно-ориентированных языках, как я уже рассказывал в статье "Связывание и композиция, часть 2". Объектно-ориентированные языки предпочитают иметь множество структур данных и множество методов, а функциональные языки объявляют небольшое количество структур данных и множество методов. Объектно-ориентированные языки побуждают создавать методы, специфические для конкретных классов, благодаря чему можно выявить повторяющиеся шаблоны для последующего повторного использования. Функциональные языки помогают добиться повторного использования кода, побуждая применять стандартные преобразования к структурам данным и используя функции высшего порядка для адаптации поведения для конкретных случаев.

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

Целью данной статьи является создание "словаря" для перевода терминов функционального программирования. Я возьму простую проблему, для решения которой необходимо прибегнуть к принятию решений (decision) и циклическому выполнению действий (iteration), и подготовлю её решение на пяти языках (Java, Groovy, Clojure, Jruby и Scala) и двух функциональных инфраструктурах (Functional Java и Totally Lazy) для языка Java (см. раздел "Ресурсы"). Хотя реализация во всех случаях и совпадает, но её детали для различных языков могут существенно различаться.

Реализация на чистом Java

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

В листинге 1 приведена простая реализация на языке Java.

Листинг 1. Программа на языке Java для определения простоты числа
public class PrimeNumberClassifier {
    private Integer number;

    public PrimeNumberClassifier(int number) {
        this.number = number;
    }

    public boolean isFactor(int potential) {
        return number % potential == 0;
    }

    public Set<Integer> getFactors() {
        Set<Integer> factors = new HashSet<Integer>();
        factors.add(1);
        factors.add(number);
        for (Integer i = 2; i < number; i++)
            if (isFactor(i))
                factors.add(i);
        return factors;
    }

    public int sumFactors() {
        int sum = 0;
        for (int i : getFactors())
            sum += i;
        return sum;
    }

    public boolean isPrime() {
        return sumFactors() == number + 1;
    }
}

Если вы читали предыдущие статьи из цикла "Функциональное мышление", то наверняка узнали алгоритм, используемый в методе getFactors() в листинге 1. Его ядром является метод isFactor(), отбирающий подходящие делители.


Определение простого числа в Groovy

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

Листинг 2. Определение простоты числа в Groovy
class PrimeNumberClassifier {
  private int number;

  PrimeNumberClassifier(int number) {
    this.number = number
  }

  public def isFactor(int potential) {
    number % potential == 0;
  }

  public def getFactors() {
    (1..number).findAll { isFactor(it) }.toSet()
  }

  public def sumFactors() {
    getFactors().inject(0, {i, j -> i + j})
  }

  public def isPrime() {
    sumFactors() == number + 1
  }
}

С методами, представленными в листинге 2, произошли серьёзные изменения по сравнению с их аналогами из листинга 1, не считая смены синтаксиса с Java на Groovy. Метод getFactors() использует Groovy-класс Range, чтобы представить подходящие числа. Метод findAll() применяет блок кода к каждому элементу в коллекции, возвращая список, содержащий только те элементы, для которых данный блок кода вернул true. Блок кода принимает единственный параметр, в котором передаётся исследуемый параметр. Я использовал удобное сокращение из арсенала Groovy, чтобы сделать этот блок ещё короче. Например, блок кода можно было записать как (1..number).findAdd {i-> isFactor(i) }, но повторное упоминание параметра является лишним. Groovy предлагает показанный в листинге 2 вариант, позволяющий заменить единственный параметр неявной переменной it.

В листинге 2 также стоит отметить метод sumFactors(). Используя набор чисел, сгенерированный методом getFactors(), я вызываю метод inject(), который относится к Groovy-методам для работы с коллекциями и выполняет операцию свёртывания (fold). Метод inject соединяет все элементы в коллекции с помощью блока кода, переданного во втором параметре, используя первый параметр в качестве исходного значения. В листинге 2 в этом параметре находится блок кода {i, j-> i + j}, возвращающий сумму двух чисел. Метод inject() применяет этот блок, начиная с первого элемента, к каждому элементу в коллекции, суммируя всю последовательность чисел.

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


Определение простого числа в Scala

В листинге 3 представлена Scala-версия программы для определения простоты числа.

Листинг 3. Определение простоты числа в Scala
object PrimeNumberClassifier {
  def isFactor(number: Int, potentialFactor: Int) =
    number % potentialFactor == 0

  def factors(number: Int) =
    (1 to number) filter (isFactor(number, _))

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

  def isPrime(number: Int) =
    sum(factors(number)) == number + 1
}

Помимо того, что версия программы на Scala получилась гораздо короче, она отличается от предыдущих примеров и в других аспектах. Так как мне требуется только один экземпляр, то я могу реализовать его сразу в виде объекта, а не класса. В методе factors() используется такая же реализация, как и в Groovy-примере в листинге 2, но с другим синтаксисом. Я применяю метод filter (Scala-aналог метода findAll() из Groovy) к диапазону чисел (1 to number) и использую метод isFactor(), объявленный в начале листинга 3, в качестве предиката. В Scala также существует "заполнитель" (placeholder) для параметров — символ "_".

Метод sum в листинге 3 использует Scala-метод foldLeft(), который аналогичен Groovy-методу inject. В данном случае я использую нуль в качестве исходного значения и "заполнители" для обоих параметров.


Определение простого числа в Clojure

Язык Clojure – это современная реализация Lisp, работающая поверх виртуальной Java-машины, поэтому его синтаксис разительно отличается от уже показанных примеров.

Листинг 4. Определение простоты числа в Clojure
(ns prime)

(defn factor? [n, potential]
  (zero? (rem n potential)))

(defn factors [n]
  (filter #(factor? n %) (range 1 (+ n 1))))

(defn sum-factors [n]
  (reduce + (factors n)))

(defn prime? [n]
  (= (inc n) (sum-factors n)))

Хотя методы в листинге 4 и выглядят незнакомыми для Java-программистов, но показанный код реализует всё тот же известный алгоритм. Метод (factor?) проверяет, что остаток от деления (Clojure-функция rem) равен нулю. Метод (factors) использует Clojure-метод (filter), который принимает два параметра. В первом параметре передается блок кода, который будет использоваться в качестве предиката и выполняться для каждого элемента. Этот блок будет возвращать true в случае, если ему было передано значение соответствующее указанному критерию. В коде #(factor? N %) с помощью подстановочного параметра % определяется анонимная Clojure-функция. Во втором параметре в функцию (filter) передаётся коллекция, которую необходимо отфильтровать, в данном случае диапазон чисел от 1 до исследуемого числа плюс 1 (последний элемент при этом исключается из диапазона и не обрабатывается).

Метод (sum-factors) в листинге 4 использует Clojure-метод (reduce), аналог метода inject() в Groovy или метода foldLeft() в Scala. В данном случае в качестве операции используется простой оператор сложения "+", который в Clojure не отличается от любого другого метода, принимающего на вход два параметра и возвращающего результат.

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


Определение простого числа в JRuby

JRuby – это работающая поверх JVM реализация языка Ruby, в котором также накопилось большое количество функциональных конструкций. Рассмотрим (J)Ruby-версию программы для определения простоты числа, приведённую в листинге 5.

Листинг 5. Определение простоты числа в JRuby
class PrimeNumberClassifier
  def initialize(num)
    @num = num
  end

  def factor?(potential)
    @num % potential == 0
  end

  def factors
    (1..@num).select { |i| factor?(i) }
  end
    
  def sum_factors
    factors.reduce(0, :+)
  end

  def prime?
    (sum_factors == @num + 1)
  end
end

В методе factors в листинге 5 используется метод select, который является аналогом метода findAll в Groovy и метода filter в Scala и Clojure. Одна из удобных возможностей JRuby – это создание псевдонимов (alias) для методов, которые позволяют давать методам имена, соответствующие контексту их использования. Так, в JRuby имеется псевдоним find_all для метода select, однако он обычно не используется в классическом JRuby-программировании.

Для метода sum_factors в листинге 5 я использую JRuby-метод reduce, аналоги которого имеются и в других языках. В JRuby, также как и в Clojure, операторы — это методы с названиями-символами; так, Ruby позволяет мне указать имя метода plus с помощью его символа +. Для удобства восприятия в Ruby и Clojure к именам функций, которые должны возвращать булевские значения, можно добавлять знак вопроса "?". Наконец, для большей согласованности в Ruby имеется метод inject, являющийся псевдонимом для метода reduce.


Определение простого числа в Functional Java

Некоторые библиотеки для функционального программирования дополняют функциональными конструкциями сам язык Java, чтобы не оставить «за бортом» программистов, по прежнему использующих этот язык. К таким инфраструктурам относится Functional Java; в листинге 6 приведена программа для определения простоты числа, написанная на Functional Java.

Листинг 6. Определение простоты числа в Functional Java
public class FjPrimeNumberClassifier {
    private int number;

    public FjPrimeNumberClassifier(int number) {
        this.number = number;
    }

    public boolean isFactor(int potential) {
        return number % potential == 0;
    }

    public List<Integer> getFactors() {
        return range(1, number + 1)
                .filter(new F<Integer, Boolean>() {
                    public Boolean f(final Integer i) {
                        return isFactor(i);
                    }
                });
    }

    public int sumFactors() {
        return getFactors().foldLeft(fj.function.Integers.add, 0);
    }

    public boolean isPrime() {
        return sumFactors() == number + 1;
    }
}

Метод getFactors() в листинге 6 применяет метод filter() к диапазону чисел (последний элемент диапазона исключается, как и в Clojure, поэтому в определении диапазона указано number+1). Поскольку в Java на данный момент отсутствуют функции высшего порядка, Functional Java обходит это ограничение с помощью экземпляров анонимных вложенных классов, основанных на встроенном классе F; при этом используемые типы параметризуются с помощью дженериков Java.

Как и в языке Scala, в Functional Java имеется метод foldLeft(), принимающий на вход определённый блок кода, который суммирует числа, и стартовое значение.


Определение простоты числа в Totally Lazy

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

Листинг 7. Определение простоты числа в Totally Lazy
public class TlPrimeNumberClassifier {
    private int number;

    public TlPrimeNumberClassifier(int number) {
        this.number = number;
    }

    public boolean isFactor(Integer potential) {
        return (number % potential) == 0;
    }

    private List<Integer> listOfPotentialFactors() {
        List<Integer> results = new ArrayList<Integer>();
        for (int i = 1; i <= number + 1; i++)
            results.add(i);
        return results;
    }

    public boolean isPrime() {
        return (this.number + 1) ==
            Sequences.init(listOfPotentialFactors())
                     .filter(new Predicate<Integer>() {
                         @Override
                         public boolean matches(Integer other) {
                             return isFactor(other);
                      }})
                     .foldLeft(0, sum())
                     .intValue();
    }
}

Метод isPrime() в листинге 7 использует класс Sequences, инициализированный списком потенциальных делителей (в который входят все числа от 1 до целевого числа), а затем применяет метод filter(). В Totally Lazy метод filter() получает на вход потомка класса Predicate (множество потомков данного класса уже реализованы для таких стандартных ситуаций). В данном примере я переопределяю метод matches(), который будет использовать метод isFactor() для определения того, соответствует число критерию или нет. После этого я получаю список делителей и применяю метод foldLeft() вместе с вложенным методом sum в качестве параметра.

В листинге 7 основную работу выполняет метод isPrime. На самом деле тот факт, что все структуры данных в Totally Lazy являются структурами с отложенным исполнением, иногда усложняет их совместное использование. Рассмотрим версию метода getFactors(), показанную в листинге 8.

Листинг 8. Метод getFactors с отложенным итерированием
public Iterator<Integer> getFactors() {
    return Sequences
            .init(listOfPotentialFactors())
            .filter(new Predicate<Integer>() {
                @Override
                public boolean matches(Integer other) {
                    return isFactor(other);
                }
            })
            .iterator();
}

Метод getFactors() в листинге 8 возвращает объект типа Iterator<Integer>, но на самом деле это итератор с отложенным исполнением, поэтому значения появятся в коллекции только тогда, когда вы будете выполнять по ней итерирование. Эта особенность значительно усложняет тестирование коллекций с отложенным исполнением. В листинге 9 приведён unit-тест для Totally Lazy примера из листинга 8.

Листинг 9. Тестирование коллекции в Totally Lazy
@Test
public void factors() {
    TlPrimeNumberClassifier pnc = new TlPrimeNumberClassifier(6);
    List<Integer> expected = new ArrayList<Integer>() {{
        add(1);
        add(2);
        add(3);
        add(6);
    }};
    Iterator<Integer> actual = pnc.getFactors();
    assertTrue(actual.hasNext());
    int count = 0;
    for (int i = 0; actual.hasNext(); i++) {
        assertEquals(expected.get(i), actual.next());
        count++;
    }
    assertTrue(count == expected.size());
}

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

Хотя в Totally Lazy можно написать версию программы, структурированную так же, как и предыдущие варианты, вы, скорее всего, "завязнете" в запутанных структурах данных вроде <Iterator<Iterator<Number>>>.


Заключение

В этой статье я "расшифровал" различные названия, которые в различных функциональных языках и инфраструктурах используются для наименования одних и тех же концепций. Возможно, названия, использующиеся в различных языках и инфраструктурах, никогда не будут согласованы между собой. Но в среду исполнения Java постепенно добавляются такие конструкции как замыкания (closure), что облегчает взаимодействие между различными языками. Благодаря этому они будут использовать одинаковые стандартные представления вместо использования запутанных конструкций, как, например, <Iterator<Iterator<Number>>> в Totally Lazy.

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

Ресурсы

Научиться

  • Functional thinking: Tons of transformations: оригинал статьи (EN).
  • The Productive Programmer (Neal Ford, O'Reilly Media, 2008): новая книга Нила Форда, в которой более подробно рассматриваются некоторые вопросы из данной серии статей.
  • Scala: современный функциональный язык на основе JVM.
  • Clojure: современная, функциональная реализация Lisp, работающая поверх JVM.
  • Инфраструктура Functional Java добавляет в язык Java множество возможностей из арсенала функциональных языков программирования.
  • Totally Lazy: инфраструктура, добавляющая в Java различные типы коллекций с отложенным заполнением.
  • JRuby: реализация Ruby поверх JVM, поддерживающая множество функциональных конструкций.
  • Groovy: Java-подобный динамический язык программирования, добавляющий различные функциональные расширения к синтаксису Java.
  • Посетите магазин книг, посвященных ИТ-технологиям и различным аспектам программирования.
  • Раздел Java-технологий на портале developerWorks содержит сотни статей обо всех аспектах Java-программирования.

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

Обсудить

  • Участвуйте в сообществе developerWorks. Объединяйтесь с другими пользователями developerWorks и исследуйте блоги разработчиков, форумы, группы и Wiki-ресурсы.

Комментарии

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=900935
ArticleTitle=Функциональное мышление: Различные подходы к выполнению стандартных преобразований
publish-date=04252013