Получение экземпляра Show на основе Haskell

Я играю с красно-черным деревом:

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

:l red-black-tree.hs [1 из 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.

Я думаю, что есть несколько проблем с тем, что я пытаюсь сделать, но я не могу понять это из доступной документации.


show haskell deriving
person Joe    schedule 29.08.2013    source источник
comment
Просто используйте data Tree a = ... deriving (Show)   -  person bheklilr    schedule 29.08.2013
comment
Добавление deriving (Show) в конец data RBT... дает мне следующее сообщение об ошибке: No instance for (Show Color) arising from the 'deriving' clause of a data type declaration   -  person Joe    schedule 29.08.2013
comment
Просто добавьте deriving (Show) в конец data Color = R | B   -  person nponeccop    schedule 29.08.2013

Ответы (3)


arrow_upward
5
arrow_downward

Для преобразования значения в строку Haskell использует так называемый класс типов. Упрощенные классы типов просто предоставляют функции, которые ведут себя по-разному в зависимости от типа их аргумента. Этот подход очень похож на перегрузку методов, известную из объектно-ориентированных языков программирования. Класс типов Show предоставляет функцию show, которая преобразует значение некоторого типа в строку. Например, выражение show 1 дает строку "1". Если есть функция show, которая преобразует значение некоторого типа в строку, мы говорим, что для этого типа существует экземпляр класса типов Show. Другими словами, существует экземпляр класса типов Show для целых чисел.

Эта функция show также используется при оценке выражения в ghci. Поэтому он говорит вам, что экземпляра (Show (Set Char)) нет, другими словами, он не знает, как преобразовать значение типа Set Char в строку. Для пользовательских типов, таких как ваши типы Set, RBT и Color, вы должны предоставить экземпляры класса типов Show, чтобы отображать значения этих типов на консоли. Чтобы определить экземпляр класса типов Show для типа Color, вы можете использовать следующее определение.

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

То есть, если вы запишете R в ghci, он напечатает Red. Для простых типов данных Haskell существует каноническое определение класса типов Show. Например, каноническое определение Show для 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", а затем показывать значение типа Color. Поэтому для получения экземпляра Show для RBT требуется экземпляр Show для Color.

person Jan Christiansen    schedule 29.08.2013

arrow_upward
4
arrow_downward

Код вашего экземпляра не работает:

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

  1. Компилятор жалуется, что Set не является конструктором данных, и это не так - это имя синонима типа. Итак, вы неправильно использовали Set в шаблоне. Там вы можете использовать конструкторы данных - а для RBT конструкторами данных являются T и E.

  2. Ваше объявление экземпляра неблагородно: Set является синонимом для RBT, а RBT имеет один аргумент типа, то есть это функция от типа к типу с доброй подписью * -> *. Но для экземпляра 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.

person nponeccop    schedule 29.08.2013

arrow_upward
1
arrow_downward

У вас нет никаких модных расширений, поэтому вы должны иметь возможность использовать встроенный механизм deriving для Show.

Для автоматического получения экземпляра Show для типа данных все типы, используемые в вашем определении типа, также должны иметь экземпляры Show. Просто добавьте deriving (Show) в конец всех ваших data определений. Возможно, вам захочется просто добавить deriving (Eq, Show) ко всем вашим типам data, так как вам почти всегда нужны тесты на структурное равенство и отображаемость для ваших типов.

Кроме того, вы не можете создать экземпляр класса любого вида для псевдонима типа, только для типа. Ключевое слово type определяет псевдоним типа, а не новый тип. Если вы создадите экземпляр Show для своего типа RBT a, он будет автоматически использоваться для всего, что вы объявите как Set a, поскольку Set a — это просто псевдоним для RBT a.

person Levi Pearson    schedule 29.08.2013