Функциональное мышление: Создание деревьев с помощью Either и использование сопоставления с шаблоном

Использование класса Either и параметризованных типов для создания функциональности на языке Java, аналогичной функциональности сопоставления с шаблоном, имеющейся в языке Scala

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

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

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



09.01.2013

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

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

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

При помощи параметризованных типов (дженериков), доступных в Java, класс Either становится монолитной структурой данных, которая принимает на вход объект одного из двух типов, сохраняя его в своей левой или правой части.

В анализаторе римских чисел, разбиравшемся в предыдущей статье, класс Either содержал либо исключительную ситуацию типа Exception (в поле left) либо числовое значение типа Integer (в поле right), как показано на рисунке 1.

Рисунок 1. Абстракция Either, содержащая объект одного из двух допустимых типов.
Рисунок 1. Абстракция Either, содержащая объект одного из двух допустимых типов.

В данном примере демонстрируется создание объекта Either путем присваивания значения, полученного из метода parseNumber().

Either<Exception, Integer> result = RomanNumeralParser.parseNumber("XLII");

Сопоставление с шаблоном в Scala

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

Листинг 1. Использование сопоставления с шаблоном в Scala для присвоения буквенных кодов в зависимости от числовых значений
val VALID_GRADES = Set("A", "B", "C", "D", "F")


def letterGrade(value: Any) : String = value match {
  case x:Int if (90 to 100).contains(x) => "A"
  case x:Int if (80 to 90).contains(x) => "B"
  case x:Int if (70 to 80).contains(x) => "C"
  case x:Int if (60 to 70).contains(x) => "D"
  case x:Int if (0 to 60).contains(x) => "F"
  case x:String if VALID_GRADES(x.toUpperCase) => x.toUpperCase
}

printf("Amy scores %d and receives %s\n", 91, letterGrade(91))
printf("Bob scores %d and receives %s\n", 72, letterGrade(72))
printf("Sam never showed for class, scored %d, and received %s\n", 
    44, letterGrade(44))
printf("Roy transfered and already had %s, which translated as %s\n",
    "B", letterGrade("B"))

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

В данном примере сопоставление с шаблоном используется в сочетании с case-классами Scala. Эти классы обладают особыми свойствами, включая возможность сопоставления значения с неким образцом, что позволяет отказаться от стандартного подхода к принятию решений, основанного на if-конструкциях. В листинге 2 представлен пример определения цвета.

Листинг 2. Использование case-классов для сопоставления с образцами
class Color(val red:Int, val green:Int, val blue:Int)

case class Red(r:Int) extends Color(r, 0, 0)
case class Green(g:Int) extends Color(0, g, 0)
case class Blue(b:Int) extends Color(0, 0, b)

def printColor(c:Color) = c match {
  case Red(v) => println("Red: " + v)
  case Green(v) => println("Green: " + v)
  case Blue(v) => println("Blue: " + v)
  case col:Color => {
    print("R: " + col.red + ", ")
    print("G: " + col.green + ", ")
    println("B: " + col.blue)
  }

  case null => println("invalid color")
}

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

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


Концепция Either и древовидные структуры

Древовидную структуру данных можно смоделировать с помощью трех абстракций, перечисленных в таблице 1.

Таблица 1. Создание дерева с помощью трех абстракций
Emptyв ячейке нет никакого значения (пустая)
Leafв ячейке есть значение определенного типа (лист — терминальный элемент)
Nodeячейка указывает на другую ячейку Leaf или Node (узел — промежуточный элемент)

В прошлой статье я уже реализовал простую версию класса Either, но для большего удобства в этот раз я воспользуюсь классом Either, входящим в инфраструктуру Functional Java (см. раздел "Ресурсы"). В принципе абстракция Either может иметь любое необходимое количество ячеек. Например, объявление Either<Empty, Either<Leaf, Node>> создает структуру данных, состоящую из трех частей, как показано на рисунке 2.

Рисунок 2. Структура данных Either<Empty, Either<Leaf, Node>>'s data structure
Рисунок 2. Структура данных

Используя версию Either, содержащую три абстракции, необходимые для создания дерева, я могу определить своё дерево, как показано в листинге 3.

Листинг 3. Дерево, созданное с помощью класса Either
import fj.data.Either;
import static fj.data.Either.left;
import static fj.data.Either.right;

public abstract class Tree {
    private Tree() {}

    public abstract Either<Empty, Either<Leaf, Node>> toEither();

    public static final class Empty extends Tree {
        public Either<Empty, Either<Leaf, Node>> toEither() {
            return left(this);
        }

        public Empty() {}
    }

    public static final class Leaf extends Tree {
        public final int n;

        public Either<Empty, Either<Leaf, Node>> toEither() {
            return right(Either.<Leaf, Node>left(this));
        }

        public Leaf(int n) { this.n = n; }
    }

    public static final class Node extends Tree {
        public final Tree left;
        public final Tree right;

        public Either<Empty, Either<Leaf, Node>> toEither() {
            return right(Either.<Leaf, Node>right(this));
        }

        public Node(Tree left, Tree right) {
            this.left = left;
            this.right = right;
        }
    }
}

На базе абстрактного класса Tree, приведенного в листинге 3, определяются три обычных final-класса: Empty, Leaf и Node. Внутри класса Tree в свою очередь используется объект Either с тремя ячейками, изображенный на рисунке 2, с заранее установленными правилами, что в крайней левой ячейке хранится объект типа Empty, в центральной – объект типа Leaf, а в самой правой – объект типа Node. Подобное поведение обеспечивается за счёт того, что в каждом классе объявлен метод toEither() возвращающий "ячейку", соответствующую данному классу. Каждая "ячейка" в структуре данных является множеством, как этот термин понимается в области вычислительных технологий, способным хранить в один момент времени только одно значение из трех допустимых типов.

Используя данную древовидную структуру и зная её внутреннее устройство, основанное на <Either, <Left, Node>>, я могу организовать обход всех элементов дерева на основе «аналога» сопоставления с шаблоном.


Использование сопоставления с шаблоном для обхода дерева

Реализация сопоставления с шаблоном в Scala предполагает мышление в дискретных ситуациях. Методы left() и right() класса Either в Functional Java реализуют интерфейс Iterable, что позволяет мне создать код на основе сопоставления с шаблоном для определения глубины дерева, как показано в листинге 4.

Листинг 4. Определение глубины дерева в стиле сопоставления с шаблоном
static public int depth(Tree t) {
    for (Empty e : t.toEither().left())
        return 0;
    for (Either<Leaf, Node> ln: t.toEither().right()) {
        for (Leaf leaf : ln.left())
            return 1;
        for (Node node : ln.right())
            return 1 + max(depth(node.left), depth(node.right));
    }
    throw new RuntimeException("Inexhaustible pattern match on tree");
}

Метод depth() в листинге 4 является рекурсивной функцией для определения глубины дерева. Так как моё дерево построено из определенных структур данных (<Either, <Left, Node>>), я могу трактовать каждую "ячейку" как отдельный случай. Если ячейка пуста, то глубина данной ветви равна нулю. Если в ячейке лежит объект Leaf, то её глубина может считаться глубиной дерева. Если же в ячейке лежит узел (объект Node), то я знаю, что должен выполнить рекурсивный поиск по его левой и правой ветвям, добавив 1 к текущему уровню рекурсии.

Синтаксис на основе сопоставления с шаблоном также можно применить для рекурсивного поиска по дереву, как показано в листинге 5.

Листинг 5. Поиск значения в дереве
static public boolean inTree(Tree t, int value) {
    for (Empty e : t.toEither().left())
        return false;
    for (Either<Leaf, Node> ln: t.toEither().right()) {
        for (Leaf leaf : ln.left())
            return value == leaf.n;
        for (Node node : ln.right())
            return inTree(node.left, value) | inTree(node.right, value);
    }
    return false;
}

Как и раньше, я определяю возвращаемое значение для всех ячеек, имеющихся в структуре данных. Если я попадаю в пустую ячейку, то возвращаю false, т.е. поиск закончился неудачно. При попадании в терминальную ячейку (Leaf) я возвращаю true, если её значение соответствует искомому. Если же я попал в узловую ячейку (Node), то я выполняю рекурсивное обращение к дереву, используя оператор | для объединения обоих полученных boolean-значений (оператор | вычисляет обе части логического выражения ИЛИ, в отличие от укороченной версии ||).

В листинге 6 представлен unit-тест, в котором выполняется создание дерева и последующий поиск по нему.

Листинг 6. Проверка возможности поиска по дереву
@Test
public void more_elaborate_searchp_test() {
    Tree t = new Node(new Node(new Node(new Node(
            new Node(new Leaf(4),new Empty()), 
            new Leaf(12)), new Leaf(55)), 
            new Empty()), new Leaf(4));
    assertTrue(inTree(t, 55));
    assertTrue(inTree(t, 4));
    assertTrue(inTree(t, 12));
    assertFalse(inTree(t, 42));
}

В листинге 6 я сначала строю дерево, а затем исследую, какие элементы в нем находятся. Метод inTree() возвращает true, в случае если искомое значение содержится в одном из терминальных узлов. Это значение передается наверх по цепочке рекурсивных вызовов благодаря тому, что я воспользовался оператором |, как показано в листинге 5.

Пример из листинга 5 определяет, присутствует ли искомый элемент в дереве. Более сложная версия, приведенная в листинге 7, также способна подсчитать, сколько раз данный элемент встречается в дереве.

Листинг 7. Определение количества вхождений значения в дерево
static public int occurrencesIn(Tree t, int value) {
    for (Empty e: t.toEither().left())
        return 0;
    for (Either<Leaf, Node> ln: t.toEither().right()) {
        for (Leaf leaf : ln.left())
            if (value == leaf.n) return 1;
        for (Node node : ln.right())
            return occurrencesIn(node.left, value) + occurrencesIn(node.right, value);
    }
    return 0;
}

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

В листинге 8 приведен unit-тест, проверяющий работу методов depth(), inTree() and occurencesIn() на примере сложного дерева.

Листинг 8. Определение глубины развернутого дерева, поиск определенного значения и подсчёт количества вхождений
@Test
public void multi_branch_tree_test() {
    Tree t = new Node(new Node(new Node(new Leaf(4),
            new Node(new Leaf(1), new Node(
                    new Node(new Node(new Node(
            new Node(new Node(new Leaf(10), new Leaf(0)),
                    new Leaf(22)), new Node(new Node(
                            new Node(new Leaf(4), new Empty()),
                            new Leaf(101)), new Leaf(555))),
                            new Leaf(201)), new Leaf(1000)),
                    new Leaf(4)))),
            new Leaf(12)), new Leaf(27));
    assertEquals(12, depth(t));
    assertTrue(inTree(t, 555));
    assertEquals(3, occurrencesIn(t, 4));
}

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


Заключение

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

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

Ресурсы

  • Functional thinking: Either trees and pattern matching: оригинал статьи (EN).
  • The Productive Programmer (Neal Ford, O'Reilly Media, 2008): новая книга Нила Форда, в которой более подробно рассматриваются некоторые вопросы из данной серии статей.
  • Scala: современный функциональный язык на основе JVM.
  • The busy Java developer's guide to Scala (EN): узнайте больше о сопоставлении с шаблоном, case-классах и других функциональных возможностях Scala.
  • Structural Pattern Matching in Java (EN): интересный пост Рунара Оли (Rúnar Óli) в блоге Apocalisp, посвященном функциональному программированию, который и послужил источником вдохновения для написания этой статьи.
  • Инфраструктура Functional Java добавляет в язык Java множество возможностей из арсенала функциональных языков программирования.
  • Tree visitors in Clojure (Alex Miller, developerWorks, сентябрь 2011 г.) (EN): статья со сравнением алгоритмов обхода дерева, применяемых в Java и Clojure (функциональном аналоге для JVM).
  • Execution in the Kingdom of Nouns (Steve Yegge, март 2006 г.) (EN): занимательная статья, посвященная отдельным особенностям архитектуры языка Java.

Комментарии

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=854352
ArticleTitle=Функциональное мышление: Создание деревьев с помощью Either и использование сопоставления с шаблоном
publish-date=01092013