árvore

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))
    }
}

(more…)