Problems on migrating from functional to OO

Question

I'm used to work with functional programming (mainly Haskell) and I'm beginning with OO (scala).

I'm having troubles on translating my code. For instance, that's my Haskell definition of a B-tree:

data BTree a = 
    Leaf
    |Node2 (BTree a) a (BTree a)
    |Node3 (BTree a) a (BTree a) a (BTree a)
    deriving (Eq,Read,Show) 

It's quite simple. My tree is empty, or it has a value and is a father of two trees or it is a father of 3 sub trees.

What is it on OO? I have no clue. I just can't figure out how can I do it in a sane way.

Answer 1

Some good answers here, but I think they all miss the opportunity to show the point you are missing. So, you have shown this:

data BTree a = 
    Leaf
    |Node2 (BTree a) a (BTree a)
    |Node3 (BTree a) a (BTree a) a (BTree a)
    deriving (Eq,Read,Show)

And asked how do you implement this in an object-oriented fashion. So, here it is:

Most important thing

trait Tree[A] {
  // not required because it is inherited from AnyRef
  // def equals(other: Any): Boolean

  // not required because it is inherited from AnyRef
  // def toString: String

  // does not belong in the object
  // def fromString(input: String): Tree[A]

  // Stuff that is missing but is needed
  def isEmpty: Boolean
  def value: Option[A]
  def subtrees: Seq[Tree[A]]
  def iterator: Iterator[A]
  def depthFirstIterator: Iterator[A]
  def breadthFirstIterator: Iterator[A]
}

So, here's the deal: when you speak of object orientation, that you have a BTree, a finger tree, or whatever other tree structure is irrelevant. In fact, it should be hidden. What is relevant is what you can do with it.

You are having trouble doing this because you are approaching the problem from precisely the direction you shouldn't.

The not-so-important thing

sealed abstract class BTree[A] extends Tree[A]
object BTree {
  def apply[A](input: String): BTree[A] = { /* factory */ null.asInstanceOf[BTree[A]] }
  private case object Leaf extends BTree[Nothing] {
    // method implementation
  }
  private case class Node2[A](value: A, private one: BTree[A], private two: BTree[A]) extends BTree[A] {
    // method implementation
  }
  private case class Node3[A](value: A, private one: BTree[A], private two: BTree[A], private three: BTree[A]) extends BTree[A] {
    // method implementation
  }
}

Now here you actually offer an implementation, but the details of the BTree are completely hidden. You only get to use the methods that Tree has defined.

This is the ideal object oriented architecture: clients depend on interfaces, data structure is hidden.