M. Sperber, H. Klaeren Wintersemester 1998/99

Compilerbau I

Blatt 1

Abgabe: 27.10.1998

1. [5 Punkte] Schreiben Sie eine Funktion partition_list : ('a -> bool) -> 'a list -> ('a list * 'a list), so daß partition_list f, l ein Paar ( , ) liefert, in dem genau die Elemente x von l enthält mit f x = true und die Elemente x mit f x = false.
2. [5 Punkte] Definieren Sie den Datentyp Rational für rationale Zahlen mit den arithmetischen Operationen Addition, Subtraktion, Multiplikation und Division. Benutzen Sie eine eindeutige Darstellung.
3. [10 Punkte] Geben Sie eine Funktion length' : 'a list -> int an, welche die Länge einer Liste berechnet. length' soll selbst nicht rekursiv sein, darf aber die fold_...-Funktionen aus dem Modul List der Standardbibliothek benutzen.
4. [10 Punkte] Schreiben Sie eine Caml-Funktion

   lcs : string -> string -> string

   so daß die längste gemeinsame Teilfolge zweier Zeichenketten x und y liefert. (So ist tie die längste gemeinsame Teilfolge von striped und tiger.)

   Schreiben Sie außerdem eine Funktion

   diff : string -> string -> int

   so daß die Distanz zweier Zeichenketten berechnet, also die minimale Anzahl von Einfügungen und Löschungen, die erforderlich sind, um x in y zu überführen.

• Über dieses Dokument ...