함수에서 OO 로의 마이그레이션에 관한 문제

Question

저는 함수 프로그래밍 (주로 Haskell)을 사용하고 OO (scala)로 시작했습니다.

내 코드를 번역하는 데 문제가 있습니다. 예를 들어 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) 

매우 간단합니다. 내 나무는 비어 있거나 가치가 있으며 두 나무의 아버지이거나 3 개의 하위 나무를 가진 아버지입니다.

OO에는 무엇이 있습니까? 나는 단서가 없다. 나는 그걸 어떻게 정상적으로 할 수 있는지 알 수 없다.

Answer 1

는,이 스칼라에서 수행 될 것이다 어떻게 수업. 그런 식으로 스칼라 패턴 매칭에서도 사용할 수 있습니다. (1.5 이후) 자바, C++ 및 C# 같은 언어에서

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] 

당신은 유형의 안전에 도움이 템플릿의 같은 종류가 있습니다. 그것들은 기본적으로 Haskell의 타입 변수처럼 작동합니다.

이 예제는 스칼라이지만 다른 OO 언어의 경우 비슷한 방법으로 처리합니다. 추상 기본 클래스를 만들고 데이터 생성자를 클래스/객체로 변환합니다.

Answer 2

"제정신"을 정의하십시오. 사실, 이것은 멋지다 : 다른 방법보다는 기능적에서 OO로가는 데 어려움을 겪고있는 사람을 본 것은 처음이다.

진실은 당신이 그것을하기 위해 더 많은 것들을 가질 것이라는 것입니다; 그것이 기능적인 이유 중 하나입니다. 기능적으로 이점이있는 구체적인 경우를 치고 있습니다. 객체 지향 언어에서

(이것은, 특정 언어로 바로 의사를 의미하지 않는다)이 노드

에 대한

class Node 
    children : array of Node; 
end 

을하는 클래스를 필요 해요 다음이 방법이, 예를 들면, 노드를 자식으로 추가하면 작업을 수행 할 수 있습니다.

그런 다음 노드를 사용하여 삽입, 균형 조정 등을 수행하여 BTree 클래스를 만듭니다.

Answer 3

다음은 기능적 사고 방식에서 객체 지향을위한 첫 번째 단계입니다. 객체는 데이터와 비슷한 기능을합니다. 그 (것)들과 같은 생각하십시오; 투명하고 구조화 된 데이터에서 작동하는 함수 대신 이제 추상 동작의 불투명 한 덩어리를가집니다.

"좋아요, 여기 내 데이터의 구조가 있습니다, 지금은 ..."라고 생각하면 뒤로 거슬러 올라갑니다. (show 여기 fmap 같은 것들을 잊지 마세요) 당신의 B-나무와 함께 할 수있는 기본적인 행동이 무엇인지 파악하여

• 시작과 클래스를 설계 :

  시도의이 같은 그것들에 기초해서.

• 트리와 같은 합계 유형의 경우 기본 클래스를 비워두고 데이터 생성자의 변형에 따라 하위 클래스를 사용하는 것이 더 쉬울 수 있습니다. OO의 경험에 따르면, 후속 행동을 대폭 변경하는 선택의 여지가있는 곳이면 어디서든 하위 유형 다형성을 사용하여 사례를 구별하는 것이 좋습니다.

• 당신이해야 할 때까지 내부 표현에 대해 걱정할 필요가 없으며 표현 세부 사항이 클래스에서 누출되지 않도록하십시오. 프리미티브 유형을 반환하는 GetFoo() 메서드가 많다는 것은 Doing It Wrong의 표시입니다.

그리고 마지막으로 : 스칼라를 사용하고 있다는 것을 기억하십시오. 그것은 이유가있는 하이브리드 언어입니다. 모든 것이 OO 스타일로하는 것이 합리적이지는 않습니다. Design Patterns 책을 뒤집어 보면 절반 정도가 누락 된 언어 기능에 대한 바로크하고 유지 관리가 용이 ​​한 해결 방법이라는 것을 알 수 있습니다.case으로 모든 하스켈 생성자에서

당신은 (하스켈 타입의) 기본 특성을 가지고 있고, 파생 : 여기 당신이 당신의 태그 목록에 스칼라를 가지고 있기 때문에

Answer 4

충격 요법을위한 시간 : 자바. 유형 BTree는 클래스 계층 구조의 맨 위에 있습니다. typeclasses가 없으면 대신 equals 및 toString 메서드를 덮어 씁니다 (읽기에는 해당하지 않음). 그런 다음 모든 함수를 메서드 (메서드는 종종 BTree의 추상 버전과 하위 클래스의 구체적인 버전)에 넣습니다. 모든 Leaf에 대해 새 인스턴스를 사용하는 것은 낭비이기 때문에 대신 정적 필드 (익명 클래스를 사용하여 초기화 됨)를 재사용하지 않습니다 (Java가 제네릭 유형을 사용하지 않고 다시 속임수로 처리하는 이유는 Java가 "bottom" Scala의 Nothing처럼). 물론 이것은 오류 처리 등없이 매우 원유 스케치 아니라 그리고 네, 그것은

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 5

여기에 몇 가지 좋은 답변 ... 대신 스칼라를 사용할 수 있는지 너무 행복, 정말 자세한 얻을 수 있지만, 나는 그들이 생각 모두 당신이 놓친 부분을 보여줄 수있는 기회를 놓치게됩니다. 그래서, 당신은 이것을 보여 줬습니다 :

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에 정의 된 메서드 만 사용할 수 있습니다.

이것은 이상적인 객체 지향 아키텍처입니다. 클라이언트는 인터페이스에 의존하고 데이터 구조는 숨겨져 있습니다.

Answer 6

저는 스칼라를 모르지만 자바를 알고 있습니다.

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

tree 객체를 몇 가지 동작/메소드로 변환하여 실제로 원하는 모든 종류의 이진 트리를 만들 수 있습니다. 오직 빈 나무를 만들 수 있고 그들을 변경하지 아마도 유용하지 않습니다!

우리는 addLeftChild (노드 addFrom, int 값) 및 addRightChild (노드 addFrom, int 값) 메소드를 만들 수 있습니다. 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 값)를 추가하는 방법이있을 수 있습니다, 그래서 우리는 먼저 이진 트리를 할 때 우리는 루트 노드를 추가 할 수 있습니다. 노드를 제거하는 메서드 (비헤이비어)가있을 수도 있습니다. 트리에서 값/노드를 검색하거나 트리에 대한 정보 (예 : 깊이, 노드 수)를 제공하는 메소드가있을 수 있습니다.

그리고 우리는 어떤 식 으로든 그들과 상호 작용, 실제로 이진 트리 객체를 만들기 위해 몇 가지 코드를 작성할 수 있습니다 예 :

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

그런 다음 우리가 갈 수 : 우리가 할 수 우리의 이진 트리를 구축 한 후 다음

  4 
     /\ 
     3 1 

:

이

ourBT.addRightChild(rootNode, 1); 

이 상태에서 우리의 이진 트리를 떠날 것이다 어쩌면 그걸로 다른 흥미로운 것들을 할 수도 있습니다 (예 : 검색, 제거)

이것은 아마도 최고의 exa는 아닙니다. mple하지만 잘하면 사용자 정의 데이터 구조가 OO 스타일로 작성된 방법에 대해 약간의 통찰력을주었습니다.