Pensamento Funcional: Reconhecimento de padrões e árvores no Either

Usando Either e genéricos para criar reconhecimento de padrões estilo Scala em Java

A capacidade do Scala de realizar envio com base em reconhecimento de padrões é alvo de muita inveja pelos desenvolvedores de Java™. Essa parte do artigo mostra como uma combinação de estruturas de dados padrão e genéricos oferece uma sintaxe semelhante a reconhecimento de padrões em Java puro.

Neal Ford, Software Architect / Meme Wrangler, ThoughtWorks Inc.

Photo of Neal FordNeal Ford é arquiteto de software e Meme Wrangler na ThoughWorks, uma consultoria global de TI. Ele também projeta e desenvolve aplicativos, materiais de instrução, artigos para revistas, treinamentos e apresentações em vídeo/DVD, e é autor ou editor de livros que abordam várias tecnologias, incluindo o mais recente The Productive Programmer. Sua especialidade é o projeto e a criação de aplicativos corporativos de grande porte. Também é palestrante admirado em conferências de desenvolvedores no mundo todo. Conheça seu website website.



26/Jul/2012

Sobre esta série

Esta série visa reorientar sua perspectiva para uma mentalidade funcional, ajudando a encarar problemas comuns de maneiras novas e encontrar maneiras de melhorar sua codificação diária. Ela explora os conceitos de programação funcional, estruturas que permitem programação funcional dentro da linguagem Java, linguagens de programação funcional executadas em JVM e algumas indicações de tendência futura do design da linguagem. A série é voltada para desenvolvedores que conhecem Java e como suas abstrações funcionam, mas têm pouca ou nenhuma experiência na utilização de uma linguagem funcional.

Na última parte do artigo, apresentei uma abstração comum no mundo da programação funcional: Either. Nesta parte do artigo, continuo a explorar o Either, usando-o para desenvolver estruturas em forma de árvore — o que permite imitar o reconhecimento de padrões do Scala para criar métodos de passagem.

Ao usar genéricos em Java, um Either torna-se uma única estrutura de dados que aceita um de dois tipos, que são armazenados em partes esquerda e direita.

No analisador de numerais romanos do artigo passado, Either contém uma Exception (esquerda) ou um Integer (direita), como ilustra a Figura 1:

Figura 1. A abstração Either contendo um de dois tipos
A abstração Either contendo um de dois tipos

Nesse exemplo, esta designação preenche o Either:

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

Reconhecimento de padrões do Scala

Um dos bons recursos do Scala é a capacidade de usar reconhecimento de padrões para envio (consulte Recursos). É mais fácil mostrar do que descrever, portanto, observe a função na Listagem 1, que converte pontuações numéricas para classificações em letra:

Listagem 1. Usando o reconhecimento de padrões do Scala para atribuir classificações de letra com base em uma pontuação
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"))

Na Listagem 1, todo o corpo da função consiste em match aplicado a value. Para cada uma das opções, uma guarda de padrão permite filtrar as correspondências com base em critérios além do tipo de argumento. A vantagem dessa sintaxe é o particionamento limpo das opções, em vez de uma série pouco prática de instruções if.

O reconhecimento de padrões funciona em conjunto com as classes de caso do Scala, que são classes com propriedades especializadas — incluindo a capacidade de realizar reconhecimento de padrões — para eliminar sequências de decisões. Considere a correspondência de combinações de cores, como mostra a Listagem 2:

Listagem 2. Correspondência de classes de caso no 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")
}

Na Listagem 2, crio uma classe Color básica, depois crio versões especializadas de cor única como classes de caso. Ao determinar qual cor foi passada para a função, eu uso match para fazer reconhecimento de padrões em relação às opções possíveis, incluindo o último caso, que lida com null.

Java não possui reconhecimento de padrões, portanto não pode replicar a capacidade do Scala de criar código de envio de fácil leitura. Mas a união de genéricos e estruturas de dados bem conhecidas chega perto disso, o que me traz de volta ao Either.


Árvores Either

É possível modelar uma estrutura de árvore de dados com três abstrações, como mostra a Tabela 1:

Tabela 1. Criando uma árvore com três abstrações
VaziaA célula não possui valor
FolhaA célula possui um valor de um tipo de dados em particular
Aponta para outras Folhas ou s

Eu implementei uma versão simples da classe Either na última parte do artigo, mas, por conveniência, usarei uma da estrutura Functional Java (consulte Recursos) neste exemplo. Conceitualmente, a abstração Either expande-se em quantos slots forem necessários. Por exemplo, considere a declaração Either<Empty, Either<Leaf, Node>>, que cria uma estrutura de dados de três partes como a mostrada na Figura 2:

Figura 2. Estrutura de dados de Either<Empty, Either<Leaf, Node>>
Estrutura de dados de Either<Empty, Either<Leaf, Node>>

Com uma implementação Either das três abstrações de árvore, eu defino uma árvore, como mostra a Listagem 3:

Listagem 3. Árvore com base em 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;
        }
    }
}

A classe abstrata Tree na Listagem 3 define em si três classes concretas final: Empty, Leaf e Node. Internamente, a classe Tree usa o Either de três slots mostrado na Figura 2, reforçando a convenção de que o slot à esquerda sempre contém Empty, o slot do meio contém Leaf e o slot da direita contém um Node. A maneira como isso é feito é solicitar a cada classe que implemente o método toEither(), retornando o "slot" apropriado daquele tipo. Cada "célula" na estrutura de dados é uma união no sentido tradicional da ciência da computação, projetado para conter apenas um dos três tipos possíveis a qualquer dado momento.

Dada essa estrutura de árvore e o fato de que sua estrutura interna é baseada em <Either, <Left, Node>>, é possível imitar o reconhecimento de padrões para visitar cada elemento na árvore.


Reconhecimento de padrões para passagem da árvore

O reconhecimento de padrões do Scala incentiva a pensar sobre casos discretos. Os métodos left() e right() da implementação de Either de Functional Java implementam a interface Iterable. Isso permite escrever um código inspirado em reconhecido de padrões, como mostra a Listagem 4, para determinar a profundidade da árvore:

Listagem 4. Verificando a profundidade de uma árvore usando sintaxe semelhante a reconhecimento de padrões
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");
}

O método depth() na Listagem 4 é uma função recursiva para descobrir profundidade. Como a árvore é baseada em uma estrutura de dados específica (<Either, <Left, Node>>), cada "slot" pode ser tratado como um caso específico. Caso a célula esteja vazia, essa ramificação não possui profundidade. Se a célula é uma folha, é tratada como um nível da árvore. Se a célula é um nó, é necessário procurar recursivamente nos lados esquerdo e direito, incluindo um 1 para outro nível de recursão.

Também é possível usar a mesma sintaxe de reconhecimento de padrões para realizar uma procura recursiva da árvore, como mostra a Listagem 5:

Listagem 5. Determinando presença em uma árvore
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;
}

Como antes, eu especifiquei o valor de retorno de cada "slot" possível na estrutura de dados. Quando uma célula vazia é encontrada, o retorno é false; a procura falhou. Para uma folha, verifica-se o valor passado, retornando true se forem correspondentes. Do contrário, ao encontrar um nó, o programa passa recursivamente pela árvore, usando | (operador ou sem curto-circuito) para combinar os valores booleanos retornados.

Para ver a criação e procura da árvore em ação, observe o teste de unidade da Listagem 6:

Listagem 6. Testando a capacidade de procura da árvore
@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));
}

Na Listagem 6, desenvolvemos uma árvore e depois investigamos se os elementos estão presentes. O método inTree() retorna true se uma das folhas for igual ao valor de procura, e true é propagado através da pilha de chamada recursiva, devido ao operador | ("or"), como mostra a Listagem 5.

O exemplo na Listagem 5 determina se um elemento aparece na árvore. Uma versão mais sofisticada também verifica o número de ocorrências, como mostra a Listagem 7:

Listagem 7. Encontrando número de ocorrências em uma árvore
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;
}

Na Listagem 7, o código retorna 1 para cada folha com correspondência, permitindo contar o número de ocorrências de cada número na árvore.

A Listagem 8 mostra testes de depth(), inTree() e occurrencesIn() em uma árvore complexa:

Listagem 8. Testando profundidade, presença e ocorrências em árvores complexas
@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));
}

Como uma regularidade foi imposta à estrutura interna da árvore, é possível analisá-la durante a passagem pensando em cada caso individualmente, refletido no tipo de elemento. Embora não seja tão expressivo como o reconhecimento de padrões completo do Scala, a sintaxe é surpreendentemente parecida com o ideal do Scala.


Conclusão

Nessa parte do artigo, mostrei como impor regularidade na estrutura interna de uma árvore permite reconhecimento de padrões no estilo do Scala durante as passagens pela árvore, aproveitando algumas propriedades inerentes de genéricos, Iterables, classe Either de Functional Java e alguns outros ingredientes combinados para imitar um recurso eficiente do Scala.

No próximo artigo, eu começo uma investigação sobre os vários mecanismos de envio de método presentes nas linguagens Java da próxima geração, em oposição às opções limitadas disponíveis em Java.

Recursos

Aprender

Obter produtos e tecnologias

Discutir

Comentários

developerWorks: Conecte-se

Los campos obligatorios están marcados con un asterisco (*).


Precisa de um ID IBM?
Esqueceu seu ID IBM?


Esqueceu sua senha?
Alterar sua senha

Ao clicar em Enviar, você concorda com os termos e condições do developerWorks.

 


A primeira vez que você entrar no developerWorks, um perfil é criado para você. Informações no seu perfil (seu nome, país / região, e nome da empresa) é apresentado ao público e vai acompanhar qualquer conteúdo que você postar, a menos que você opte por esconder o nome da empresa. Você pode atualizar sua conta IBM a qualquer momento.

Todas as informações enviadas são seguras.

Elija su nombre para mostrar



Ao se conectar ao developerWorks pela primeira vez, é criado um perfil para você e é necessário selecionar um nome de exibição. O nome de exibição acompanhará o conteúdo que você postar no developerWorks.

Escolha um nome de exibição de 3 - 31 caracteres. Seu nome de exibição deve ser exclusivo na comunidade do developerWorks e não deve ser o seu endereço de email por motivo de privacidade.

Los campos obligatorios están marcados con un asterisco (*).

(Escolha um nome de exibição de 3 - 31 caracteres.)

Ao clicar em Enviar, você concorda com os termos e condições do developerWorks.

 


Todas as informações enviadas são seguras.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=80
Zone=Tecnologia Java
ArticleID=827395
ArticleTitle=Pensamento Funcional: Reconhecimento de padrões e árvores no Either
publish-date=07262012