CSCI 301 Lab 6: Relationen in Racket – Reflexive, Symmetrische & Transitive Hülle

Eigenschaften von Relationen in Racket: Einführung

In der diskreten Mathematik und funktionalen Programmierung spielen Relationen eine zentrale Rolle. Für das CSCI 301 Lab 6 musst du in Racket die reflexive, symmetrische und transitive Hülle einer Relation implementieren – und zwar rein rekursiv ohne set! oder Iteration. Dieser Leitfaden erklärt dir die Konzepte anhand aktueller Beispiele und zeigt dir, wie du die Funktionen Reflexive-Closure, Symmetric-Closure und Transitive-Closure Schritt für Schritt aufbaust.

Stell dir vor, du entwickelst eine Social-Media-App wie TikTok oder Instagram: Die Beziehung „folgt“ ist eine Relation. Wenn du möchtest, dass jeder sich selbst folgt (reflexiv), dass Folgen gegenseitig ist (symmetrisch) oder dass indirekte Verbindungen auch als Folge gelten (transitiv), dann arbeitest du mit Hüllen. Genau das programmierst du in Lab 6.

Grundlagen: Relationen als Listen von Paaren

In Racket wird eine Relation als Liste von Paaren dargestellt, z.B. '((a b) (b c)). Jedes Paar (x y) bedeutet, dass x in Relation zu y steht. Die Grundmenge S ist eine Liste von Elementen, z.B. '(a b c). Deine Aufgabe ist es, die Hüllen zu berechnen, ohne vorhandene Paare zu entfernen.

Reflexive Hülle (Reflexive-Closure)

Die reflexive Hülle fügt für jedes Element der Grundmenge S ein Paar (x x) hinzu, falls es noch nicht vorhanden ist. Beispiel: (Reflexive-Closure '((a a) (b b)) '(a b c)) ergibt '((a a) (b b) (c c)).

Implementierungsidee: Rekursiv über die Liste S gehen. Für jedes Element prüfen, ob ein Paar (x x) bereits in L ist. Wenn nicht, wird es angehängt. Die Rekursion arbeitet ohne Seiteneffekte – du baust eine neue Liste auf.

(define (Reflexive-Closure L S)
  (cond [(null? S) L]
        [else (let ([x (car S)])
                (if (member (list x x) L)
                    (Reflexive-Closure L (cdr S))
                    (Reflexive-Closure (append L (list (list x x))) (cdr S))))]))

Beachte: member vergleicht mit equal?, was für Listen funktioniert. Die Funktion ist tail-rekursiv, aber das ist nicht zwingend erforderlich.

Symmetrische Hülle (Symmetric-Closure)

Die symmetrische Hülle fügt für jedes Paar (a b) das inverse Paar (b a) hinzu, falls es fehlt. Beispiel: (Symmetric-Closure '((a b) (a c))) ergibt '((a b) (a c) (b a) (c a)).

Implementierungsidee: Rekursion über die Liste L. Für jedes Paar (a b) prüfen, ob (b a) bereits in der aktuellen Liste (oder im bisherigen Ergebnis) ist. Wenn nicht, füge es hinzu. Da wir keine Seiteneffekte verwenden, müssen wir die Liste nach und nach aufbauen.

(define (Symmetric-Closure L)
  (define (helper L result)
    (cond [(null? L) result]
          [else (let ([pair (car L)]
                      [a (caar L)]
                      [b (cadar L)])
                  (if (member (list b a) result)
                      (helper (cdr L) result)
                      (helper (cdr L) (append result (list (list b a))))))]))
  (helper L L))

Hier starten wir mit result = L und fügen nur fehlende inverse Paare hinzu. Achtung: Die Reihenfolge der Paare im Ergebnis kann von den Beispielen abweichen, aber solange alle Paare enthalten sind, ist es korrekt.

Transitive Hülle (Transitive-Closure)

Die transitive Hülle ist komplexer: Sie fügt alle indirekten Verbindungen hinzu. Wenn es (a b) und (b c) gibt, muss (a c) hinzugefügt werden, bis keine neuen Paare mehr entstehen. Das ist ein Fixpunktproblem.

Implementierungsidee: Wiederhole den Vorgang: Für jedes Paar (x y) und jedes Paar (y z) füge (x z) hinzu, falls nicht vorhanden. Wiederhole dies, bis sich nichts mehr ändert. Rekursion ohne Schleifen: entweder mit einer Hilfsfunktion, die den gesamten Schritt berechnet, und dann prüft, ob sich etwas geändert hat.

(define (Transitive-Closure L)
  (define (step L)
    (foldl (lambda (pair result)
             (foldl (lambda (other result)
                      (if (and (equal? (cadr pair) (car other))
                               (not (member (list (car pair) (cadr other)) result)))
                          (cons (list (car pair) (cadr other)) result)
                          result))
                    result
                    L))
           L
           L))
  (let ([newL (step L)])
    (if (equal? L newL)
        L
        (Transitive-Closure newL))))

Die step-Funktion erzeugt eine neue Liste, indem sie für jedes Paar (x y) und jedes Paar (y z) ein (x z) hinzufügt. Da foldl die Liste von links durchläuft, kann die Reihenfolge anders sein. Wichtig ist, dass die Funktion terminiert, da die Anzahl der möglichen Paare durch |S|^2 begrenzt ist.

Trend-Beispiel: Transitive Hülle in Gaming-Netzwerken

Stell dir vor, du entwickelst ein Matchmaking-System für ein Spiel wie Fortnite oder League of Legends. Spieler A hat gegen B gewonnen, B gegen C – dann sollte A indirekt als besser als C gelten. Die transitive Hülle modelliert genau diese indirekten Beziehungen. Mit deiner Transitive-Closure-Funktion kannst du aus einer Liste direkter Siege alle indirekten Siege ableiten. Das ist nützlich für Ranglisten oder Turnierbäume.

Häufige Fehler und Tipps

Reihenfolge der Paare: In den Beispielen wird eine bestimmte Reihenfolge erwartet. Achte darauf, dass deine Funktion die Paare in der gleichen Reihenfolge wie in den Beispielen ausgibt. Verwende append oder cons mit Bedacht.
Keine doppelten Paare: Deine Hüllen sollten keine Duplikate enthalten. Prüfe vor dem Hinzufügen, ob das Paar bereits existiert.
Rekursion ohne set!: Du musst neue Listen aufbauen, nicht bestehende verändern. Das ist funktionale Programmierung.
Teste mit leeren Listen: Alle Funktionen sollten mit '() umgehen können.

Zusammenfassung

Mit diesem Leitfaden hast du die Grundlagen, um Reflexive-Closure, Symmetric-Closure und Transitive-Closure in Racket zu implementieren. Denk daran: Rekursion ist dein Werkzeug, und Seiteneffekte sind tabu. Übe mit den Beispielen aus der Aufgabenstellung und erweitere sie. Viel Erfolg bei CSCI 301 Lab 6!

Stand: Juni 2026 – Dieser Artikel wurde für das Sommersemester 2026 aktualisiert.