5

私は赤黒木で遊んでいます：

-- Taken from Okasaki 1999
module RedBlackTree where

--node coloring data
--a node is R (red) or B (black)
data Color = R | B

--tree constructor
--a RBT can be E (empty) or be T (a non empty tree)
data RBT e = E | T Color (RBT e) e (RBT e)

--set operations on tree
type Set a = RBT a

--define an empty set
empty :: Set e
empty = E

--define a member of a set
--Sees if an item of type e is
--in a set if type e elements
member :: (Ord e) => e -> Set e -> Bool
member x E = False
member x (T _ a y b) | x <  y = member x a -- if less, go left
                     | x == y = True
                     | x >  y = member x b -- if more, go right


--tree operations
--Insert an element
insert :: (Ord e) => e -> Set e -> Set e
insert x s = makeBlack (ins s)
    where ins E = T R E x E --basically the typical BST insert
          ins (T color a y b) | x <  y = balance color (ins a) y b
                              | x == y = T color a y b
                              | x >  y = balance color a y (ins b)
          makeBlack (T _ a y b) = T B a y b --inserts a black node

-- balance operations
--case 1:
balance B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
--case 2:
balance B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
--case 3:
balance B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
--case 4:
balance B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
--generic balancing operation
balance color a x b = T color a x b

GHCi で次のステートメントを実行すると:

> RedBlackTree.insert ('b') (RedBlackTree.T R E ('a') E)

次のエラー メッセージは、 の show のインスタンスがないことを示していますSet Char。

<interactive>:116:1:
No instance for (Show (Set Char)) arising from a use of `print'
Possible fix: add an instance declaration for (Show (Set Char))
In a stmt of an interactive GHCi command: print it

member 'b' ...where ...is を呼び出すと、以前に実行されたステートメントが返されるため、ツリーが機能していることがわかります。戻り値はTrueです。この問題に関する他の SO の投稿を読んでいますが、それらに対して見つかった解決策 (例: Haskell: Deriving Show for custom type ) は機能しません。

たとえば、次のように追加します。

instance Show Set where:
    show (Set Char) = show Char

を使用してロードしようとすると、次のエラー メッセージが表示されます:l。

:l red-black-tree.hs [1 of 1] RedBlackTree のコンパイル ( red-black-tree.hs、解釈済み )

red-black-tree.hs:54:11: Not in scope: data constructor `Set'

red-black-tree.hs:54:15: Not in scope: data constructor `Char'

red-black-tree.hs:54:28: Not in scope: data constructor `Char'
Failed, modules loaded: none.

私がやろうとしていることにはいくつかの問題があると思いますが、利用可能なドキュメントからはそれを理解できないようです。

4

3 に答える 3

4

インスタンス コードが壊れています:

instance Show Set where
    show (Set Char) = show Char

  1. Setコンパイラは、それはデータ コンストラクターではないと不平を言いますが、そうではありません。それは型シノニム名です。Setしたがって、パターンで誤って使用しました。そこでデータ コンストラクターを使用できます。また、RBTデータ コンストラクターはTとEです。

  2. インスタンス宣言の種類が悪い:Setは のシノニムでRBTあり、RBT1 つの型引数があります。つまり、型から型への関数であり、種類シグネチャは* -> *です。ただし、Showインスタンスには引数のない型が必要です。これは型コンストラクターではなく型であり、指定したのでは*なく種類* -> *です。instance Show (RBT Char)したがって、またはのいずれかを指定して修正する必要がありますinstance (Show a) => RBT a。

おそらくあなたが望んでいたのは、「その中の文字を表示することで一連の文字を表示する」と書くことです。

したがって、インスタンスを修正するには:

instance Show (RBT Char) where
    show a = "something"

しかし、それは有用なものを何も示していません。作業を完了するには、RBT のコンストラクターでパターン マッチングを行う必要があります。

instance Show (RBT Char) where
    show E = "something"
    show (T a b c d) = "something else"

Showしかし、あなたのタスクでは、 と の派生インスタンスを使用するだけで簡単になりRBT aますColor。

于 2013-08-29T19:44:40.520 に答える
1

deriving派手な拡張機能は使用していないので、組み込みのメカニズムを使用できるはずですShow。

データ型のインスタンスを自動的に派生させるにShowは、型定義で使用されるすべての型にもShowインスタンスが必要です。すべての定義deriving (Show)の最後に追加するだけです。ほとんどの場合、型の構造的等価性テストと表示可能性が必要になるため、すべての型に追加する習慣を身につけたいと思うかもしれません。dataderiving (Eq, Show)data

また、 type aliasに対してはどのような種類のクラス インスタンスも作成できず、typeに対してのみ作成できます。キーワードtypeは、新しい型ではなく、型エイリアスを定義します。Show型のインスタンスを作成すると、は の単なるエイリアスであるため、RBT aとして宣言したものすべてに自動的に使用されます。Set aSet aRBT a

于 2013-08-29T19:10:46.280 に答える