Bom, esses dias estava estudando Scala. Uma linguagem multi-paradigma, mas que parece mais “funcional” do que “imperativa”. Scala cai numa posição ainda nebulosa para a maior parte das pessoas (e acho até que para o mercado também). Afinal, imutabilidade é “programação funcional”? Scala não faz nada que impede “side-effects” no código, como Haskell por exemplo, então ela é funcional mesmo?

Como mesmo eu não tenho muitos conhecimentos em linguagens funcionais, resolvi propor um problema para mim mesmo: implementar uma árvore binária em Ruby, e depois portá-la para Scala, tentar uma abordagem imutável em Scala, e depois portar para Haskell. O código está no github, mas algumas coisas vão ser discutidas aqui.

Primeiramente, a árvore imutável é feita recriando a árvore inteira. Claro, não podemos re-criar apenas um nó e apontar, digamos, a referencia de seu pai para esse novo nó, porque o pai é imutável (assim como qualquer outro aspecto do programa).

class Node[A <% Ordered[A]](value: A = None, left: Option[Node[A]] = None, right: Option[Node[A]] = None) {
    def insertNew(newValue: A): Node[A] = value match {
        case v if(newValue < v) => insertLeft(newValue)
        case _ => insertRight(newValue)
    }

    private def insertLeft(newValue: A) = new Node(value, newChild(left, newValue), right)
    private def insertRight(newValue: A) = new Node(value, left, newChild(right, newValue))
    private def newChild(child: Option[Node[A]], newValue: A) = child match {
        case Some(child) => Some(child insertNew newValue)
        case None => Some(new Node(newValue))
    }
}


Para esse código, eu usei a idéia de Option, de Scala. Note que o tipo “A” é polimórfico, e forçadamente diz que ele precisa implicitamente ser um Ordered (facilitando: “A” é um tipo, em Scala, que implemente comparações (menor, igual, maior, etc). Ou seja, um “Int” vale, um “String” também). A idéia do Option é semelhante ao nulo. O valor pode estar lá, ou não. É muito usado em buscas:

val a = List(1, 2, 3) //Cria uma lista. O método "find", abaixo, retorna um Option[Int]
//para essa lista, pois essa lista é do tipo List[Int].
val b = a.find(e => e == 2) //"b" é uma instância do tipo Some[Int]. O tipo "Option" i

Option, em Scala, tem dois valores possíveis (duas sub-classes): “Some”, e “None”. Some é quando o valor foi encontrado, None quando não foi encontrado. É possível fazer “pattern match” nesses casos, igual ao “case Some(child)”. Enfim, a idéia funciona, a árvore é re-criada, mas precisamos ficar pensando em casos que a sub-árvore existe (Some) e em casos aonde ela não existe (None), e é quase como trabalhar com nulos, mas de uma forma mais “abstraída”, que no nosso caso se reflete no compilador reclamando se você não tratar um Option.

Agora, a versão em Haskell. Primeiro, definimos um tipo de dados:

data Tree a = EmptyTree | Node a (Tree a) (Tree a)

A árvore (Tree) ou é uma árvore vazia (EmptyTree) ou um nó que contém um valor, uma árvore à direita e uma à esquerda.

Wow.

Sério, o ponto aqui não é a API. É simplesmente o que isso significa. Eu não disse que uma “árvore vazia” é um nulo, um None, ou qq coisa que o seja. Eu descrevi o que é, para mim, uma árvore. Além disso, Haskell permite definir seus métodos de acordo com o que eles esperam receber. Ou seja, um método pode ser definido de forma diferente se ele espera “1” ou se ele espera outros valores, como no caso do fatorial:

fat 0 = 1
fat x = x * (fat x - 1)

Ok, estamos chegando em algum lugar. E se implementássemos nossa árvore assim também?

(<<) EmptyTree value = Node value EmptyTree EmptyTree
(<<) (Node value left right) newValue = if newValue < value 
    then Node value (left << newValue) right
    else Node value left (right << newValue)

Nesse código, (<<) é para definir uma função chamada "<<". Em Haskell, qualquer função que não seja composto por caracteres alfanuméricos pode ser escrito entre os operadores. Assim, uma função chamada "($@) parametro1 parametro2" pode ser escrita ou como "($@) parametro1 parametro2" ou como "parametro1 $@ parametro2" (note a ausência de parenteses, que Haskell não precisa e nem deixa). Achei que a idéia de fazer um método "arvore << valor" faz mais sentido do que "insertInto arvore valor". Voltando ao código acima, repare em uma coisa incrível: esse código, SOZINHO, monta uma árvore. Nem mais, nem menos. Podemos fazer isso em Scala?

A verdade, é que podemos.

class Tree[A &lt;% Ordered[A]]() extends Traversable[A] {
    def &lt;&lt; (newValue: A): Tree[A] = this match {
        case EmptyTree() =&gt; Node(newValue, EmptyTree[A], EmptyTree[A])
        case Node(value, left, right) if(newValue &lt; value) =&gt; Node(value, left &lt;&lt; newValue, right)
        case Node(value, left, right) =&gt; Node(value, left, right &lt;&lt; newValue)
    }
}
case class EmptyTree[A &lt;% Ordered[A]]() extends Tree[A]
case class Node[A &lt;% Ordered[A]](a: A, left: Tree[A], right: Tree[A]) extends Tree[A]

Repare nos "case class". São o equivalente ao "data" do Haskell, só que BEM menos descritivos, infelizmente. Agora, vamos pensar numa forma de percorrer essa árvore. Em Haskell, podemos criar uma lista e podemos imprimir os valores da árvore:

toArray EmptyTree = []
toArray (Node value left right) = toArray left ++ value : toArray right

printTree EmptyTree = return ()
printTree (Node value left right) = do
    printTree left
    print value
    printTree right

PORÉM, não podemos aproveitar uma função para a outra… porque, a função "toArray" é "pura", pois não tem efeitos colaterais e retorna um valor único (a lista). Já o printTree retorna um valor simbólico (chamado de "IO ()", que indica que ela tem efeitos colaterais (o IO) e que não retorna nada (um conjunto vazio)). Tentei usar um meio de aplicar uma função, e ver se essa função "aplicada" poderia ou imprimir ou retornar uma lista, mas não rola – uma tem efeitos colaterais e não é "pura", a outra não tem e é "pura", e Haskell é bem categórico em dividir o código entre essas duas partes.

Já o código em Scala:

class Tree[A &lt;% Ordered[A]]() extends Traversable[A] {
    def foreach[U](f: (A =&gt; U)) = this match {
        case Node(value, left, right) =&gt; left foreach f; f(value); right foreach f
        case EmptyTree() =&gt;
    }
}

Como eu extendo o Traversable (o equivalente ao Enumerable do Ruby), eu posso aproveitar isso para o toList e tudo o mais. Porém, como é possível ver, essa função não é "pura", pois no caso do EmptyTree, ela simplesmente não retorna.

Isso é desejável? Isso é uma aberração dos paradigmas? Claro, isso dá uma flexibilidade que nem Haskell nem Java (ou Ruby) possuem, mas aí vem a pergunta: que paradigma é esse? É um "pseudo-funcional", "orientado a objetos e funções"? Quais as implicações, as regras que aprendemos continuam valendo?

Eu ainda busco a minha resposta para isso. Mas, como o que eu mais gosto em uma linguagem é a flexibilidade que ela me oferece, não posso negar que, hoje, Scala disputa com Ruby em linguagem mais flexível.


4 Comments

Renato Zannon (@renato_bill) · 2011-10-19 at 08:08

Não sei se era bem isso que você queria fazer, mas podemos tornar o tipo Tree “printável” fazendo dele uma instância da classe Show:

“`haskell
instance (Show a) => Show (Tree a) where
show EmptyTree = “”
show node = show $ toArray node
“`

Depois, no ghci:

“`haskell
*Main> let t = EmptyTree << 5 << 7 << 8 << 3 << 2 < print t
[2,3,5,7,8,9]
“`

Maurício Szabo · 2011-10-20 at 15:33

Boa pergunta, não sei se tem uma forma… mas não adiantaria muito, pq o WordPress não tem suporte a Haskell (eu usei suporte a F-Sharp nos meus exemplos em Haskell)

Enfim, não era isso não q eu pensei. O que eu queria fazer era que eu pudesse passar uma função para ser aplicada a cada um dos elementos da árvore, mas como Haskell é estática, não dá pra essa função ser “genérica” e poder tanto retornar os elementos em ordem (como um Array ou alguma outra estrutura) ou imprimir cada elemento na tela.

    Renato Zannon (@renato_bill) · 2011-10-25 at 00:22

    Eu andei lendo novamente aquele tutorial “Learn You a Haskell for Great Good” e percebi que na verdade tem sim, só não é tão natural quanto no seu exemplo de Scala.
    https://gist.github.com/1311185

    Provavelmente dá pra fazer coisas ainda mais legais fazendo Tree ser uma instância de functor/applicative functor por exemplo, mas aí já além do pouco que eu sei =p

Leave a Reply to Renato Zannon (@renato_bill) Cancel reply

Your email address will not be published. Required fields are marked *