Wo ist die Set-Klasse?

Question

In Haskell Data.Set implementiert einen konkreten Set-Typ. Normale [] Listen implementieren auch alle Operationen eines Satzes (in Data.List). Aber es scheint keine vordefinierte Set Typklasse zu geben, die beide implementieren. Sie können eine selbst implementieren:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies #-} 

module Set where 

import qualified Data.List as ConcreteList 
import qualified Data.Set as ConcreteSet 

class Set set a | set -> a where 
    empty :: set 
    singleton :: a -> set 
    insert :: a -> set -> set 
    delete :: a -> set -> set 
    union :: set -> set -> set 
    intersection :: set -> set -> set 
    member :: a -> set -> Bool 
    filter :: (a -> Bool) -> set -> set 

instance (Ord a) => Set (ConcreteSet.Set a) a where 
    empty = ConcreteSet.empty 
    singleton = ConcreteSet.singleton 
    insert = ConcreteSet.insert 
    delete = ConcreteSet.delete 
    union = ConcreteSet.union 
    intersection = ConcreteSet.intersection 
    member = ConcreteSet.member 
    filter = ConcreteSet.filter 

instance (Eq a) => Set [a] a where 
    empty = [] 
    singleton e = [e] 
    insert = (:) 
    delete = ConcreteList.delete 
    union = ConcreteList.union 
    intersection = ConcreteList.intersect 
    member = ConcreteList.elem 
    filter = ConcreteList.filter 

aber es scheint, dass dies bereits getan worden wäre, wenn dies der Weg ist zu gehen. Meine Frage ist also: Wo ist die Set Typklasse oder welche alternative Lösung hat die Haskell-Community?

Meine Frage ist zugegebenermaßen sehr ähnlich zu Why is Haskell missing “obvious” Typeclasses, aber indem ich konkreter bin (auf ein konkretes Beispiel mit Beispielimplementierung konzentrierend), hoffe ich, noch konkretere Antworten zu bekommen.

Answer 1

können Sie Data.Containers from mono-traversable

Haskell Code versuchen, im Allgemeinen weniger von einem in Richtung verallgemeinern Datentypen wie diese gelehnt haben neigt als, sagen wir, Java, weshalb diese Abstraktionen nicht in containers oder unordered-containers sind.

Answer 2

Aus welchem ​​Grund auch immer, Haskell neigt nicht dazu, tiefe Hierarchien von Typklassen für die Darstellung aller möglichen Arten von Containern zu haben.

Im Allgemeinen haben verschiedene Arten von Containern Leistungseigenschaften für verschiedene Operationen. In der Regel wissen Sie, welche Vorgänge für Sie wichtig sind, und Sie wählen den am besten geeigneten Container aus und verwenden ihn explizit. Es ist nicht sehr wichtig, wirklich generischen Code schreiben zu können, der über jede mögliche Art von Container funktioniert.

Beachten Sie, dass es einige Typ Klassen für den Umgang mit Containern gibt bereits — sie sind nur nicht diejenigen, die Sie erwarten könnten. Zum Beispiel:

• Functor können Sie eine Funktion auf jedes Element eines Behälters — jeder Behälter — und sammeln Sie die Ergebnisse in einen neuen Behälter des gleichen Typs anzuwenden.

• Applicative und/oder Monad können Sie eine Funktion auf jedes Element anwenden und mehr als ein Element als Ergebnis erzeugen. (Es kann nicht offensichtlich sein, aber man kann diese „Filterung“ verwenden, auszuführen und sogar „Löschen“, obwohl es wahrscheinlich nicht effizient ist.)

• Monoid Ihre empty und union Methoden bietet (aber mempty und mappend genannt).

• Alternative, Foldable und Traversable können Sie weitere interessante Magie tun.

Answer 3

Ich werde die Klasse ein wenig mit Anmerkungen versehen:

-- The functional dependency here ties in to the issues with 
-- restricted type class instances, for which there is no one 
-- globally adopted solution. 
class Set set a | set -> a where 
    -- This is a `Monoid`- or `Alternative`-like constant 
    empty :: set 

    -- This is an `Applicative`-like operation 
    singleton :: a -> set 

    -- If you have `singleton` and `union` you have `insert`. 
    -- Which means that `insert` might fall out of the 
    -- `Alternative` class. 
    insert :: a -> set -> set 

    -- This looks like a variant of `filter` below. 
    delete :: a -> set -> set 

    -- These two are `Semigroup` operations 
    union :: set -> set -> set 
    intersection :: set -> set -> set 

    -- Can't think of anything for this one. 
    member :: a -> set -> Bool 

    -- This is very `Monad`-like operation. You can write this 
    -- in terms of a bind/`unionMap` operation + your `singleton` 
    -- and `empty`. 
    filter :: (a -> Bool) -> set -> set 

Also im Grunde zieht es die Gemeinschaft eine Menge von kleinen Klassen, die mehr wiederverwendbar sind, als diese Set Klasse sein würde.

Hier ist ein weiterer Punkt, der nützlich sein könnte. Sie scheinen geistig Klassen an Typen zu binden, als eine mentale Klassifizierung von Typen, die ähnlich sind, weil sie "Sätze darstellen". Aber die Haskell-Community bindet Klassen häufiger an Operationen. Sie können dies in der Anmerkung oben sehen, ich hoffe, die meisten der Operationen, die Sie vorschlagen, erinnern mich an eine bereits bestehende Klasse. Die schwarze Markierung ist die Tatsache, dass die meisten dieser Klassen nicht mit einem Typ wie Set funktionieren, der einen Elementtyp-Constraint ...