Strukturell erzwingen No Red Children des roten Knotens

Question

Während des Studiums Learn You A Haskell For Great Good und Purely Functional Data Structures dachte ich zu versuchen, eine Red Black tree Reimplementierung beim Versuch, eine andere Struktur Invariante strukturell zu erzwingen.

Paraphrasieren Okasaki Code, seine Knoten sieht in etwa wie folgt aus:

import Data.Maybe 

data Color = Red | Black 

data Node a = Node { 
    value :: a, 
    color :: Color, 
    leftChild :: Maybe (Node a), 
    rightChild :: Maybe (Node a)} 

Eine der Eigenschaften eines Rot-Schwarz-Baum ist, dass a red node cannot have a direct-child red node, also versuchte ich dies wie folgt zu kodieren:

import Data.Either 

data BlackNode a = BlackNode { 
    value :: a, 
    leftChild :: Maybe (Either (BlackNode a) (RedNode a)), 
    rightChild :: Maybe (Either (BlackNode a) (RedNode a))} 
data RedNode a = RedNode { 
    value :: a, 
    leftChild :: Maybe (BlackNode a), 
    rightChild :: Maybe (BlackNode a)} 

Dies gibt die Fehler:

Multiple declarations of `rightChild' 
Declared at: :4:5 
      :8:5 


Multiple declarations of `leftChild' 
Declared at: :3:5 
      :7:5 


Multiple declarations of `value' 
Declared at: :2:5 
      :6:5 

ich habe versucht, mehr Änderungen des vorherigen Codes, aber alle Fehler bei der Kompilierung. Was ist der richtige Weg, dies zu tun?

Answer 1

Unterschiedliche Datensatztypen müssen unterschiedliche Feldnamen haben. Zum Beispiel ist dies nicht erlaubt:

data A = A { field :: Int } 
data B = B { field :: Char } 

während dies OK ist:

data A = A { aField :: Int } 
data B = B { bField :: Char } 

Die ersten beiden Projektionen zu definieren versuchen würde

field :: A -> Int 
field :: B -> Char 

aber leider können wir nicht haben ein Name mit zwei Arten. (Zumindest nicht so einfach ...) Dieses Problem ist in OOP-Sprachen nicht vorhanden, wo Feldnamen niemals allein verwendet werden können, sondern sofort auf ein Objekt angewendet werden müssen, wie in object.field - was eindeutig ist , vorausgesetzt, wir kennen bereits den Typ object. Haskell erlaubt Standalone-Projektionen, wodurch die Dinge hier komplizierter werden.

Dieser Ansatz definiert stattdessen

aField :: A -> Int 
bField :: B -> Char 

und vermeidet das Problem.

Wie oben bei @dfeuer erwähnt, wird GHC 8.0 diese Einschränkung wahrscheinlich lockern.