Проблемы с переходом от функционального к OO

Ответ 1

Поскольку у вас есть 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), С++ и С#, у вас есть одинаковые шаблоны, чтобы помочь ввести безопасность. Они в основном работают как переменные типа в Haskell.

Этот пример находится в Scala, но для других языков OO вы должны сделать это аналогичным образом: Создайте абстрактный базовый класс и превратите конструкторы ваших данных в классы/объекты.

Ответ 2

Некоторые хорошие ответы здесь, но я думаю, что они все упускают возможность показать, что вам не хватает. Итак, вы показали это:

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, дерево пальцев или какая-либо другая древовидная структура, не имеет значения. На самом деле это должно быть скрыто. Важно то, что вы можете с ним сделать.

У вас возникли проблемы с этим, потому что вы приближаетесь к проблеме именно с того направления, которое вы не должны.

Не очень важная вещь

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 определил.

Это идеальная объектно-ориентированная архитектура: клиенты зависят от интерфейсов, структура данных скрыта.

Ответ 3

Здесь первый шаг для перехода к OO из функционального мышления: Объекты больше похожи на функции, чем аналогичные данные. Думайте о них как таковых; вместо функций, действующих на прозрачные структурированные данные, теперь у вас есть непрозрачные глотки абстрактного поведения.

Размышляя об этом с точки зрения "хорошо, вот структура моих данных, теперь я..." идет об этом назад.

Попробуйте что-то вроде этого:

• Начнем с выяснения основных действий, которые могут быть выполнены с вашим B-деревом (не забывайте о таких вещах, как show и fmap здесь), и создайте класс на основе этих.

• Для типа суммы, такого как ваше дерево, может быть проще оставить базовый класс пустым и использовать подклассы для разных вариантов конструкторов данных. Как правило, в OO, где угодно, вы должны сделать какой-то выбор, который кардинально изменит последующее поведение, решительно рассмотрите использование полиморфизма подтипов, чтобы отличать случаи.

• Старайтесь не беспокоиться о внутреннем представлении до тех пор, пока вам не понадобится, и не позволяйте деталям представления утечки из класса. Наличие кучи методов GetFoo(), возвращающих примитивные типы, является признаком Doing It Wrong.

И, наконец: Помните, что вы используете Scala. Это гибридный язык по какой-то причине; не все имеет смысл делать в стиле OO. Переверните книгу "Образцы рисунков", и вы обнаружите, что половина ее касается барочных, обходных решений с высоким уровнем обслуживания для недостающих функций языка.

Ответ 4

Определите "здравомыслящий". На самом деле, это классно: это первый раз, когда я видел, что у кого-то возникают проблемы с функциональностью до ОО, а не с другой стороны.

Истина заключается в том, что у вас будет больше возможностей сделать это OO; что одна из причин функциональности хорошая. Вы сталкиваетесь с конкретным случаем, в котором функциональность имеет преимущества.

На языке OO (это не означает, что какой-либо конкретный язык, просто псевдокод) вам понадобится класс для node

class Node
  children : array of Node;
end

а затем у вас есть методы, например, добавить node в качестве дочернего элемента, чтобы вы могли с ним что-то делать.

Затем вы создаете класс BTree с помощью node для вставки, балансировки и т.д.

Ответ 5

ОК, время для шоковой терапии: Java. Ваш тип BTree становится вершиной иерархии классов. Нет стилей, вы вместо этого переписываете методы equals и toString (но не эквивалент Read). Затем вы помещаете все функции внутри объектов, как методы (часто абстрактную версию в BTree и конкретные версии в подклассах). Поскольку было бы бесполезно использовать новый экземпляр для каждого Листа, мы обманываем повторное использование статического поля (которое инициализируется с использованием анонимного класса) вместо этого (где мы снова обманываем, оставляя общий тип, потому что 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

Ответ 6

Я не знаю Scala, но я знаю Java.

В Java и объекте часто моделируется конкретная вещь, например: автомобиль или B-дерево и т.д.

Объект будет хранить данные (информацию) об этой вещи. У объекта также будет поведение, которое может быть выполнено в отношении данных (например: открыть дверь автомобиля), которые часто меняют состояние вещи (изменяют данные). Поведение (метод) также может просто указывать нам информацию о состоянии объекта и не изменять состояние. Кроме того, точная форма внутренних данных обычно скрыта (по хорошей практике).

Теперь в любой момент времени объект будет иметь точное состояние.

Итак, если мы думаем о двоичном древовидном объекте. мы можем иметь двоичное дерево (содержащее целые числа), которое выглядит так:

      4
    /   \
   2     1
 /      / \
1     3    1

Таким образом, в любой момент времени он будет иметь определенное количество узлов с определенными значениями, привязанными определенным образом.

Теперь нам нужно решить, как хранить информацию о нашем двоичном дереве. Это будет сделано внутренне в каждом двоичном древовидном объекте.

Итак, мы знаем, что каждое бинарное дерево будет состоять из некоторого количества узлов.

Итак, нам нужно каким-то образом хранить информацию о узлах. Теперь узлы должны хранить то, что они держат, а также то, что у них есть у левых/правых детей. Поскольку они содержат более одной части информации, нам нужно сохранить их как объекты.

Таким образом, каждому объекту node необходимо будет иметь переменную для значения, переменную, которая сообщает нам, что ее левый ребенок (если есть), и один для него правильный ребенок.

Итак, для node, содержащих целые значения, мы могли бы пойти:

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

}

Теперь не все узлы будут иметь левый или правый дочерний элемент (или вообще любые дети). Отсутствие левого ребенка представляется левой переменной, имеющей значение "null", а не ссылкой на фактический node.

Вышеприведенный код представляет собой node вообще без указания конкретной информации о состоянии, но конкретный node, который мы создали, будет иметь определенные значения для переменных "значение", "слева" и "справа".

Теперь мы знаем, что бинарное дерево состоит из нескольких узлов. Он начинается с корня node. И тогда корень node будет содержать информацию о том, какие узлы находятся ниже него (его дочерние элементы).

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) и addRightChild (Node addFrom, int value), методы. AddLeftChild сделает новый node с заданным значением (и без детей) и сделает его левым дочерним элементом node, заданным addFrom, но только если "addFrom" node еще не имеет левый ребенок.

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 state somehow to achieve this
   }

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

}

У нас также может быть метод добавления нового корня node, addRoot (значение int), поэтому мы можем добавить root node, когда мы сначала создадим двоичное дерево. Вероятно, у вас также есть методы (поведение) для удаления узлов. У вас могут быть методы поиска по дереву для значений/узлов или для получения информации о дереве (например: глубина, количество узлов).

Затем мы могли бы написать некоторый код, чтобы фактически создавать двоичные древовидные объекты, каким-то образом взаимодействовать с ними, например:

// 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 (только корень node)

           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.