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

Нил Форд, Архитектор ПО, ThoughWorks Inc.
10 Июля 2012
перевод статьи Functional thinking: Either trees and pattern matching

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

Используя дженерики в Java, Either станет цельной структурой данных, которая принимает или Exception (левое значение) или Integer (правое значение), как это показано на Изображении 1:

Изображение 1. Either абстракция содержащая какой-то из 2х типов

В этом примере, это присваивание генерирует Either:

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

Сопоставление-по-образцу в Scala

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

Листинг 1. Использование сопоставления-по-образцу для сопоставления оценок с результатами

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 %sn", 91, letterGrade(91))
printf("Bob scores %d and receives %sn", 72, letterGrade(72))
printf("Sam never showed for class, scored %d, and received %sn", 
    44, letterGrade(44))
printf("Roy transfered and already had %s, which translated as %sn",
    "B", letterGrade("B"))

В Листинге 1, все тело функции состоит из match который применяется к value. Для каждого варианта, pattern guard позволяет мне фильтровать совпадения, базируясь на критерии в довесок к типу аргумента. Преимущество такого синтаксиса это чистое разделение вариантов, вместо не элегантной серии if определений.

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

Листинг 2. Сопоставление case классов в Scala

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 классы. Когда происходит определение какой цвет был передан в функцию, я использую match для того чтобы сопоставить образец со всеми возможными значениями, включая последний случай, который обрабатывает null.

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

Either деревья

Волне реально смоделировать древовидную структуру данных с 3мя асбтракциями, как это показано в Табице 1:

Таблица 1. Построение дерева с 3мя абстракциями

Я реализовал простую версию класса Either в прошлой части, но для удобства я буду использовать реализацию из библиотеки Functional Java в этом примере. Концептуально, абстракция Either расширяется во столько слотов, сколько необходимо. Например, представим себе объявление Either<Empty, Either<Leaf, Node>>, которое создает структуру данных с 3-мя составляющими, как это показано в изображении 2:

Изображение 2. Структура данных Either<Empty, Either<Leaf, Node>>

Вооруженный такого рода реализацией 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 определяет внутри себя 3 final, конкретных класса: Empty, Leaf и Node. Внутри, класс Tree использует класс Either c 3-мя слотами, представленный на Изображении 2, поддерживая соглашение что самый левый слот содержит Empty, средний слот содержит Leaf и самый правый содержит Node. Это осуществляется благодаря обязательной реализации toEither() метода для каждого класса, возвращаемый правильный «слот» в соответствии с типом. Каждая «ячейка» в структуре данных это объединение (union) в традиционном для компьютерных наук смысле, созданная для того, чтоб содержать только один из трех возможных типов данных в определенный момент времени.

Используя данную структуру данных и тот факт, что я знаю внутреннюю структуру данных, которая базируется на <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 если они совпадают. В другом случае, если попадается узел, я рекурсивно обхожу дерево используя | (оператор или) для объединения возвращаемых булевых значений.

Для того чтобы увидеть создание дерева и поиск в действии, рассмотрим юнит тест представленный в Листинге 6:

Листинг 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 если одно из листьев равно поисковому значению, и 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 для каждого совпадающего листа (leaf), что позволяет мне подсчитать количество раз, когда элемент попадается в дереве.

Листинг 8, иллюстрирует тесты для методов depth(), inTree() и occurrencesIn() в сложном дереве:

Листинг 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-идеальному.

Заключения

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

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

Автор: Sigrlami

Источник