5

I am playing with a Red-Black tree:

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

If I execute the following statement in GHCi:

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

The following error message tells me there is not an instance of show for 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

I know the tree is working because by calling member 'b' ... where ... is the previously executed statement, the returned value is True. I've been reading the other SO posts on this problem but the solutions found for them (e.g.:Haskell: Deriving Show for custom type) does not work.

For example, by adding:

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

I get the following error message when I try to load using :l:

: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.

I think there are a few problems going on with what I'm trying to do but I can't seem to figure it out from the available documentation.

4

3 回答 3

5

为了将值转换为字符串，Haskell 使用了所谓的类型类。简化的类型类只是提供了根据参数类型而不同行为的函数。这种方法与面向对象编程语言中已知的方法重载非常相似。类型类Show提供了一个函数，该函数show将某种类型的值转换为字符串。例如，表达式show 1产生字符串"1"。如果有一个函数show将某种类型的值转换为字符串，我们就说这个类型有一个类型类的实例Show。换句话说，有一个Show整数类型类的实例。

show当您在 ghci 中评估表达式时，也会使用此函数。因此，它告诉您没有实例(Show (Set Char))，换句话说，它不知道如何将类型的值Set Char转换为字符串。对于自定义类型，例如您的 types Set，RBT，并且Color您必须提供类型类Show的实例才能在控制台上显示这些类型的值。Show要为类型定义类型类的实例，Color您可以使用以下定义。

instance Show Color where:
  show R = "Red"
  show B = "Black"

也就是说，如果你写入Rghci，它将打印Red. 对于简单的 Haskell 数据类型，有一个Show类型类的规范定义。例如，Showfor的规范定义Color如下。

instance Show Color where:
  show R = "R"
  show B = "B"

为了让用户不必像这样定义实例，Haskell 提供了一种所谓的“派生机制”。也就是说，如果你写

  deriving (Show)

在定义数据类型之后，编译器将为Show您的数据类型生成类型类的规范实例。

如果一种数据类型使用另一种数据类型，则派生Show前者的实例将需要Show后者的实例。例如，考虑以下数据类型。

data RBT e = E | T Color (RBT e) e (RBT e)

数据类型RBT使用Color其定义中的类型。构造函数的规范Show实例T将以“T”开头，然后显示 type 的值Color。因此，派生for 的Show实例RBT需要 for 的Show实例Color。

于 2013-08-29T19:45:55.037 回答
4

您的实例代码已损坏：

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

  1. 编译器抱怨这Set不是一个数据构造函数，它不是——它是一个类型的同义词名称。所以你错误地使用Set了一个模式。您可以在那里使用数据构造函数 -RBT数据构造函数是Tand E。

  2. 您的实例声明是恶意的：Set是的同义词RBT并且RBT有一个类型参数，即它是一个从类型到类型的函数，具有* -> *. 但是Showinstance 需要一个不带参数的类型，即类型而不是类型构造函数，*而不是* -> *您提供的类型。所以你应该通过提供instance Show (RBT Char)or来解决这个问题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 aand会更简单Color。

于 2013-08-29T19:44:40.520 回答
1

您没有使用任何花哨的扩展，因此您应该能够deriving使用Show.

为了自动派生Show数据类型的实例，类型定义中使用的所有类型也必须具有Show实例。只需添加deriving (Show)到所有data定义的末尾即可。您可能只想养成添加deriving (Eq, Show)所有data类型的习惯，因为您几乎总是需要对您的类型进行结构相等性测试和可展示性。

此外，您不能为类型别名创建任何类型的类实例，只能为类型创建。关键字type定义类型别名，而不是新类型。如果您Show为您的类型创建一个实例RBT a，它将自动用于您声明为 a 的任何内容Set a，因为Set a它只是RBT a.

于 2013-08-29T19:10:46.280 回答