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.

Answers


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.


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.


Need Your Help

want to stop restarting asynctask on orientation change

android

My application simply request the json data from url and displays it in TableLayout. I used asynctask to request the json data and then I use that jsondata to fill my TableLayout. It works correct ...