Problems on migrating from functional to OO

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.

---

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.

---

Here's a first step for getting to OO from a functional mindset: Objects are more like functions than like data. Think of them as such; instead of functions acting on transparent, structured data, now you have opaque globs of abstract behavior.

Thinking of it in terms of "okay, here is the structure of my data, now I..." is going about it backwards.

Try something like this:

• Start by figuring out what are the fundamental actions that can be done with your B-tree (don't forget things like show and fmap here) and design the class based on those.

• For a sum type like your tree, it can be easier to leave the base class empty and use subclasses for different variations on the data constructors. As a rule of thumb in OO, anywhere you have to make some sort of choice that drastically changes the subsequent behavior, strongly consider using subtype polymorphism to distinguish cases.

• Try not to worry about the internal representation until you have to, and don't let representation details leak out of the class. Having a bunch of GetFoo() methods that return primitive types is a sign of Doing It Wrong.

And finally: Remember that you're using Scala. It's a hybrid language for a reason; not everything makes sense to do in OO style. Flip through the Design Patterns book and you'll find that half of it is about baroque, high-maintenance workarounds for missing language features.

---

Since you have Scala in your tag-list, here is how it would be done in Scala:

You have a base trait (in Haskell the type), and derived from that all the Haskell constructors as case classes. That way you can use them in Scala pattern matching as well.

sealed trait Tree[+A]

case object Leaf extends Tree[Any]
case class Node2[+A](a: A,  t1: Tree[A], t2: Tree[A]) extends Tree[A]
case class Node3[+A](a: A, b: A,  t1: Tree[A], t2: Tree[A], t2: Tree[A]) extends Tree[A]

In languages like Java (since 1.5), C++ and C# you have the same kind of templates to help type safety. They basically work like the type variables in Haskell.

This example is in Scala, but for other OO languages you would do it in a similar way: Create an abstract base class and turn the constructors of your data into classes/objects.

---

Define "sane". Actually, this is cool: it's the first time I've seen someone having trouble going from functional to OO rather than the other way.

The truth is that you're going to have more stuff to do it OO; that's one reason functional is nice. You're hitting a specific case in which functional has advantages.

In an OO language (this isn't meant to be any specific language, just pseudocode) you're going to need a class for node

class Node
  children : array of Node;
end

and then you have methods to, for example, add a node as a child so you can do things with it.

Then you create a BTree class using Node to do insertion, balancing, and so on.

---

OK, time for the shock therapy: Java. Your type BTree becomes the top of the class hierarchy. No typeclasses, you overwrite the equals and toString methods instead (no equivalent for Read, though). Then you put all functions inside the objects, as methods (often an abstract version in BTree, and concrete versions in the sub-classes). As it would be wasteful to use a new instance for every Leaf, we cheat an reuse a static field (wich is initialized using an anonymous class) instead (where we cheat again by leaving off the generic type, because Java has no "bottom" like Scala's Nothing). Of course this is only a very crude sketch without error handling etc. And yes, it gets really verbose, so be happy if you can use Scala instead ...

public abstract class BTree<A> {
   public static final BTree LEAF = new BTree {
      //concrete implementations of the methods 
      public boolean isEmpty(){ return true; } 
      public String toString() { return ""; }
   }
   public abstract boolean isEmpty(); 
   //concrete methods that are the same for all sub-classes
   //abstract methods that are different
}

public class Node2<A> {
   private BTree<A> left; 
   private BTree<A> right; 
   private A a;

   public Node2(BTree<A> left, A a, BTree<A> right) {
      this.left = left;
      this.a = a;
      this.right = right;  
   }

   public String toString() {
      return "(" + left +  a + right +  ")";
   }

   public boolean equals(Object o) {
      if (o instanceof Node2) {
          Node2<A> n2 = (Node2<A>) n2;
          return a.equals(n2.a) && left.equals(n2.left) && right.equals(n2.right);
      }
      return false;    
   }

   public boolean isEmpty(){ return false; } 
   //other concrete methods
}  

//same for Node3

---

I don't know Scala, but I know Java.

In Java, and object, will often model a specific thing, eg: a car, or a B-tree etc.

An object will store data (information) about this thing. An object will also have behaviour that can be done with respect to the data (eg: open the car's door) which will often change the state of the thing (change the data). The behaviour (method) might also just tells us information about the object's state and not change the state though. Also, the exact form of the internal data is usually hidden (by good practice).

Now at any point in time an object will have an exact state.

So if we think about a binary tree object. we might have a binary tree (containing integers) that looks exactly like this:

      4
    /   \
   2     1
 /      / \
1     3    1

So at any point in time it's going to have a certain number of nodes with certain values, attached in certain ways.

Now we need to decide how to store information about our binary tree. This will be done internally in each binary tree object.

So we know each binary tree is going to be made up some number of nodes.

So we'll need some way to store information about nodes. Now nodes we need to store what value they hold as well as what left/right children they have. Because they contain more than one piece of information we'll need to store these as objects.

So each node object will need to have variable for the value, a variable which tells us what its left child is (if any), and one for it's right child.

So for a node containing integer values we could go:

class Node {
  int value;
  Node left;
  Node right;

}

Now not all nodes will have a left or right child (or any children at all). A lack of left child is represented by the left variable having value 'null' rather than referring to an actual node.

The above code represents a node in general without containing specific state information, but a particular node that we've created will have a particular values for the 'value', 'left' and 'right' variables.

Now we know a binary tree is made up of a number of nodes. It starts with a root node. And then the root node will just contain the information about what nodes are below it (its children).

class BinaryTree {
    Node root;


}

But we'll also want to give our binary tree's (ie. the objects) some behaviour so we can do some interesting things with them. After all, why do we even want a binary tree anyway -- so we can do something useful with it!

First we need a "constructor" so we can make a binary tree object, and set it's state to some initial values. So we'll just make our binary trees start off being empty. We represent this by having 'root' variable null. This just means we don't even have a root! So it's empty. We write a constructor in the same form as a method (a function which belongs to a class/object) except we give it the same name as the class itself:

class BinaryTree {
    Node root;

    BinaryTree() {
       root = null; // make it so that newly made objects start off being empty
   }
}

We'll probably want to give our binary tree objects some behaviour/methods so that we can actually build up whatever kind of binary tree that we want. Only being able to make empty trees and not change them probably won't be useful!

So we might make an addLeftChild(Node addFrom, int value), and addRightChild(Node addFrom, int value), methods. The addLeftChild will make a new node having the given value (and no children), and make it the left child of the node given by addFrom, but only if the 'addFrom' node doesn't already have a left child.

class BinaryTree {
    Node root;

    BinaryTree() {
       root = null; // make it so that newly made objects start off being empty
   }

   Node addLeftChild(Node addFrom, int value) {
            // change the binary tree's state somehow to achieve this
   }

   Node addRightChild(Node addFrom, int value) {
            // change the binary tree's state somehow to achieve this
   }

}

We might also have a method to add a new root node, addRoot(int value), so we can add a root node when we first make a binary tree. You would probably also have methods (behaviour) to remove nodes. You might have methods to search the tree for values/nodes, or to give you information about the tree (eg: depth, number of nodes).

Then we might write some code to actually make binary tree objects, interact with them in some way, eg:

// this is some main method,etc
BinaryTree ourBT = new BinaryTree(); // make an new binary tree
                                    // remember these start off empty

 Node rootNode; // variable so we can tell 
                // later add methods which node to add from

 rootNode =  ourBT.addRoot(4);

this would give us this so far as this binary tree called ourBT (just a root node)

           4

then we might go:

ourBT.addLeftChild(rootNode, 3); // remember the parameter rootNode refers 
                                 // to the root node we just added before

which would leave our binary tree in this state:

           4
         /
        3

Then we could go:

   ourBT.addRightChild(rootNode, 1); 

which would leave our binary tree in this state:

           4
         /  \
        3    1

Then after building up our binary tree we could maybe then do some other interesting stuff with it (eg: searching, removing)

This probably isn't the best example, but hopefully I've given you a bit of insight into how custom data structures are written in OO style.