Scala, Traversable, e Implicits

Meu primeiro post bem técnico sobre Scala, vamos ver no que dá (rs).

Bom, primeiro, um pouco de “background”: comecei o fantástico curso de Machine Learning no site coursera.org, e todas as lições que estão no site são em Octave/Matlab. Não conhecia Octave, muito menos Matlab, e quando programei nestas linguagens descobri algumas coisas meio estranhas (bom, eu pelo menos considero estranho que, ao esquecer de colocar um “;” no final de um comando, ele imprima o resultado na tela), além, claro, de não ser possível programar pra Android, por exemplo.

Como estou estudando Scala, e como já consegui fazer Scala rodar no Android de um jeito menos “doloroso” (mais sobre isso em outro post), resolvi fazer os códigos em Scala. Há bibliotecas boas de multiplicação de matrizes em Scala, porém comparadas com as versões Java, elas são BEM mais lentas. Foi aí que pensei: por que não encapsular uma dessas bibliotecas Java em Scala?

Tudo correu bem, até o momento que resolvi que queria que cada matriz funcionasse como um Traversable. Para quem é de Ruby, o Traversable é equivalente ao Enumerable, com algumas coisas a menos e outras a mais. Só para comparar, vamos ver o código dos dois (para simplificar, vou omitir alguns códigos, mas a API é a seguinte: Matrix#rows e Matrix#cols para saber o número de linhas e colunas, Matrix#* multiplica matrizes ou uma matriz com um número. Também, a matriz possui um atributo, “list”, que contém um array de arrays com os elementos internos da matriz).

class Matrix(list: List[List[Double]]) extends Traversable[Double] {
  def cols = 3 //Só pro nossos códigos de exemplo compilarem...
  def foreach[B](function: Double => B) = list.flatten.foreach { e => function(e) }
}
class Matrix
  include Enumerable
  def each(&b)
    list.flatten.each &b
  end
end

Repare que o código é semelhante nas duas linguagens, a diferença básica é que em Ruby não precisamos definir tipos, em Scala precisamos (não que nesse caso faça alguma diferença). Só que temos um caso engraçado tanto em Ruby como em Scala: se queremos um método que, digamos, eleve todos os elementos ao quadrado, elemento por elemento, ao usar “map” para fazer esse processo, ele vai nos retornar, em Ruby, um Array, e em Scala, um Traversable[Double]. E pior, os elementos vão ficar “achatados”. Em ambos, é possível resolver isso fazendo o “each” (ou o “foreach”) retornar uma lista de elementos que está em cada linha, mas ainda assim temos o problema que nosso retorno será semelhante a um “array de arrays”, não uma matriz. O que fazer?

Bom, em Ruby, a gente se ferrou, literalmente. Não temos uma maneira de fazer isso que não envolva sobrescrever o map, e todos os métodos que constrõem uma lista a partir de outra. Em Scala, temos “implicits”, e um conceito “canBuildFrom”.

A partir de agora, começamos a ver o poder da tipagem de Scala. Vendo a API do Traversable podemos ver que é dito que precisamos implementar um método, “newBuilder”, para criar coleções do mesmo tipo.

Só que isso não funciona.

Basicamente, vou usar a definição do método “map”, para vermos o que ele faz: na API, a assinatura de método completa dele está assim:

def map[B, That](f: (A) ⇒ B)(implicit bf: CanBuildFrom[Traversable[A], B, That]): That

Bom, o que significa cada uma dessas coisas? Primeiro, diz que o método chama map, e define dois tipos, B e That. Recebe um parâmetro f, que mapeia um elemento A para um elemento B, e retorna That. Sopa de letrinhas… o que é cada coisa?

A é a tipagem de nossa coleção. No meu caso (class Matrix extende de Traversable[Double]), o A sempre será Double; B é o retorno do map. Repare que nem sempre o retorno será um Double, e aqui eu tenho um problema com meu código: eu não trato isso; That é o retorno do Map, isto é, um elemento (que no meu caso, do jeito como eu implementei, That é um Traversable[Double]).

E por que “That” é um “Traversable[Double]”? Simples, porque eu disse na definição da minha classse, que “Matrix É UM Traversable[Double]”. Para resolver isso, eu poderia dizer que minha classe é um TraversableLike, então vamos corrigir isto agora:

class Matrix(list: List[List[Double]]) extends Traversable[Double] with scala.collection.TraversableLike[Double, Matrix] {
  def cols = 3
  def foreach[B](function: Double => B) = list.flatten.foreach { e => function(e) }
}

Isso nos dá um erro de compilação. O erro diz, claramente, que o método newBuilder não é válido. Isso porque antes, o newBuilder retornava uma classe Traversable, agora deve retornar um Matrix. Vamos corrigir isso:

class Matrix(list: List[List[Double]]) extends Traversable[Double] with scala.collection.TraversableLike[Double, Matrix] {
  def cols = 3
  def foreach[B](function: Double => B) = list.flatten.foreach { e => function(e) }
  //Não me perguntem o que significa protected[this], eu só copiei a definição...
  override protected[this] def newBuilder = ???
}

Isso precisa retornar um Builder, que construi um Matrix. Há um jeito fácil de construir um, usando o ListBuffer: você instancia um ListBuffer, e mapeia o resultado dele para o que você quer. Vamos fazer isso:

class Matrix(list: List[List[Double]]) extends Traversable[Double] with scala.collection.TraversableLike[Double, Matrix] {
  def cols = 3
  def foreach[B](function: Double => B) = list.flatten.foreach { e => function(e) }
  override protected[this] def newBuilder = buildMe

  def buildMe = new scala.collection.mutable.ListBuffer[Double].mapResult { e => 
    val list = e.grouped(cols).map { l => l.toList }.toList
    new Matrix(list)
  }
}

Explicando o buildMe, ele cria um ListBuffer, e chama o método mapResult, que traz o resultado do listBuffer como parâmetro. Eu agrupo o resultado em colunas (afinal, temos uma matriz, e depois do map nosso resultado está “achatado”) e mapeio ele pra nossa matriz. Show, compilo, e testo… para ver que ainda não deu certo.

Bom, isso ainda não funciona porque estamos esquecendo de uma parte da declaração do map: (implicit bf: CanBuildFrom[Traversable[A], B, That]). O que significa isso? Scala tem uma coisa engraçada que é “implicits”. Um “implicit” é, em linhas gerais, um método que é chamado automaticamente, quando necessário. A declaração desto map, no TraversableLike, é um pouco diferente do Traversable: def map[B, That](f: (A) ⇒ B)(implicit bf: CanBuildFrom[Repr, B, That]): That (repare que, no TraversableLike, o primeiro parâmetro foi substituído de Traversable[Double] para Repr). Explicando cada parâmetro (eles estão explicitados na classe CanBuildFrom): o primeiro, Repr, é a classe a qual está CHAMANDO o map (no nosso caso, Matrix). O segundo, B, é o PARÂMETRO que está saindo do “map”, ou seja, o retorno da função (ou da closure) passada para map. O terceiro, é o objeto a ser mapeado com a saída “map”. Como se aproveitar disso?

Na verdade, é muito simples. Precisamos colocar, em algum lugar, um método implícito que diz que podemos construir um Matrix quando o retorno do map for um Double, mas para isso precisamos saber ONDE colocar este método. Por padrão, os implicits são colocados no objeto de mesmo nome da classe (Scala chama isso de “companion objects”), e eu não achei uma maneira de colocar em outro lugar, então vamos lá:

class Matrix(list: List[List[Double]]) extends Traversable[Double] with scala.collection.TraversableLike[Double, Matrix] {
  def cols = 3
  def foreach[B](function: Double => B) = list.flatten.foreach { e => function(e) }
  override protected[this] def newBuilder = buildMe

  def buildMe = new scala.collection.mutable.ListBuffer[Double] mapResult { e => 
    val list = e.grouped(cols).map { l => l.toList }.toList
    new Matrix(list)
  }
}

object Matrix {
  //Como o método é implícito, o nome dele pode ser qualquer coisa.
  implicit def blahblah[A] = new scala.collection.generic.CanBuildFrom[Matrix, Double, Matrix] {
    def apply(from: Matrix) = ???
    def apply() = ???
  }
}

Acelerando um pouco, o CanBuildFrom é abstrato, então precisamos implementar dois métodos: apply(from) e apply(). Obviamente, o código acima não funciona, porque precisamos retornar algo. O que precisamos retornar? Precisamos retornar um scala.collection.mutable.Builder que construa o Matrix. SÓ QUE temos um problema aí: para construir nossa Matrix, precisamos de informações da classe Matrix (número de colunas, ou seja, o método “col”, e não temos isso no object). Para fazer isso, eu repassei essa responsabilidade para a classe:

class Matrix(list: List[List[Double]]) extends Traversable[Double] with scala.collection.TraversableLike[Double, Matrix] {
  def cols = 3
  def foreach[B](function: Double => B) = list.flatten.foreach { e => function(e) }
  override protected[this] def newBuilder = buildMe

  def buildMe = new scala.collection.mutable.ListBuffer[Double] mapResult { e => 
    val list = e.grouped(cols).map { l => l.toList }.toList
    new Matrix(list)
  }
}

object Matrix {
  implicit def blahblah = new scala.collection.generic.CanBuildFrom[Matrix, Double, Matrix] {
    def apply(from: Matrix) = from.buildMe
    def apply() = new Matrix(List(List())).buildMe
  }
}

Compilamos, e… FUNCIONA! Um código, como por exemplo, new Matrix(List(List(1, 2, 3), List(4, 5, 6))).map { e => e + 2 } retorna uma instância de Matrix! Show! E agora, se fizermos new Matrix(List(List(1, 2, 3), List(4, 5, 6))).map { e => e.toString } retornamos…

Traversable[String].

Bom, claro. Falamos, literalmente, que podemos construir, a partir de um Matrix, de uma função que retorna um Double, outro Matrix. E se fosse necessário retornar um String, ou qualquer outra classe? Que faremos?

A resposta é: outro implicit.

Por questão de simplicidade, eu vou retornar apenas uma Lista de Listas aqui:

class Matrix(list: List[List[Double]]) extends Traversable[Double] with scala.collection.TraversableLike[Double, Matrix] {
  def cols = 3
  def foreach[B](function: Double => B) = list.flatten.foreach { e => function(e) }
  override protected[this] def newBuilder = buildMe

  def buildMe = new scala.collection.mutable.ListBuffer[Double] mapResult { e => 
    val list = e.grouped(cols).map { l => l.toList }.toList
    new Matrix(list)
  }
  
  def buildList[B] = new scala.collection.mutable.ListBuffer[B] mapResult { e => 
    e.grouped(cols).map { l => l.toList }.toList
  }
}    
     
object Matrix {
  implicit def blahblah = new scala.collection.generic.CanBuildFrom[Matrix, Double, Matrix] {
    def apply(from: Matrix) = from.buildMe
    def apply() = new Matrix(List(List())).buildMe
  }
  
  implicit def matrix2list[B] = new scala.collection.generic.CanBuildFrom[Matrix, B, List[List[B]]] {
    def apply(from: Matrix) = from.buildList
    def apply() = new Matrix(List(List())).buildList
  }
}

Aqui, deve ser tudo auto-explicativo: novo implicit, que mapeia de um Matrix, retorno B, para uma Lista de Lista de B (wow), que quando aplicado em um Matrix, chama o método buildList do Matrix.

E você, aí, achando que tipagem era só um monte de sintaxe inútil nas linguagens de programação…

Advertisements
This entry was posted in Scala and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s