我正在使用红黑树进行操作:
-- 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)
以下错误信息告诉我,不存在用于 "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' ...
时返回的值是True
,其中...
是先前执行的语句。我已经阅读了其他有关此问题的SO帖子,但为它们找到的解决方案(例如:Haskell:为自定义类型推导Show)不起作用。例如,通过添加以下内容:
instance Show Set where:
show (Set Char) = show Char
当我尝试使用
:l
加载时,出现以下错误信息:
请注意,这是一个关于IT技术的问题。:l red-black-tree.hs [1 of 1] Compiling RedBlackTree ( red-black-tree.hs, interpreted )
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.
我认为在我所尝试做的事情中存在一些问题,但是从可用的文档中似乎无法解决它。
data Tree a = ... deriving (Show)
。 - bheklilrdata RBT...
的末尾添加deriving (Show)
会导致以下错误消息:No instance for (Show Color) arising from the 'deriving' clause of a data type declaration
。 - Joedata Color = R | B
的末尾添加deriving (Show)
即可。 - nponeccop