Generics, como Scala trata o Problema de Generalização de Classes

Generics em Java = Type Parameters em Scala


A motivação para o uso de generics em Java é bem conhecida, e Scala resolve o mesmo problema, dando um nome diferente para a solução: Type Parameters. Podemos chamar também de Generic Types, o significado é o mesmo.

Criando uma lista de tipo específico




Vamos implementar uma lista ligada para valores String. Tente fazer você mesmo, implementando um classe para ser a célula da lista, e uma para ser a lista em si. A lista deve também conter métodos para adicionar, remover e buscar um elemento específico dado o índice.

Em um paradigma mais funcional por assim dizer, você pode acabar em uma implementação para a célula, parecida com a minha:

1
2
3
4
5
6
7
8
package br.com.dclick.typeparameters

abstract class StringListCell {
    def isEmpty: Boolean
    def next: StringListCell
    def setNext(n: StringListCell): Unit
    def value: String
}


1
2
3
4
5
6
7
8
package br.com.dclick.typeparameters

class StringEmptyCell extends StringListCell{
    def isEmpty = true
    def next: StringListCell = error("empty")
    def value: String = error("empty")
    def setNext(n: StringListCell) = error("empty")
}


1
2
3
4
5
6
7
8
9
package br.com.dclick.typeparameters

class StringValueCell(v: String) extends StringListCell{
    var nextElem: StringListCell = new StringEmptyCell
    def isEmpty = false
    def setNext(n: StringListCell) = nextElem = n
    def next: StringListCell =  nextElem
    def value: String = v
}


Implementação diferente do usual, né? :)
Repare que criei dois tipos de célula: uma célula que está sempre vazia, e uma célula que contém de fato o valor a ser guardado. Fiz isso pois em Scala não existe (ou a idéia é não utilizar) null, assim a checagem é feita por células vazias e não por null. Como Scala utiliza código Java, é possível passar e receber valores nulos. Código puramente em Scala estão praticamente livres de NullPointerException, justamente por essa restrição com valores nulos. Vamos ver logo mais um caso em que é possível obter tal erro.
Em Scala uma das alternativas para execução de funções que devolvem null como resultado para certas circunstâncias, é o Option. Option, como o próprio nome sugere, se trata de um opção por devolver, ou não um valor. No caso de se devolver algum valor, deve-se devolver um Some contendo o valor. No caso de não se devolver o valor, deve-se devolver um None. Ambos são Case Classes, portanto não necessitam da palavra new, e possuem todas a propriedades que vimos em um post anterior.

Pensando em todas essas características da linguagem, cheguei nesta implementação para a lista, e usei uma abordagem recursiva. Vou mostrar o resultado:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package br.com.dclick.typeparameters

class StringList {
    var head: StringListCell = new StringEmptyCell
    var last = head

    def add(value: String): StringTypeList = {
        if (head.isEmpty) {
            head = new ValueCell(value)
            last = head
        }
        else {
            last setNext new ValueCell(value)
            last = last.next
        }
        this
    }

    def remove(index: Int, node: StringListCell): StringListCell = {
        if (node.isEmpty)
            new StringEmptyCell
        if (index == 0) {
            node.next
        }
        else {
            node.setNext(remove(index-1, node.next))
            node
        }
    }

    def get(index: Int, node: StringListCell): Option[String] = {
        if (node.isEmpty)
            None
        else
            if (index == 0)
                Some(node.value)
            else
                get(index-1, node.next)
    }
}


Outra implementação não muito convencional… mas mesmo assim não deixa de ser clara. Mesmo não send o foco do post, vou dar uma breve explicação: na lista guardo o último elemento, assim sei onde devo adicionar o novo elemento; na função add verifico se o início da lista está vazio para adicionar, ou se devo adicionar no final; na função remove se a célula passada estiver vazia devolvo uma nova célula vazia, se o índice atual for zero, ou seja, queremos remover o atual, devolvo o próximo, e como caso padrão seto o próximo item como sendo o resto da lista com o item correto removido (Repare que não funciona para remover o primeiro item, mas não é esse o intuito mesmo :p); na função get verificao se a célula está vazia, logo não devolvo nada, e itero no resto dos itens de maneira recursiva no caso padrão.

Para termos certeza que nossa lista está funcionando corretamente, criei o seguinte teste unitário usando JUnit4, que para utilizá-lo é muito fácil, como foi visto no post anterior.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package br.com.dclick
import br.com.dclick.typeparameters._
import org.junit._
import Assert._

class ListTest {

    @Test
    def testList = {
        val list = new StringList

        assertEquals(None, list.get(0, list.head))

        list add "1" add "2" add "3" add "4" add "5" add "6"

        assertEquals("1", list.get(0, list.head).get)
        assertEquals("2", list.get(1, list.head).get)
        assertEquals("3", list.get(2, list.head).get)
        assertEquals("4", list.get(3, list.head).get)
        assertEquals("5", list.get(4, list.head).get)
        assertEquals("6", list.get(5, list.head).get)
        assertTrue(list.get(6, list.head).isEmpty)

        list.remove(1, list.head)
        list.remove(1, list.head)
        list.remove(1, list.head)

        assertEquals("1", list.get(0, list.head).get)
        assertEquals("5", list.get(1, list.head).get)
        assertEquals("6", list.get(2, list.head).get)
        assertTrue(list.get(3, list.head).isEmpty)
    }
}


Rode o teste para ter certeza de que está tudo rodando.

Generalizando nossa Lista


Agora imagine que queremos fazer uma lista de inteiros ao invés de Strings. O problema é o mesmo que temos em Java. Se generalizarmos nossa lista para guardar AnyRef do Scala ao invés de Strings (em Java faríamos o mesmo com Object), teremos o problema de ter que fazer cast do resultado em toda chamada para nossa lista. Para isso que existem os Generic Types.

Se você reparou como utilizamos Option, tivemos que passar um tipo de parâmetro para ele, que no nosso caso foi String, dessa forma quem utiliza o resultado do método, sabe que está lidando com Strings e portanto não precisa fazer o cast do resultado. Vamos implementar a mesma funcionalidade em nossa lista. Para isso temos que modificar nossas células e nossa lista, de maneira que recebam o tipo como parâmetro. Segue o código da lista modificada:

1
2
3
4
5
6
7
8
package br.com.dclick.typeparameters

abstract class ListCell[T] {
    def isEmpty: Boolean
    def next: ListCell[T]
    def setNext(n: ListCell[T]): Unit
    def value: T
}


1
2
3
4
5
6
7
8
9
package br.com.dclick.typeparameters

class ValueCell[T](v: T) extends ListCell[T]{
    var nextElem: ListCell[T] = new EmptyCell[T]
    def isEmpty = false
    def setNext(n: ListCell[T]) = nextElem = n
    def next: ListCell[T] = nextElem
    def value: T = v
}


1
2
3
4
5
6
7
8
package br.com.dclick.typeparameters

class EmptyCell[T] extends ListCell[T]{
    def isEmpty = true
    def next: ListCell[T] = error("empty")
    def value: T = error("empty")
    def setNext(n: ListCell[T]) = error("empty")
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package br.com.dclick.typeparameters

class TypeList[T] {
    var head: ListCell[T] = new EmptyCell[T]
    var last = head

    def add(value: T): TypeList[T] = {
        if (head.isEmpty) {
            head = new ValueCell(value)
            last = head
        }
        else {
            last setNext new ValueCell(value)
            last = last.next
        }
        this
    }

    def remove(index: Int, node: ListCell[T]): ListCell[T] = {
        if (node.isEmpty)
            new EmptyCell[T]
        if (index == 0) {
            node.next
        }
        else {
            node.setNext(remove(index-1, node.next))
            node
        }
    }

    def get(index: Int, node: ListCell[T]): Option[T] = {
        if (node.isEmpty)
            None
        else
            if (index == 0)
                Some(node.value)
            else
                get(index-1, node.next)
    }
}


Note que a implementação é praticamente a mesma, a única coisa diferente é o tipo do valor passado para guardar na lista. Repare que para quem usa a lista, basta adicionar um tipo no momento de criação da mesma, por isso em nosso teste mude apenas a linha que instancia uma nova lista, e rode o teste.

1
val list = new TypeList[String]


Crie um outro teste com um tipo de valor diferente e veja que funciona da mesma maneira que no Java.

Restrições de Tipos Genéricos


Nosso tipo T pode ser qualquer coisa. Existe em Scala uma sintaxe própria inclusive para inicializar uma varável de um tipo genérico, basta utilizar um ‘_‘. Dessa forma você está explicitando que sua variável pode ou não ter um valor do tipo genérico, afinal não tem como saber se o tipo será um primitivo ou não. Este é o caso em que estamos sujeito ao NullPointerException que citei no começo do post: para definir uma variável em Scala é necessário iniciá-la, e no caso de tipos genéricos, como não possível iniciá-los, as variáveis possuem valor nulo (‘_‘), logo geram código que pode lançar NullPointerException.

Com nosso tipo genérico podendo ser qualquer coisa, não conseguiríamos, por exemplo, ordenar nossa lista, afinal nem tudo é ordenável. A solução em Java é a mesma, mas a sintaxe em Scala me parece bem mais amigável. O que é necessário fazer, é dizer que o seu tipo obrigatoriamente extende de alguma classe determinada. No caso de querermos uma lista ordenada, basta obrigarmos o tipo passado extender de Comparable (no Java), ou Ordered (em Scala). Ordered extende Comparable, sobrescrevendo os operadores de comparação básico (>, <, >=, <=) e utilizando o método de comparação disponível em Comparable (compareTo).

Vamos mudar o parâmetro de nossa lista para obter tal comportamento. Para isto, basta mudar a assinatura da classe com seguinte código:

1
class TypeList[T <: Comparable[T]] {


Estou usando Comparable, pois não teremos erros de compilação usando String como parâmetro. Porém em Scala é possível dizer que um parâmetro poder ser convertido para o tipo definido na restrição. Esse tipo de restrição é chamado de View Bound e Scala já implementa a conversão implícita para os tipos primitivos e String, portanto se mudarmos nossa classe para:

1
class TypeList[T <% Ordered[T]] {


nosso código ainda compila, e nossos testes funcionam, o que é o mais importante :) .

Invariância e Covariância


Pensando em termos de orientação a objetos, se definirmos um lista TypeList[String], esta lista deve ser subtipo de TypeList[AnyRef]? Parece uma pergunta simples de se responder, mas as respostas tem suas implicações. Se a resposta é não, então estamos dizendo que quando criarmos uma lista de Strings, só faremos referência a essa lista sabendo que é do tipo String, e que portanto só adicionamos valores String na lista. Se a resposta é não, então estamos dizendo que ao criarmos um lista de Strings, podemos referenciá-la como uma lista de AnyRef e portanto conseguimos adicionar qualquer valor em nossa lista. O primeiro caso é dito invariante, e o segundo caso é dito Covariante.

Em Scala os tipos são por padrão sempre invariantes. Diferente do Java que é covariante.

Quando os tipos são covariantes, temos o problema de lidar com tipos diferentes dos esperados. Java resolve esse problema fazendo a verificação em tempo de execução, no momento da atribuição de um tipo. Em Scala o problema é resolvido de maneira estática impedindo o código de compilar. Ainda assim é possível estabelecer tipo covariantes em Scala. Para nossa lista, basta mudar a assinatura, com o operador +:

1
class TypeList[+T] {


Fazendo isso, seremos obrigados a mudar em todas as classes que usem T, por exemplo, nossas células.

Mas com isso surge um problema: como que o compilador irá saber tratar o tipo T de maneira que este possa ser de algum supertipo do mesmo? Para isso podemos definir nosso tipo T, como um limitante inferior. Basta usarmos a sintaxe simétrica a de restrições de limitantes superiores:

1
A >: T


Assim estamos dizendo que A é supertipo de T, e portanto podemos usá-lo em nossas funções sem que o compilador reclame.

Também podemos definir um range para nossas restrições combinando os operadores, por exemplo:

1
A >: B <: C


Objects


Scala não permite que usemos parâmetros em objects, por isso mesmo nossa célula vazia teve que definir um tipo para o parâmetro.

Para definirmos um object como super classe de uma classe que necessite de parâmetros, precisamos que a classe pai seja cocariante, e em nosso object, basta extendermos tal classe com o tipo Nothing. O tipo Nothing é subclasse de todos os tipos em Scala, portanto é o menor limitante inferior. Com isso conseguimos definir um object que extende uma classe que precisa de parâmetros.

Antes de falarmos de listas em Scala, ainda falta falarmos de tuplas e Functions. Veremos isso em um screencast que será divulgado em breve.

Espero que a série tenha andado bem até aqui, e que as informações que estou publicando sejam úteis a muitas pessoas. Lembrando que todos os tipos de comentários são bem vindos: críticas, dúvidas e sugestôes.

Por @Gust4v0_H4xx0r