Prof. Dr. Manfred Schmidt-Schauß Fachbereich Informatik (20) Künstliche Intelligenz/Softwaretechnologie Johann Wolfgang Goethe-Universität Frankfurt am Main

Einführung in das funktionale Programmieren:

Sommersemester 1997

Übungsblatt Nr. 2

Aufgabe 1

Programmieren Sie in KFP eine Funktion maxseg, so daß maxseg n x diejenige Teilliste der Länge n berechnet, deren Summe maximal ist. Nehmen Sie an, die Addition sei für die Elemente der Liste definiert.

Aufgabe 2

Übersetzen Sie folgende Definitionen aus Haskell nach KFP:

1. twice f x = f (f x)

2. []++ ys = ys (x: xs) ++ ys = x: (xs ++ ys)

  3. concat [] = []
     concat (x: xs) = x ++ (concat xs)
  4. concat = foldr (++) []
     foldr f n [] = n

foldr f n (x: xs) = f x (foldr f x xs)

Aufgabe 3

Nehmen Sie an ein Datentyp BTree für binäre Bäume, die auch leer sein können, sei definiert. Definieren Sie in KFP eine Funktion inorder, die die Liste der Daten in den Knoten beim Inorder-Durchlaufen des Baumes berechnet.

Aufgabe 4

1. Für welche Terme xs ist twice head xs dynamisch wohlgetypt?

2. Geben Sie für die KFP-Definitionen aus Aufgabe 2 Beispiele für Ausdrücke, die nicht dynamisch wohlgetypt sind. Zeigen Sie, daß Ihre Beispiele tatsächlich nicht dynamisch wohlgetypt sind.