カスタムデータを含むHaskellバイナリ検索ツリー

Question

カスタムデータタイプブックのバイナリ検索ツリーを作成したいとします。ブックには、名前とページの2つの属性があります。ツリーのノードとして属性ページを使用したいと思います。私は木を定義することに固執しました。誰でもリソースを教えてくれますか？私が試したコードはここにあります（動作していません）

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秒以上を保持できると仮定しよう。この場合

、我々は期待：aはBook、または任意の他の適切なタイプとすることができ

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

を。ただし、treeInsertがBookで動作するには、BookにOrdインスタンスが必要です。すべてのタイプで動作するように意図されているのでBookはこの定義に表示されていないことを

singleton a = Node a EmptyTree EmptyTree 

注：

singleton機能だけNodeに全体aを置きます。

insertTreeの機能にはBookも含まれませんが、引数として必要なのは、Ordのインスタンスを利用します。

編集

あなたはTreeは、あなたのようにそれを定義する必要があり、Bookでのみ動作する場合：

data Tree = EmptyTree | Node Book Tree Tree 

の関数の型シグネチャを、その後になる：

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

singletonの実装は上記と同じになります（Book全体をNodeに入れてください）。 ）。

insertTreeはBookを処理していることが分かっているため、を取得できないため、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があり、正しいタイプではないことがわかります。

がOrdを実装しているため、任意のタイプの値をtreeInsertに使用します。