M. Sperber Sommersemester 1996

Funktionale Programmierung

Blatt 3

Abgabe: 13.5.1997 (nächstes Blatt fällig 16.5.)

1. [10 Punkte] Implementieren Sie einen Datentyp Queue a für Queues mit den üblichen Operationen naiv. Welche Laufzeit-Nachteile hat die funktionale Version gegenüber einer Implementation in einer imperativen Sprache? Implementieren Sie eine Version von Queue a, mit gleicher mittlerer Laufzeitkomplexität wie die Operationen einer imperative Fassung.
2. [5 Punkte] Definieren Sie einen algebraischen Datentyp HetList mit den Datenkonstruktoren Nil und Cons, so daß folgendes Programmstück keine Typfehler verursacht:

   het_length Nil        = 0
   het_length (Cons _ x) = 1 + het_length x
   
   hrgwrglmrgl = Cons 1 (Cons True (Cons 'X' Nil))
   

3. [5 Punkte (bitte ignorieren!)] Der Typ von foldr (+) 0 ist [Int] -> Int. Wie muß der Ausdruck geändert werden, damit er den Typ Num a => [a] -> a hat?
4. [10 Punkte] Definieren Sie einen Datentyp Rational' entsprechend Aufgabe 4 von Blatt 1 als Instanz der Typklassen Eq, Ord, Text und Num.

• Über dieses Dokument ...