从函数式迁移到面向对象的问题

Question

我习惯于使用函数式编程（主要是 Haskell），并且我从 OO（scala）开始。

我在翻译代码时遇到了麻烦。例如，这是我对 B 树的 Haskell 定义：

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

它非常简单。我的树是空的，或者它有一个值并且是两棵树的父亲，或者它是 3 个子树的父亲。

OO 上有什么？我不知道。我只是不知道如何才能以理智的方式做到这一点。

Answer 1

这里有一些很好的答案，但我认为他们都错过了展示您所缺少的观点的机会。因此，您已经展示了这一点：

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

并询问如何以面向对象的方式实现这一点。所以，这就是：

最重要的事情

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

所以，事情是这样的：当你谈到面向对象时，你有一个 BTree、一棵手指树或任何其他树结构不相关< /em>。事实上，它应该隐藏。相关的是您可以用它做什么。

您在执行此操作时遇到困难，因为您正在从不应该的方向处理问题。

不那么重要的事情

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

现在，您实际上提供了一个实现，但 BTree 的细节完全隐藏了。您只能使用 Tree 定义的方法。

这是理想的面向对象架构：客户端依赖于接口，数据结构是隐藏的。

Answer 2

这是从函数式思维方式转向面向对象的第一步：对象更像函数而不是数据。这样想它们；现在，您拥有的是不透明的抽象行为，而不是作用于透明的结构化数据的函数。

从“好吧，这是我的数据结构，现在我......”的角度思考它是倒退的。

尝试这样的事情：

• 首先弄清楚可以使用 B 树执行哪些基本操作（不要忘记诸如 show 和 fmap此处）并基于这些设计类。

• 对于像树这样的总和类型，将基类留空并使用子类来实现数据构造函数的不同变体会更容易。作为 OO 中的经验法则，任何地方您必须做出某种选择来彻底改变后续行为，请强烈考虑使用子类型多态性来区分情况。

• 除非必要，否则尽量不要担心内部表示，并且不要让表示细节泄漏到类之外。拥有一堆返回原始类型的 GetFoo() 方法是做错事的标志。

最后：请记住您使用的是 Scala。它是一种混合语言是有原因的；并非所有事情都以 OO 风格进行是有意义的。翻阅《设计模式》一书，您会发现其中一半内容是关于针对缺失的语言功能的巴洛克式的、高维护性的解决方法。

Answer 3

既然你的标签列表中有 Scala，那么在 Scala 中是如何完成的：

你有一个基本特征（在 Haskell 中是类型），并从所有 Haskell 构造函数派生为 case 类。这样您也可以在 Scala 模式匹配中使用它们。

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]

在 Java（自 1.5 起）、C++ 和 C# 等语言中，您可以使用相同类型的模板来帮助实现类型安全。它们基本上像 Haskell 中的类型变量一样工作。

此示例使用 Scala，但对于其他 OO 语言，您可以采用类似的方式进行操作：创建一个抽象基类并将数据的构造函数转换为类/对象。

Answer 4

定义“理智”。实际上，这很酷：这是我第一次看到有人在从函数式转向面向对象而不是其他方式时遇到困难。

事实上，你将会有更多的事情要做；OO；这就是功能性良好的原因之一。您遇到的是功能性具有优势的特定情况。

在面向对象的语言中（这并不意味着是任何特定的语言，只是伪代码），您将需要一个节点类

class Node
  children : array of Node;
end

，然后您可以使用方法来添加节点作为子节点，这样您就可以做一些事情与它。

然后使用 Node 创建一个 BTree 类来执行插入、平衡等操作。

Answer 5

好的，休克疗法时间到了：Java。您的类型 BTree 成为类层次结构的顶部。没有类型类，您可以重写 equals 和 toString 方法（不过，Read 没有等效方法）。然后将所有函数作为方法放入对象中（通常是 BTree 中的抽象版本，子类中的具体版本）。因为为每个 Leaf 使用一个新实例是浪费的，所以我们欺骗了重用静态字段（使用匿名类初始化）（我们再次欺骗了泛型类型，因为 Java 没有“底层”）就像 Scala 的 Nothing）。当然，这只是一个非常粗略的草图，没有错误处理等。是的，它变得非常冗长，所以如果你可以使用 Scala 来代替，那就很高兴了......

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

Answer 6

我不懂Scala，但我懂Java。

在Java中，对象通常会对特定的事物进行建模，例如：汽车或B树等。

对象将存储有关该事物的数据（信息）。对象还将具有可以针对数据完成的行为（例如：打开车门），这通常会改变事物的状态（更改数据）。行为（方法）也可能只是告诉我们有关对象状态的信息，但不会更改状态。此外，内部数据的确切形式通常是隐藏的（通过良好的实践）。

现在，在任何时间点，对象都将具有精确状态。

因此，如果我们考虑一个二叉树对象。我们可能有一个看起来完全像这样的二叉树（包含整数）：

      4
    /   \
   2     1
 /      / \
1     3    1

因此在任何时间点，它都会有一定数量的具有特定值的节点，并以特定方式连接。

现在我们需要决定如何存储有关二叉树的信息。这将在每个二叉树对象内部完成。

所以我们知道每个二叉树将由一定数量的节点组成。

因此，我们需要某种方法来存储有关节点的信息。现在，我们需要存储节点所持有的值以及它们拥有的左/右子节点。因为它们包含不止一条信息，所以我们需要将它们存储为对象。

因此，每个节点对象都需要有一个值变量，一个变量告诉我们它的左子节点是什么（如果有），一个变量告诉我们它的右子节点。

因此，对于包含整数值的节点，我们可以这样：

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

}

现在并非所有节点都有左或右子节点（或任何子节点）。缺少左子节点由值为“null”的左变量表示，而不是引用实际节点。

上面的代码表示一般的节点，不包含特定的状态信息，但是我们创建的特定节点将具有“value”、“left”和“right”变量的特定值。

现在我们知道二叉树是由许多节点组成的。它从根节点开始。
然后根节点将只包含有关其下面的节点（其子节点）的信息。

class BinaryTree {
    Node root;


}

但我们还想赋予二叉树（即对象）一些行为，以便我们可以用它们做一些有趣的事情。毕竟，为什么我们甚至想要一棵二叉树——这样我们就可以用它做一些有用的事情！

首先，我们需要一个“构造函数”，以便我们可以创建一个二叉树对象，并将其状态设置为一些初始值。所以我们会让我们的二叉树开始为空。我们通过将“root”变量设为 null 来表示这一点。这仅仅意味着我们甚至没有根！所以它是空的。我们以与方法（属于类/对象的函数）相同的形式编写构造函数，只是我们给它赋予与类本身相同的名称：

class BinaryTree {
    Node root;

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

我们可能想给我们的二叉树对象一些行为/方法，所以我们实际上可以构建我们想要的任何类型的二叉树。只能制作空树而不改变它们可能没有用！

因此，我们可以创建 addLeftChild(Node addFrom, int value) 和 addRightChild(Node addFrom, int value) 方法。 addLeftChild 将创建一个具有给定值（并且没有子节点）的新节点，并使其成为 addFrom 给定节点的左子节点，但前提是“addFrom”节点还没有左子节点。

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
   }

}

我们可能还有一个添加新根节点的方法，addRoot(int value)，因此我们可以在第一次创建二叉树时添加根节点。
您可能还会有删除节点的方法（行为）。您可能有方法在树中搜索值/节点，或者为您提供有关树的信息（例如：深度、节点数）。

然后我们可能会编写一些代码来实际创建二叉树对象，以某种方式与它们交互，例如：

// 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);

这将为我们提供这个称为 ourBT（只是根节点）的二叉树，

           4

然后我们可能会：

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

这将留下我们的处于这种状态的二叉树：

           4
         /
        3

然后我们可以：

   ourBT.addRightChild(rootNode, 1); 

这将使我们的二叉树处于这种状态：

           4
         /  \
        3    1

然后在构建我们的二叉树之后，我们也许可以用它做一些其他有趣的事情（例如：搜索，删除）

这可能不是'这是最好的例子，但希望我能让您深入了解如何以 OO 风格编写自定义数据结构。