M. Sperber Sommersemester 1997

Funktionale Programmierung

Blatt 4

Abgabe: 16.5.1997

1. [10 Punkte] Schreiben Sie ein kleines Telefonbuchprogramm in Haskell, das Paare aus Namen und Telefonnummern in einer (festen) Datei ablegt. Es sollte möglich sein, von der Kommandozeile aus neue Einträge hinzuzufügen und für einen Namen die zugehörige Telefonnummer zu erfragen.
2. [10 Punkte] Hugs bietet als Erweiterung zum Haskell-Standard sogenannte ,,State Threads`` an, eine Zustandstransformations-Monade ST, welche die entsprechende Monade aus der Vorlesung verallgemeinert. Innerhalb von ST können sowohl ,,normale`` Variablen als auch Arrays mit veränderbaren Elementen erzeugt und verändert werden. ST s a ist dabei ein Zustandstransformator mit Zustandstyp s und Resultat-Typ a, MutVar s a ist der Typ einer mutierbaren Variable innerhalb eines Zustands vom Typ s, und MutArr s a b ist der Typ eines modifizierbaren Arrays innerhalb eines Zustands vom Typ s mit Indextyp a und Elementtyp b. Folgende Operationen sind definiert:

   returnST :: a -> ST s a
   thenST :: ST s a -> (a -> ST s b) -> ST s b
   
   newVar :: a -> ST s (MutVar s a)
   readVar :: MutVar s a -> ST s a
   writeVar :: MutVar s a -> a -> ST s ()
   
   newArr :: (Int,Int) -> b -> ST s (MutArr s Int b)
   readArr :: MutArr s Int b -> Int -> ST s b
   writeArr :: MutArr s Int b -> Int -> b -> ST s ()
   freezeArr :: MutArr s Int b -> ST s (Array Int b)
   

   Außerdem gibt es noch eine Operation runST, die auf ein Objekt vom Typ ST s a angewendet das Resultat der Berechnung vom Typ a liefert. (Der Typ von runST läßt sich nicht als normaler Haskell-Typ schreiben.)

   Nach :load ST bzw. :load STArray (und danach :also <file>) stehen diese Operationen zur Verfügung. freezeArr ist dazu da, um ein veränderbares Array in ein normales Haskell-Array zu verwandeln. (Siehe Haskell-Report.)

   Programmieren Sie in Haskell einen Zustandstransformator, der einen Bubble''=Sort auf Arrays durchführt, also etwa folgenden Typ hat:

   bubbleSortST :: (Ord a) => MutArr s Int a -> (Int, Int) -> ST s ()

3. [10 Punkte] Geben Sie eine Implementierung einer Ausnahme-Monade mit analoger Funktionalität zum Ausnahmemechanismus der I/O-Monade an.

• Über dieses Dokument ...