Orientado a Objetos versus Funcional

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 <% Ordered[A]]() extends Traversable[A] {
    def << (newValue: A): Tree[A] = this match {
        case EmptyTree() => Node(newValue, EmptyTree[A], EmptyTree[A])
        case Node(value, left, right) if(newValue < value) => Node(value, left << newValue, right)
        case Node(value, left, right) => Node(value, left, right << newValue)
    }
}
case class EmptyTree[A <% Ordered[A]]() extends Tree[A]
case class Node[A <% 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 <% Ordered[A]]() extends Traversable[A] {
    def foreach[U](f: (A => U)) = this match {
        case Node(value, left, right) => left foreach f; f(value); right foreach f
        case EmptyTree() =>
    }
}

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.

Advertisements
This entry was posted in Linguagens de Programação, Ruby, Scala and tagged , , , , , , . Bookmark the permalink.

4 Responses to Orientado a Objetos versus Funcional

  1. 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]
    “`

  2. 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.

    • 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.

      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

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