Warum ist Bounded nicht eine Unterklasse von Enum in Haskell?

Es scheint, dass jede Bounded-Instanz eine vernünftige Implementierung von Enum haben sollte. Ich kann mir kein Gegenbeispiel vorstellen, obwohl ich verstehen werde, warum dies nicht der Fall ist, wenn jemand eines findet, das nicht pathologisch ist.

Ausgehend :ivon den beiden Typklassen scheint die einzige Ausnahme, die derzeit in der Standardbibliothek enthalten ist, Tupel zu sein, die begrenzt, aber keine Aufzählungen sind. Jedes Bounded-Tupel muss jedoch auch auf vernünftige Weise aufzählbar sein, indem einfach das letzte Element inkrementiert und dann umbrochen wird, wenn es zu maxBound gelangt.

Diese Änderung würde wahrscheinlich auch das Hinzufügen predBund / nextBoder ähnliches zu Bounded beinhalten, um einen sicheren / schleifenförmigen Weg zum Durchlaufen der Enum-Werte zu finden. In diesem Fall toEnum 0 :: (...)wäre gleich(toEnum 0, toEnum 0, ...) :: (...)

haskell typeclass Semikolon
quelle

Ich kann dies nicht wirklich verbindlich beantworten, aber ich betrachte den Bereich aller reellen Zahlen zwischen 0 und 1. Es hat klare Unter- und Obergrenzen, aber es hat unzählige unendliche Mitglieder.

Doval

@Doval das ist ein fairer Punkt. Das Gleiche gilt jedoch für alle reellen Zahlen im Allgemeinen (unzählige unendliche Mitglieder), aber Double/ Floatund alle ähnlichen Typen implementieren sie Enumtrotzdem, sie machen nur succ = (+ 1)und fromEnum = truncate. Haskells Weg ist aus praktischer Sicht tatsächlich sinnvoll, da sonst [0, 0,5 ..] und ähnliches nicht funktionieren würden. Haskell scheint sich also keine Sorgen um die Zählbarkeit zu machen, wenn es um Enums geht.

Semikolon

Ich war nicht bewusst , dass succist (+1). Das ist seltsam, weil Doubleund Floathaben nicht unendliche Präzision und sind daher aufzählbar - succhätte als +1 ULP definiert werden können .

Doval

@Doval Ich denke, der Grund dafür war, dass das Haskell-Kernteam wollte, dass [1 ..] mit Doubles dasselbe bedeutet wie mit Ints.

Semikolon

@semicolon Doubles und Floats sind keine reellen Zahlen (z. B. kann PI nicht in einem Double gespeichert werden, ohne an Genauigkeit zu verlieren), daher sind sie aufzählbar

jk.

Antworten:

Ein praktisches Beispiel, das mir gefällt, stammt aus der Welt der Programmiersprachen: Die Menge der Typen in einem OO-System ist begrenzt und diskret, aber nicht aufzählbar und teilweise geordnet, aber nicht vollständig geordnet.

Die fragliche Teilreihenfolge ist die Subtypisierungsbeziehung <:. Die Obergrenze wäre dann der obere Typ (den C # objectund Scala aufruft Any), und die Untergrenze wäre der untere Typ (Scala Nothing; C # / Java haben kein nennenswertes Äquivalent).

Es gibt jedoch keine Möglichkeit, alle Typen im Typsystem aufzulisten, sodass Sie keine schreiben können instance Enum Type. Dies sollte klar sein: Benutzer können ihre eigenen Typen schreiben, sodass sie nicht im Voraus wissen können, was sie sein werden. Sie können alle Typen in einem bestimmten Programm auflisten, jedoch nicht im gesamten System.

Ebenso ist (gemäß einer bestimmten vernünftigen Definition der Subtypisierung) <:reflexiv, transitiv und antisymmetrisch, aber nicht vollständig . Es gibt Typenpaare, die nicht mit verwandt sind <:. ( Catund Dogsind beide Subtypen von Animal, aber keiner ist ein Subtyp des anderen.)

Angenommen, wir schreiben einen Compiler für eine einfache OO-Sprache. Hier ist die Darstellung der Typen in unserem System:

data Type = Bottom | Class { name :: String, parent :: Type } | Top

Und die Definition der Subtypisierungsrelation:

(<:) :: Type -> Type -> Bool
Bottom <: _ = True
Class _ _ <: Bottom = False
Class n t <: s@(Class m _)
    | n == m = True  -- you can't have different classes with the same name in this hypothetical language
    | otherwise = t <: s  -- try to find s in the parents of this class
Class _ _ <: Top = True
Top <: Top = True
Top <: _ = False

Dies gibt uns auch eine Supertypisierungsbeziehung.

(>:) :: Type -> Type -> Bool
t >: s = s <: t

Sie können auch die kleinste Obergrenze von zwei Typen finden:

lub :: Type -> Type -> Type
lub Bottom s = s
lub t Bottom = t
lub t@(Class _ p) s@(Class _ q) =
    | t >: s = t
    | t <: s = s
    | p >: s = p
    | t <: q = q
    | otherwise = lub p q
lub Top _ = Top
lub _ Top = Top

Übung: Zeigen Sie, dass Typeein begrenzter vollständiger Poset auf zwei Arten gebildet wird, unter <:und unter >:.

Benjamin Hodgson
quelle

Super danke! Das beantwortet meine Frage vollständig und auch meine Folgefrage zu Ord. Hätte Gl. Ähnliche Probleme? Wo ein nicht gleichwertiger Typ möglicherweise einen maxBound oder einen minBound hat. In diesem Fall sollte Cat == Dog einfach false zurückgeben, da es sich um verschiedene Klassen handelt, oder wäre es aufgrund der Baumposition, die weder über noch unter der anderen liegt, unentscheidbar?

Semikolon

Eine Bestellung impliziert eine Gleichheit - definieren Sie einfach x == y = x <= y && y <= x. Wenn ich eine PosetKlasse entwerfen würde, hätte ich class Eq a => Poset a. Ein schnelles Google bestätigt, dass andere Leute die gleiche Idee hatten .

Benjamin Hodgson

Entschuldigung, meine Frage war nicht eindeutig. Was ich meinte war, ob Bounded Gl. Implizierte, auch wenn es Ord nicht impliziert.

Semikolon

@semicolon Wieder gibt es keine Beziehung zwischen den beiden Klassen. Überlegen Sie, data Bound a = Min | Val a | Maxwelche Augments ein Typ amit +∞und -∞Elementen enthält. Durch Konstruktion Bound akann immer eine Instanz von gemacht werden, Boundedaber es wäre nur gleichwertig, wenn der zugrunde liegende Typ aist

Benjamin Hodgson

in Ordnung fair genug. Ich denke, ein Beispiel könnten Funktionen sein, die Werte vom Typ annehmen und zurückgeben Double, wobei const (1/0)is maxBoundund const (negate 1/0)is minBoundbut \x -> 1 - xund \x -> x - 1unvergleichbar sind.

Semikolon

Dies liegt daran, dass die Vorgänge unabhängig sind. Wenn Sie sie also mit einer Unterklassenbeziehung verknüpfen, erhalten Sie eigentlich nichts. Angenommen, Sie wollten einen benutzerdefinierten Typ erstellen, der implementiert wurde Bounded, möglicherweise Doubleszwischen max und min, aber Sie mussten keine der EnumOperationen ausführen. Wenn Boundedes sich um eine Unterklasse handeln würde, müssten Sie ohnehin alle EnumFunktionen implementieren , um sie zum Kompilieren zu bringen.

Es spielt keine Rolle, ob es eine vernünftige Implementierung für Enumoder eine andere Anzahl von Typklassen gibt. Wenn Sie es nicht wirklich benötigen, sollten Sie nicht gezwungen sein, es zu implementieren.

Vergleichen Sie dies mit sagen, Ordund Eq. Dort sind die OrdOperationen von denen abhängig Eq, daher ist es sinnvoll, die Unterklasse zu fordern, um Doppelarbeit zu vermeiden und Konsistenz zu gewährleisten.

Karl Bielefeldt
quelle

In diesen Fällen ist es Teil der Definition. Alle Monaden sind per Definition auch Antragsteller und Funktoren, sodass Sie den "Vertrag" der Monaden nicht erfüllen können, ohne die anderen zu erfüllen. Ich bin mit der Mathematik nicht vertraut genug, um zu wissen, ob dies eine grundlegende Beziehung oder eine auferlegte Definition ist, aber so oder so bleiben wir jetzt dabei.

Karl Bielefeldt

@semicolon In der Dokumentation zuBounded "Ord ist keine Superklasse von Bounded, da Typen, die nicht vollständig geordnet sind, auch Ober- und Untergrenzen haben können."

Benjamin Hodgson

@BenjaminHodgson Ich habe nicht einmal an teilweise geordnete Typen gedacht. +1 für ein nicht pathologisches Beispiel und zum Zitieren der Dokumentation.

Doval

@semicolon Ein Beispiel für eine Teilbestellung aus der Computerwelt könnte die Untertypisierung in OO-Sprachen sein. Schreiben <:für ist ein Subtyp von , ∀ T S. T <: S ∨ S <: Tgilt nicht (zB int !<: bool ∧ bool !<: int). Sie würden wahrscheinlich darauf stoßen, wenn Sie einen Compiler schreiben würden.

Benjamin Hodgson

@BenjaminHodgson ah ok. Wenn zum Beispiel A eine Oberklasse von B und C ist und D eine Unterklasse von B und C ist, dann sind B und C unvergleichlich, aber A und D sind max / min?

Semikolon