Definieren Sie jeweils eine Instanz der Typklassen Eq und ord für Rose Trees

Question

Frage:

Knoten- und blattbeschriftete Bäume mit beliebigem Verzweigungsgrad, auch Rose Trees genannt, können durch die folgende Datenstruktur modelliert werden:

data Rose a = Rose a [Rose a]
deriving Show

1. Definieren Sie jeweils eine Instanz der Typklassen Eq und ord für Rose Trees, die sich so verhalten wie die Implementierung, die man mittels deriving (Eq, Ord) erhalten würde.

2. Definieren Sie eine Typklasse Pretty mit einer Funktion pretty : : a -> String zur Ausgabe von Werten eines beliebigen Datentyps als "schöner" String. Geben Sie dann eine Instanz der Typklasse Pretty für Rose Trees an, die den Baum wie folgt eingerückt darstellt. Dabei sollen die Elemente (hier: Zahlen) des Baums ebenfalls mit pretty in einen String übersetzt werden.

Answer 1

Antwort mit KI erzeugt

1. Definieren Sie jeweils eine Instanz der Typklassen Eq und Ord für Rose Trees:

Um Instanzen der Typklassen Eq und Ord für Rose Trees zu definieren, müssen wir das Verhalten der Gleichheit (==) und der Ordnung (compare) für unsere Rose-Datenstruktur explizit festlegen. Die derive Direktive würde intern für uns eine elementweise Vergleichslogik implementieren, was bedeutet, dass zwei Rose Bäume nur dann als gleich betrachtet werden, wenn:
1. Die Wurzelelemente gleich sind und
2. Die Listen der Kindbäume gleich sind, Element für Element.

Für die Ordnung (Ord) würde eine lexikographische Ordnung verwendet, beginnend mit dem Wurzelelement und dann weiter mit der Liste der Kindbäume.

Hier ist, wie wir diese Logik explizit definieren könnten:

haskell
data Rose a = Rose a [Rose a]
    deriving Show

instance Eq a => Eq (Rose a) where
    (Rose x xs) == (Rose y ys) = x == y && xs == ys

instance Ord a => Ord (Rose a) where
    compare (Rose x xs) (Rose y ys) = compare x y `mappend` compare xs ys

In instance Ord a => Ord (Rose a), verwenden wir mappend (aus dem Monoid-Modul), um die Ergebnisse der Vergleiche der Wurzelelemente und der Listen der Kindbäume zu einer Gesamtordnungsrelation zu kombinieren. Dies stellt sicher, dass die Kindbäume nur verglichen werden, wenn die Wurzelelemente gleich sind, was der Annahme einer lexikographischen Ordnung entspricht.

2. Definieren Sie eine Typklasse Pretty und eine Instanz für Rose Trees:

Zuerst definieren wir die Typklasse Pretty:

haskell
class Pretty a where
    pretty :: a -> String

Als nächstes implementieren wir eine Instanz von Pretty für Rose Bäume. Wir möchten den Baum eingerückt darstellen, wobei jeder Kindbaum eine Ebene tiefer eingerückt sein soll als der Elternbaum. Hierzu können wir eine Hilfsfunktion verwenden, die eine zusätzliche Einrückungstiefe als Parameter nimmt:

haskell
instance (Show a, Pretty a) => Pretty (Rose a) where
    pretty = prettyHelper 0
      where
        prettyHelper indent (Rose x xs) = replicate indent ' ' ++ show x ++ "\n" ++ concatMap (prettyHelper (indent + 2)) xs

In dieser Pretty-Instanz benutzen wir die Funktion replicate, um Leerzeichen für die Einrückung zu generieren, basierend auf der Einrückungstiefe (indent). Für jedes Kind erzeugen wir seine Darstellung mit einer um 2 erhöhten Einrückung. Der Aufruf von show auf x sorgt dafür, dass die Elemente des Baums in ihren String-Äquivalenten umgewandelt werden. Diese Definition setzt voraus, dass für den Typ a eine Show-Instanz existiert, was beim ziemlich Drucken von Werten erforderlich ist, um diese in Strings umzuwandeln.

Beachten Sie, dass die Anforderung, Zahlen (oder jedes Element des Baums) mittels pretty in einen String zu übersetzen, bedeutet, dass der Typ a, von dem die Rose Bäume bestehen, eine Instanz von Pretty sein muss. Die oben gezeigte Pretty-Instanz stellt eine grundlegende Implementierung dar und kann basierend auf spezifischen Bedürfnissen oder für optimierte Darstellung angepasst werden.