Eigene Menge

Anleitung

Erstelle einen eigenen Set-Typ.

Manchmal ist es notwendig, eine eigene Datenstruktur eines bestimmten Typs zu definieren, zum Beispiel ein Set. In dieser Übung definierst du dein eigenes Set. Wie es intern funktioniert, ist egal, solange es sich wie ein Set aus eindeutigen Elementen verhält.

Hinweise

Um diese Übung zu lösen, musst du den Datentyp CustomSet mit Eq- und Show-Instanzen erstellen und die folgenden Funktionen implementieren:

• delete
• difference
• empty
• fromList
• insert
• intersection
• isDisjointFrom
• isSubsetOf
• member
• null
• size
• toList
• union

Eine Dummy-Datendeklaration und die Typsignaturen findest du bereits vor. Die Funktionen zu definieren und einen sinnvollen Datentyp, ein newtype oder ein Typsynonym zu erstellen, bleibt aber dir überlassen.

Wenn du eine effiziente Implementierung schreiben möchtest, aber nicht so recht weißt, wo du anfangen sollst: Der beste Einstieg, den ich kenne, ist Chris Okasakis „Purely Functional Data Structures“. Eine Version davon kannst du hier lesen: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf