사용자 지정 데이터가 포함 된 Haskell 이진 검색 트리

Question

사용자 지정 데이터 형식의 이진 검색 트리를 만들고 싶습니다. 책에는 이름과 페이지의 두 가지 속성이 있습니다. 속성 페이지를 트리의 노드로 사용하고 싶습니다. 나는 나무를 정의하는 데에 갇혀있다. 누구든지 자원으로 저를 도울 수 있습니까? 시도한 코드는 다음과 같습니다 (작동하지 않습니다).

import System.IO 
import Data.List 

data Book = Book{ 
    name:: String, 
    page::Int 
}deriving (Show) 

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) 

singleton :: (Book _ x) -> Tree x 
singleton (Book _ x) = Node x EmptyTree EmptyTree 

treeInsert :: (Ord a) => a -> Tree a -> Tree a 
treeInsert (Book _ x) EmptyTree = singleton (Book _ x) 
treeInsert (Book _ x) (Node a left right) 
    | x == a = Node x left right 
    | x < a = Node a (treeInsert (Book _ x) left) right 
    | x > a = Node a left (treeInsert (Book _ x) right) 

Answer 1

올바른 유형의 서명을 파악할 수 있습니다.

Tree이 Book을 보유하고 page으로 주문한다고 가정합니다.

Tree에만 Book을 저장하려면 매개 변수화 할 필요가 없습니다. 그러나 Tree을 매개 변수화 했으므로 이제는 Book 개 이상을 보유 할 수 있다고 가정 해 봅시다.

이 경우

, 우리는 기대 :

singleton :: a -> Tree a 
treeInsert :: Ord a => a -> Tree a -> Tree a 

a는 Book, 또는 다른 적절한 유형이 될 수있는 곳. 그러나 treeInsert이 Book과 작동하려면 Book에 Ord 인스턴스가 있어야합니다.

는 singleton 기능은 단지 Node으로 전체 a을두고 :이 모든 유형에서 작동하도록 구성되어 있기 때문에이 정의에 나타나지 않습니다

singleton a = Node a EmptyTree EmptyTree 

주 Book있다.

insertTree 함수도 Book을 언급하지 않지만 인수에 필요한 Ord 인스턴스를 이용합니다.

편집

당신이 Tree 만 Book 작업 할 경우에, 당신이로 정의한다 :

data Tree = EmptyTree | Node Book Tree Tree 

은 함수의 유형 서명은 다음이 될 :

singleton :: Book -> Tree 
insertTree :: Book -> Tree -> Tree 

singleton의 구현은 위와 동일합니다 (전체 Book을 Node에 넣으십시오).).

insertTree은 Book을 처리하고 있으므로 이제는 page을 얻을 수 있으므로 더 이상 Ord 인스턴스가 필요하지 않습니다.

내가 당신에게 추천

treeInsert b EmptyTree = singleton b 
treeInsert b (Node a l r) 
    | page b == page a = ... 

Answer 2

모든 책 엔티티를 사용하도록하고 Book에 대한 Ord 예 :

이 시작됩니다.이것에

instance Eq Book where 
    (Book _ n1) == (Book _ n2) = n1 == n2 

instance Ord Book where 
    (Book _ n1) > (Book _ n2) = n1 > n2 

그리고 당신의 코드를 변경 :

data Book = Book { 
    name :: String, 
    page :: Int 
} deriving (Show) 

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) 

singleton :: a -> Tree a 
singleton x = Node x EmptyTree EmptyTree 

treeInsert :: (Ord a) => a -> Tree a -> Tree a 
treeInsert x EmptyTree = singleton x 
treeInsert x (Node a left right) 
    | x == a = Node x left right 
    | x < a = Node a (treeInsert x left) right 
    | x > a = Node a left (treeInsert x right) 

당신은 (Book _ n)이 올바른 유형이 아닌 것을 볼 수, Book이다.

Book이 Ord을 구현하므로 어떤 유형의 값도 treeInsert으로 사용됩니다.