Herzlich Willkommen bei XALAX.DE

Übungsaufgaben zum Haskell-Kurs

In diesen Aufgaben sollen Sie viele Funktionen, die in der Prelude schon vorhanden sind, selbst definieren; sie erkennen sie an dem ' am Namensende. Dabei sollen Sie natürlich nicht einfach die entspechende vordefinierte Funktion verwenden, sondern eine eigene Definition mit Hilfe anderer (vordefinierter) Funktionen angeben.

Geben Sie vor jeder zu definierenden Funktion ihren Typ explizit durch eine Typsignaturdeklaration an.

Kapitel 1: Einleitung

  • Werten Sie die folgenden Ausdrücke mit Hugs aus. Überlegen Sie sich jeweils vorher, welches Resultat Sie erwarten.
    1. 12/3+2*19
    2. 7/3
    3. 7 `div` 3
    4. 7 `mod` 3
    5. True || False
    6. not False && False
  • Definieren Sie eine Funktion
    1. circleArea zur Berechnung der Fläche eines Kreises mit gegebenem Radius (Float).
    2. min' und eine Funktion max', die das Minimum bzw. Maximum zweier Integers bestimmen.
    3. abs' / signum', die den Absolutbetrag / das Vorzeichen einer Integer-Zahl berechnet.
    4. fib, die die n-te Fibonacci-Zahl berechnet.
    5. even' und eine Funktion odd' für Integer.
    6. eqMod, die testet, ob zwei Integer-Zahlen modulo n gleich sind.
    7. hoch, die x hoch n für Integer- Zahlen berechnet. Verwenden Sie
      1. rekursive Multiplikation mit x,
      2. rekursive Quadrierung (xn = (x(n/2))2 für gerade n).
    8. toUpper' und eine Funktion toLower', die Kleinbuchstaben in Großbuchstaben umwandelt bzw. umgekehrt. Jedes andere Zeichen soll unverändert bleiben.
    9. head', die das erste Zeichen eines Strings zurückgibt und eine Funktion last', die das letzte Zeichen eines Strings bestimmt.
    10. swapT, die zwei Boolss eines Tupels vertauscht.
    11. sortT, die zwei boolsche Werte eines Tupels ordnet.
    12. distance mit zwei Argumenten, die zu zwei Punkten in einem zweidimensionalen Koordinatensystem (Float) deren Abstand berechnet.
    Lösungen

    Kapitel 2: Funktionsdefinitionen

    Definieren Sie eine Funktion
    1. xor, die das logische exklusive Oder berechnet.
      1. mit Patternmatching
      2. ohne Patternmatching
    2. toUpperStr und eine Funktion toLowerStr, die in einer ganzen Zeichenkette Kleinbuchstaben in Großbuchstaben umwandelt bzw. umgekehrt.
    3. elem', die prüft, ob ein Zeichen Element eines Strings ist.
    4. product', die alle Integers einer Liste miteinander multipliziert.
    5. sumOfLists, die zu einer Liste von Listen, deren Einträge vom Typ Integer sind, die Summe der Listeneinträge berechnet.
    6. indexedEl, die zu einer Liste von Ints [a0, a1, a2, ...] und zu einer streng monoton wachsenden Folge von Ints [i0, i1, i2, ...], die Liste [ai0, ai1, ai2, ...] ausgibt.
    7. maxMinList, die in einem rekursiven Listendurchlauf das Maximum und das Minimum einer Liste von Ints bestimmt.
    8. Implementieren Sie Sortierfunktionen für Listen von Ints, die mit den folgenden Algorithmen arbeiten:
      • Insertion-Sort (Einfügen in sortierte Liste)
      • Bubble-Sort (Vertauschen benachbarter Elemente)
      • Merge-Sort (Verschmelzen schon sortierter Teillisten)
    Lösungen

    Kapitel 3: Parametrisierter Typpolymorphismus

    Überlegen Sie sich für jede zu definierende Funktion vorher, welchen Typ sie hat. Geben Sie diesen jedoch nicht durch eine Signaturdeklaration an, sondern fragen Sie Hugs mit : t nach dem Typ der definierten Funktion. Geben Sie danach eine Spezifikation an, die den Typ der Funktion echt einschränkt. Fragen Sie Hugs daraufhin nochmal nach dem Typ der Funktion.

    Definieren Sie eine Funktion

    1. rotateL2, rotateL3 usw., die die Elemente eines 2er-, 3er- usw. Tupels um eine Stelle nach links rotieren.
    2. oddListEl, die aus einer Liste die Teilliste der Einträge mit ungeradem Index herausfiltert (diese zurückgibt).
    3. swapListEl, die die benachbarten Einträge einer Liste vertauscht, d.h. den 1. mit dem 2., den 3. mit dem 4. usw.
    4. concat', die eine Liste von Listen durch Aneinanderhängen zu einer Liste verknüpft.
    5. transpose, die eine Liste von Listen (gleicher Länge) als Matrix auffaßt und diese Matrix transponiert (Vertauschung von Zeilen und Spalten).
    Lösungen

    Kapitel 4: Allgemeine Syntax

    1. Definieren Sie einen Operator *-*, der das Quadrat des zweiten Arguments vom Quadrat des ersten abzieht (Int-Zahlen). Testen Sie, welchen Unterschied es macht, diesen Operator als links-, rechts- oder nicht assoziativ zu definieren.
    Lösungen

    Kapitel 5: Mehr über Listen

    Definieren Sie eine Funktion
    1. permutations, die zu einer Liste die Liste aller Permutationen dieser Liste bestimmt.
    2. isPermutation mit zwei Argumenten, die testet, ob die eine Int-Liste eine Permutation der anderen Liste ist.
    3. powerList, die zu einer Liste die Liste aller Permutationen von Teillisten erzeugt, die durch Streichen einiger Listenlemente entstehen (entspricht der Potenzmenge, wenn die Liste eine Menge darstellt).
    4. queens mit allen Hilfsfunktionen. Geben Sie verschiedene Versionen mit unterschiedlichen Optimierungen an.
    Lösungen

    Kapitel 6: Funktionen höherer Ordnung

    Definieren Sie eine Funktion
    1. zipWith' :: (a -> b-> c) -> [a] -> [b] -> [c], die die Elemente zweier gleichlanger Listen durch eine Funktion paarweise verknüpft, und eine Funktion zip' :: [a] -> [b] -> [(a,b)], die zwei gleichlange Listen zu einer Liste von Paaren verknüpft.
    2. mapMat, die ein map auf Matrizen berechnet. Eine Matrix sei durch eine Liste von Listen dargestellt.
    3. factors, die die Liste aller Faktoren einer Integer-Zahl berechnet. Verwenden Sie hierbei filter
    4. unlines' :: [String] -> String, die alle Strings einer Liste mit einem Zeilenendzeichen (\nversieht und aneinanderhängt, ohne Verwendung expliziter Rekursion.
    5. reverse' unter Verwendung von foldl.
    6. length' unter Verwendung von foldl.
    7. unzip' :: [(a,b)] -> ([a],[b]), die Umkehrung von zip', unter Verwendung von foldr.
    Lösungen

    Kapitel 7: Verzögerte Auswertung - Nicht-Strikte Semantik

    1. Definieren Sie die Funktion ifThenElse :: Bool->a->a->a.
    2. Definieren Sie eine Funktion, die zu zwei totalen Funktionen des Typs Int->Int den Wert False liefert, falls diese sich an mindestens einer Stelle unterscheiden, und undefiniert ist, wenn die Funktionen gleich sind.
    3. Schreiben Sie eine Funktion, die zu einer Funktion f und einem Startwert i die Liste [i, f i, f (f i), f (f (f i)), ...] liefert.
    4. Die Knoten eines gerichteten Graphen seien Zahlen. Die Kanten des Graphen seien durch 2er-Tupel von Knoten, der Graph als Liste von Kanten dargestellt. Definieren Sie eine Funktion, die einen Weg (Liste von Knoten) von einem Knoten a zu einem Knoten b bestimmt, falls einer existiert. Verwenden Sie die Methode der List-Of-Successes. Der Graph kann auch zyklisch sein.
    5. Definieren Sie eine Funktion fak, die die Fakultät einer Zahl mit Hilfe einer Memo-Tabelle, d.h. einer unendlichen Liste der Fakultäten erzeugt.
    6. Definieren Sie auf die gleiche Weise eine Funktion fib zur Berechnung der n-ten Fibonaccizahl mit Hilfe einer Memo-Tabelle.
    Lösungen

    Kapitel 8: Benutzerdefinierte Typen

    1. Definieren Sie die Funktion mapTree mit Hilfe von foldTree.
    2. Definieren Sie verschiedene Versionen eines Datentyps Set a für Mengen mit einigen Mengenoperationen (z.B.: emptySet, isEmptySet, addToSet, union, intersection, ...)

    Kapitel 9: Klassen

    1. Definieren Sie eine Instanz der Klasse Ord für den Datentyp Tree a
    2. Definieren Sie für die von ihnen in Kapitel 8 definierten Datentypen Set a Instanzen der Klassen Eq und Ord.

    Kapitel 10: Module

    1. Machen Sie aus ihrem in Kapitel 8 und 9 definierten Datentyp Set a einen abstrakten Datentyp.

    Kapitel 11: Ein-/Ausgabe mit der I/O-Monade

    1. Schreiben Sie ein kleine Datenbank zur Verwaltung von Studierendendaten. Es sollte ein Hauptmenü mit auswählbaren Unterpunkten besitzen:
      • Studierende mit ihrer jeweiligen Matrikelnummer eingeben
      • alle gespeicherten Datensätze auflisten
      • Datensätze ändern
      • zu einer Matrikelnummer einen Studierenden suchen
      • alle Datensätze in einer Datei speichern
      • Datensätze aus einer Datei laden

    Kapitel 12: Kurz erwähnt

    1. Definieren Sie eine Instanz der Klasse Functor für ihren in vorherigen Aufgaben definierten Datentyp Set a.
    Letzte Änderung: 03.01.2008