Haskell derivanti Visualizza grado

Question

sto giocando con un albero rosso-nero:

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

Se eseguo la seguente dichiarazione in GHCi:

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

Il seguente messaggio di errore mi dice di non v'è un istanza di spettacolo per 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 

so che l'albero sta funzionando perché chiamando 01.232.dove ... è l'istruzione precedentemente eseguita, il valore restituito è True. Ho letto altri post SO su questo problema ma le soluzioni trovate per loro (ad es. Haskell: Deriving Show for custom type) non funzionano.

Ad esempio, aggiungendo:

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

ricevo il seguente messaggio di errore quando provo a caricare utilizzando :l:

: L rosso-nero-tree.hs [1 di 1] RedBlackTree compilazione (rosso-nero-tree.hs, interpretati)

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. 

Penso che ci siano alcuni problemi in corso con quello che sto cercando di fare ma non riesco a capirlo dalla documentazione disponibile.

Answer 1

Non hai estensioni di fantasia in uso, quindi dovresti essere in grado di utilizzare il meccanismo deriving integrato per Show.

Per ottenere automaticamente un'istanza Show per un tipo di dati, tutti i tipi utilizzati nella definizione del tipo devono anche avere istanze Show. Basta aggiungere deriving (Show) alla fine di tutte le delle definizioni data. Potresti voler prendere l'abitudine di aggiungere deriving (Eq, Show) a tutti i tuoi tipi data, poiché quasi sempre vorrai test di equità strutturale e visualizzabilità per i tuoi tipi.

Inoltre, non si può fare un'istanza della classe di qualsiasi tipo per un tipo alias, solo per un tipo di . La parola chiave type definisce un alias di tipo, non un nuovo tipo. Se si crea un'istanza per il proprio tipo RBT a, questa verrà automaticamente utilizzata per qualsiasi cosa che si dichiara come Set a, poiché è solo un alias per RBT a.

Answer 2

Il codice esempio è rotto:

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

1. Il compilatore si lamenta che Set non è un costruttore di dati, e non è - è un nome di tipo sinonimo. Quindi hai erroneamente utilizzato Set in uno schema. È possibile utilizzare i costruttori di dati qui - e per i costruttori di dati RBT sono T e E.

2. tua dichiarazione di istanza è mal kinded: Set è sinonimo di RBT e RBT ha un argomento di tipo, cioè si tratta di una funzione da tipo a tipo, con una firma sorta di * -> *. Ma l'istanza Show richiede un tipo senza argomento, ovvero un tipo e non un costruttore di tipo, tipo * anziché * -> * fornito. Quindi dovresti correggerlo fornendo instance Show (RBT Char) o instance (Show a) => RBT a.

Quello che probabilmente volevi è scrivere "mostra un set di caratteri mostrando caratteri in esso".

Quindi, per risolvere il tuo esempio:

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

Ma non mostra nulla di utile. Hai bisogno di fare il pattern matching sui costruttori di RBT per ottenere il lavoro fatto:

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

Ma per il vostro compito sarà più semplice solo per utilizzare i derivati ​​Show istanze per RBT a e Color.

Answer 3

Per trasformare un valore in una stringa, Haskell utilizza una cosiddetta classe di tipo. Semplificato, le classi di tipi forniscono solo funzioni che si comportano in modo diverso a seconda del tipo di argomento. Questo approccio è molto simile all'overload del metodo noto dai linguaggi di programmazione orientati agli oggetti. La classe di tipo Show fornisce una funzione denominata show che trasforma un valore di un tipo in una stringa. Ad esempio, l'espressione show 1 produce la stringa "1". Se esiste una funzione show che trasforma un valore di un tipo in una stringa, diciamo che esiste un'istanza della classe di tipo Show per questo tipo. In altre parole, esiste un'istanza della classe di tipo Show per i numeri interi.

Questa funzione show viene utilizzata anche quando si valuta un'espressione in ghci. Pertanto, ti dice che non c'è istanza (Show (Set Char)), in altre parole, non sa come trasformare un valore di tipo Set Char in una stringa. Per tipi personalizzati come i tipi Set, RBT e Color, è necessario fornire istanze della classe di tipo Show per visualizzare i valori di tali tipi sulla console. Per definire un'istanza della classe di tipo Show per il tipo Color, è possibile utilizzare la seguente definizione.

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

Cioè, se si scrive R in ghci, verrà stampata Red. Per i tipi di dati Haskell semplici, esiste una definizione canonica della classe di tipo Show. Ad esempio, la definizione canonica di Show per Color è la seguente.

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

per alleviare l'utente dalle istanze che definiscono come questo, Haskell fornisce un cosiddetto "meccanismo di deriva". Cioè, se si scrive

deriving (Show) 

dopo la definizione di un tipo di dati, il compilatore genera un'istanza canonica della classe Show tipo per il tipo di dati.

Se un tipo di dati utilizza un altro tipo di dati, derivare un'istanza Show del primo richiederà un'istanza Show di quest'ultimo. Ad esempio, considerare il seguente tipo di dati.

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

tipo I dati RBT utilizza il tipo Color nella sua definizione. L'istanza canonica Show del costruttore T inizierà con "T" e in seguito mostrerà il valore di tipo Color. Pertanto, la derivazione dell'istanza Show per RBT richiede un'istanza di Show per .