Instancing Monoid für einen Typ

Question

Ich habe einen Typ in Haskell, um eine Map mehrere Werte zu einem Schlüssel zugeordnet haben.

Wenn ich kompilieren den folgenden Code:

type Mapa k v = Map k [v] 

instance Monoid (Mapa k v) where 
    --mempty :: Mapa k v 
    mempty = DM.empty 
    --mappend :: Mapa k v -> Mapa k v -> Mapa k v 
    mappend a b = DM.unionWith (++) a b 

GHCi wird werfen:

Illegal instance declaration for `Monoid (Map k [v])' 
    (All instance types must be of the form (T a1 ... an) 
    where a1 ... an are *distinct type variables*, 
    and each type variable appears at most once in the instance head. 
    Use -XFlexibleInstances if you want to disable this.) 
In the instance declaration for `Monoid (Map k [v])' 

Should Karte ein newtype oder ein data sein; oder was ist das Problem?

Answer 1

In diesem Fall möchten Sie newtype erstellen. Wenn Sie einfach type verwenden, erstellen Sie einen Typ Synonym, die völlig kosmetisch ist - Mapa k v bedeutet genau das gleiche wie Map k [v]. Sie möchten stattdessen einen neuen Typ erstellen, da normale Maps bereits eine Monoid Instanz haben, die sich mit der neuen überschneiden würde, was zu einem verwirrenden Verhalten führt.

Da Ihr Mapa Typ in einer grundsätzlich anderen Art und Weise verhält, wollen Sie es eine andere Art sein:

newtype Mapa k v = Mapa (DM.Map k [v]) 

Als nächstes müssen Sie Ihre Instanz aktualisieren, auf neue Art zu arbeiten. Dies erfordert zwei Änderungen: Sie müssen Ihr Typ-Synonym auspacken und umbrechen, und Sie müssen eine Ord k-Einschränkung hinzufügen. Diese zweite ist notwendig, weil die Schlüssel einer Karte für die Gleichheit vergleichbar sein müssen und - da die Karte intern ein Baum ist - müssen sie geordnet werden. So wird Ihre neue Instanz wird wie folgt aussehen:

instance Ord k => Monoid (Mapa k v) where 
    mempty = Mapa DM.empty 
    mappend (Mapa a) (Mapa b) = Mapa $ DM.unionWith (++) a b 

Matching gegen Mapa a können Sie die zugrunde liegenden Map zuzugreifen; Sie können dann normale Map Funktionen darauf verwenden. Nachdem Sie fertig sind, müssen Sie es nur erneut in Mapa einpacken.

Die Verwendung eines anderen Typs wie diesem, den Sie ein- und auspacken müssen, ist ein wenig unpraktisch, aber das ist der Preis, den Sie bezahlen müssen, um verschiedene Instanzen zu haben. Es macht auch die Tatsache, dass Mapa etwas völlig anderes als eine normale Karte viel deutlicher darstellt.

Ein wenig Stil Hinweis ist, dass Sie Funktionen mit Backticks definieren können, wie Infix:

Mapa a `mappend` Mapa b = ... 

Ich denke, das für Monoide klarer ist, weil der Monoid Betrieb normalerweise als Infixoperator verwendet wird.

Schließlich ist der Grund, warum Sie newtype und nicht data verwenden möchten, weil newtype keinen Laufzeitaufwand hat: es ist nur wichtig für den Typchecker. Konzeptionell ist dies sinnvoll - Sie erstellen nicht wirklich einen neuen Typ, sondern verwenden denselben zugrunde liegenden Typ auf unterschiedliche Weise mit verschiedenen Instanzen.