Erstellen von Ord Instanzen mit newtype

Question

Bei einem Datentyp wie

Einwickeln

data Foo = Bar | Baz | Qux 

und ich wünsche für diese Art mehr verschiedene Anordnungen haben, ist der folgende der häufigste/Standard-Weg, dies zu erreichen?

newtype FooPriorityA = FooPriorityA { unFooPriorityA :: Foo } 

instance Ord FooPriorityA where 
    compare (FooPriorityA x) (FooPriorityA y) = f x `compare` f y 
     where f :: Foo -> Int 
       f Baz = 1 
       f Bar = 2 
       f Qux = 3 

newtype FooPriorityB = FooPriorityB ... and so on 

Ist die Delegierung an Int's Ord-Instanz so verrückt? Es fühlt sich sicherer und viel weniger Arbeit an als das Schreiben der n^2-Vergleiche für compare.

Alle offensichtlichen Mängel, die ich mit diesem "Hack" vielleicht übersehen hätte? Ist es überhaupt ein "Hack"?

Answer 1

Sie brauchen nur O (n) (2 ​ n-1, um genau zu sein) Definitionen insgesamt Reihenfolge festlegen, solange man die Fälle, in ansteigender Reihenfolge ihrer Priorität angeben:

instance Ord FooPriorityA where 
    compare (FooPriorityA x) (FooPriorityA y) | x == y = EQ -- Use the Eq instance 
               -- Bar is the smallest 
               | x == Bar = LT 
               | y == Bar = GT 
               -- Baz is the next smallest 
               | x == Baz = LT 
               | y == Baz = GT 
               -- Proceed in the desired order. 
               -- You don't need to say anything 
               -- explicit about the largest value 

Der erste Fall (x == y) deckt O (n) Möglichkeiten ab. Jeder folgende Fall mag unvollständig aussehen, aber er enthält die implizierte Information, dass jeder vorhergehende Fall falsch ist. Zum Beispiel bedeutet x == Bar = LT nicht, dass jeder Fall, in dem x == Bar zu LT auswertet; der Fall, wo x == Bar && y == Bar bereits behandelt wird, so ist der zweite Fall wirklich implizit .

Ebenso Fall 4 (x == Baz) trägt, die Annahme, dass y /= Baz (implizierte durch den Ausfall von Fall 1 übereinstimmen) und y /= Bar (implizit durch den Ausfall von Fall 3 zu entsprechen). Daher ist jeder verbleibende mögliche Wert für y tatsächlich größer als Baz.

Je weiter unten auf der Liste Sie gehen, desto weniger unbearbeitete Fälle bleiben. Am Ende müssen Sie nichts über den größten Gegenstand sagen; alle Informationen darüber, wie es mit den anderen n - 1 Elemente vergleicht, wurde bereits von den vorhergehenden Fällen erfasst.

---

Auch bedenken Sie, dass Ihre Definition von f eine Hälfte (fromEnum) der minimalen Implementierung einer Instanz der Enum Klasse, die Sie dann Ihre Ord Instanz definieren, verwenden könnte.

instance Enum FooPriorityA where 
    fromEnum Bar = 1 
    fromEnum Baz = 2 
    fromEnum Qux = 3 
    toEnum 1 = Bar 
    toEnum 2 = Baz 
    toEnum 3 = Qux 

instance Ord FooPriorityA where 
    compare x y = compare (fromEnum x) (fromEnum y) 
    -- compare = compare `on` Data.Function.fromEnum 

Answer 2

Das ist absolut vernünftig. In der Tat können Sie the comparing function from Data.Ord verwenden, um diesen direkteren machen auch:

instance Ord FooPriorityA where 
    compare (FooPriorityA x) (FooPriorityA y) = comparing f x y 
    where f :: Foo -> Int 
      f Baz = 1 
      f Bar = 2 
      f Qux = 3 

Obwohl je nach Ihren Vorlieben, die Version mit compare könnte nach Ihren Wünschen mehr sein.

Answer 3

Wie wäre es mit einer Funktion machen die Zuordnung von Foo zu Int basierend auf einer Liste zu erzeugen, die die Reihenfolge darstellt, die Sie wünschen:

import Data.List 

data Foo = Bar | Baz | Qux deriving Eq 

newtype FooPriorityA = FooPriorityA { unFooPriorityA :: Foo } deriving Eq 

fooOrdering :: [Foo] -> Foo -> Foo -> Ordering 
fooOrdering orderedList a b = f a `compare` f b 
    where f x = elemIndex x orderedList 

instance Ord FooPriorityA where 
    compare (FooPriorityA x) (FooPriorityA y) = fooOrdering [Baz, Bar, Qux] x y 

Sie sogar eine Behauptung, um sicherzustellen, könnte hinzufügen, dass alle Elemente genau einmal auftreten In der Liste.