Имитируем алгебраические типы данных в языке Java

Продолжаем тему внедрения элементов функционального программирования в процесс разработки на императивном языке Java. Сегодня мы поговорим о красоте такого понятия как алгебраический тип данных. Интуиция, лежащая при создании такого понятия, и его использование хорошо описаны в статье Евгения Кирпичева "Элементы функциональных языков", опубликованной в 3-м номере журнала Практика функционального программирования . Если вам интересно, то подробное математическое обоснование понятия "алгебраический тип данных" можно прочитать в статье Романа Душкина "Алгебраические типы данных и их использование в программировании", опубликованной во 2-м номере того же журанала. В дальнейшем, обещаю не использовать такие термины, как "размеченное объединение", "декартово произведение", "нотация Хоара" и т.д.

Моя же статья является упрощенным переводом Structural Pattern Matching in Java с некоторыми дополнениями.


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

          У
        /  \
     У      Л
   /  \
Л    П


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

Вот здесь на помощь и могут придти алгебраические типы данных - типы данных, состоящие из нескольких различных разновидностей, возможно составных, называемых термами. В нашем случае есть три типа термов: Node (узел), Leaf (лист) и Empty (пустой элемент). В большинстве функциональных языков со статической типизацией есть встроенная поддержка алгебраических типов данных, например в языке F# дерево можно описать следующим образом:

type 'T Tree =

    | Empty

    | Leaf of 'T

    | Node of 'T Tree * 'T Tree

С помощью символов '|' в данном описании отделяют один терм от другого, символ '*' служит для объединения компонентов составных типов данных. В частности, Node - это объект, который содержит в себе два дерева: левое и правое.

Используются абстрактные типы данных совместно с такой программной техникой, как сопоставление с образцом. Суть данной техники следующая: форма структуры (а нашем случае структура задается с помощью абстрактного типа данных) сопоставляется с некоторым образцом, имеющим пропуски - переменные. Эти переменные заполняются значениями соответствующих полей той структуры, которая удовлетворяет образцу. Для примера рассмотрим код функции, возвращающей высоту бинарного дерева, на языке F#:

let rec depth t =

    match t with

        | Empty       -> 0

        | Leaf (_)    -> 1

        | Node (L, R) -> 1 + max (depth L) (depth R)

В данном коде оператор match ... with и выполняет сопоставление с образцом. Символы '|' служат для разделения образцов, каждый образец называется "клозом". После стрелки (оператор '->') описывается действие, которое необходимо сделать, в случае, если переменная t совпала с образцом. Видно, что с переменными L и R будут связаны левое и правое поддерево, соответственно. Строго говоря, использовать термин "переменная" в данном случае не совсем корректно, т.к. данный код написан в функциональном стиле и никаких изменений значений здесь нет. Под термином "переменная" в данном случае понимается просто именнованая область памяти. При вычислении высоты дерева нам не нужно знать значение листа, поэтому в клозе Leaf используется знак _. В языке F# существует еще одна форма оператора сопоставления с образцом, но для целей данного повествования это несущественно.

Теперь вернемся к языку Java, в котором нет встроеной синтаксической поддержки алгебраических типов данных. Предположим, что нам нужно решить ту же самую задачу: описать бинарное дерево и найти его высоту. Есть несколько вариантов решения даной задачи, рассмотрим подробно каждый из них и отметим его достоинства и недостатки.

1. Использование оператора instanceof

Мы можем определить отдельные классы для каждого терма, например Empty для пустого объекта, Leaf для листа и Node для узла. Соответственно, в методе вычисления высоты дерева будем проверять класс объекта и в зависимости от класса выполнять то или иное действие. Код будет таким:

public static int depth(Tree t) {

    if (t instanceof Empty)

        return 0;

    if (t instanceof Leaf)

        return 1;

    if (t instanceof Node)

        return 1 + max(depth(((Node) t).left), depth(((Node) t).right));

   throw new RuntimeException("Inexhaustive pattern match on Tree.");

}

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

2. Использование кодировки Черча

В 20-х годах XX-го века Алонзо Черч предложил математический формализм, именуемый Лямбда-исчислением, а так же описал как можно определять данные в терминах этого формализма. Мы знаем, что каждый тип данных может быть описан через операции, которые можно выполнять над объектами этого типа. Черч пошел еще дальше, он показал, что каждый тип данных это есть функция! Для примера рассмотрим так называемые числа Черча:

0 = λf.λx. x
1 = λf.λx. f x
2 = λf.λx. f (f x)
3 = λf.λx. f (f (f x))
...
n = λf.λx. fⁿ x

Чтобы понятнее было последующее объяснение, рассмотрим представление пары в кодировке Черча. Пара - это составной тип данных, который содержит два значения: первое и второе. Над данными типа пара определены две операции: вернуть первое значение (fst) и вернуть второе значение (snd):

pair = λx.λy.λz.z (x y)
fst = λp.p (λx.λy.x)
snd = λp.p (λx.λy.y)

Подробно рассмотрим определение pair. В данном представлении пара - это функция аргумента x (первого элемента пары), которая возвращает функцию аргумента y (второго элемента пары), которая в свою очередь возвращает функцию аргумента z, которая возвращает значение переденного аргумента z от x и y (т.е. аргумент z - бинарная функция). Или, что может быть несколько понятнее, пара - это функция двух аргументов x и y, которая возвращает функцию, принимающую на вход функцию двух аргументов z и возвращающую ее значение от x и y.

Т.е. функция pair имеет тип A -> A -> (A -> A -> A). Запись A -> B -> C обозначает функцию двух аргументов, первый аргумент имеет тип A, второй - тип B, а результат функции имеет тип C. Для упрощения понимания считаем, что в паре хранятся элементы одного типа A.

Определение fst следует понимать так: это функция, принимающая на вход пару p и возвращающая значение этой пары от функции двух аргументов x и y (помним, что пара - это функция от функции), которая просто возвращает значение первого аргумента x.

Рассмотрим вычисление первого элемента пары в таком представлении:

fst (pair a b) = λp.p (λx.λy.x) ((λx.λy.λz.z x y) a b) = λp.p (λx.λy.x) (λz.z a b) = (λz.z a b) (λx.λy.x) = (λx.λy.x) a b = a

Теперь представим наше бинарное дерево, как функцию.

Empty = λa.λb.λc.a
Leaf = λa.λb.λc.λx.b (x)
Node = λa.λb.λc.λl.λr.c (l r)

Т.е. бинарное дерево, это функция трех аргументов a, b и c, которая в случае пустого элемента возвращает значение аргумента a, в случае листа - аргумента b и в случае узла - аргумента c. Причем, аргумент a - это просто некоторая константа, характерная для пустого элемента (например, при вычислении высоты дерева это будет 0). Аргумент b - унарная функция, принимающая на вход значение, хранящееся в листе дерева. В лябмда-нотации данная функция записывается, как λx.b x. И, наконец, аргумент c - это бинарная функция, принимающая на вход указатели на левое и правое поддерво, хранящиеся в узле. В лямбда-нотации данная функция записывается как λl.λr.c l r.

Итак, бинарное дерево - это функция, которая принимает на вход следующие значения:

1. значение, которое будет возвращено, если дерево пустое
2. функцию одного аргумента, которая будет вызвана для значения листа, если дерево - лист
3. функцию двух аргументов, которая будет вызвана для левого и правого поддерева, если дерево - узел.

Тип такой функции следующий:

T -> (a -> T) -> (Tree a -> Tree a -> T) -> T, где a - тип данных, хранящихся в листах дерева,
T - тип результата, получаемого при обходе дерева.

Эта запись эквивалентна следующей:

(Empty -> T) -> (Leaf -> T) -> (Node ->T) -> T


Переведем все на язык Java:

public abstract <T> T match(F<? super Empty, T> a, F<? super Leaf, T> b, F<? super Node, T> c);

В данном случае F - это псевдофункция, представляемая в виде интерфейса с единственным методом, например так:

package name.samolisov.pattern.matching.demo;



public interface F<A, B>

{

    public B f(A a);

}

 

Итак, все дерево целиком можно представить следующим образом:

package name.samolisov.pattern.matching.demo;





public abstract class Tree

{

    private Tree() {}



    public abstract <T> T match(F<? super Empty, T> a, F<? super Leaf, T> b, F<? super Node, T> c);



    public static final class Empty extends Tree

    {

        public <T> T match(F<? super Empty, T> a, F<? super Leaf, T> b, F<? super Node, T> c)

        {

            return a.f(this);

        }



        public Empty() {}

    }



    public static final class Leaf extends Tree

    {

        public final int n;



        public <T> T match(F<? super Empty, T> a, F<? super Leaf, T> b, F<? super Node, T> c)

        {

            return b.f(this);

        }



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

    }



    public static final class Node extends Tree

    {

        public final Tree left;

        public final Tree right;



        public <T> T match(F<? super Empty, T> a, F<? super Leaf, T> b, F<? super Node, T> c)

        {

            return c.f(this);

        }



        public Node(Tree left, Tree right)

        {

            if (left == null || right == null)

                throw new IllegalArgumentException("subtrees could not be null, they must be a Leaf or an Empty");



            this.left = left; this.right = right;

        }

    }

}

 

Несколько моментов. Первое, использование приватного конструктора гарантирует, что у класса Tree будут только те наследники, которые описаны в самом классе, т.е. Empty, Leaf и Node. Второе, в конструкторе класса Node переданные значения left и right проверяются на null непосредственно в процессе построения дерева. Данное решение гарантирует, что правое и левое поддерева дерева не будут null'ами и дополнительно проверять их при обходе не следует. Тем самым мы выполняем первую задачу, поставленную в начале статьи: контролируем корректность внутренней структуры дерева.

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

Рассмотрим использование такого представления дерева. Прежде всего дерево нужно создать:

Tree t = new Node(new Node(new Node(new Leaf(10), new Leaf(5)), new Leaf(6)), new Node(new Leaf(5), new Empty()));

В результате выполнения данного кода будет создано такое дерево:

                У
             /    \
         У      У
      /  \     /\
     У   6   5
   /  \
10   5

Метод, вычисляющий высоту дерева следующий:

    public static int depth(Tree t)

    {

        return t.match(constant(0), constant(1), new F<Node, Integer>()

                {

                    public Integer f(Node n)

                    {

                        return 1 + max(depth(n.left), depth(n.right));

                    }

                });

    }



 

В данном коде функция max - тривиальна, она возвращает большее из переданных ей чисел. Функция constant поинтереснее - она возвращает псевдофункцию F, которая игнорирует переданные ей значения, а возвращает константу. Фактически это - имитация замыканий на языке Java:

    public static <T extends Tree> F<T, Integer> constant(final Integer data)

    {

        return new F<T, Integer>()

        {

            public Integer f(T a)

            {

                return data;

            }

        };

    }

Чтобы не создавать разные константные функции для листа и пустого значения, метод match и был определен с использованием маски super. Строго говоря, это дает возможность программисту передавать в него не псевдофункции вида F<Empty, Integer>, например, а псевдофункции вида F<Tree, Integer>, а в них делать неправильные приведения типов, однако, цель таких манипуляций лично мне не понятна. Если нужна псевдофункция, реализующая одну и ту же логику для элементов дерева разного типа, то ее лучше объявить, как <T extends Tree> F<T, something>, если же логика различается, то тип узла надо указать явно, например, F<Node, Integer>.

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

Конечно все это в какой-то мере похоже на паттерн Visitor, особенно если не заниматься догматическим буквоедством (например, не учитывать, что в GoF методы интерфейса IVisitor описаны как void). Однако, большинство реальных алгебраических типов данных (деревья, списки, более сложные структуры) имеют 2 -3 терма (впрочем, это не значит, что нет исключений) и их реализация с помощью кодировки Черча будет более элегантной, нежели реализация паттерна Visitor от GoF. Если смотреть вперед, то в Java 7 появятся замыкания и анонимные функции, что сделает приведенный код еще более красивым, т.к. не придется описывать анонимные классы - псевдофункции.

Понравилось сообщение - подпишитесь на блог или читайте меня в twitter