TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2023-03-03 (Lösungsvorschlag)

Lösungsvorschlag von Dublbro

Aufgabe 1 (2*0.5+8+4+2+2 = 17 Punkte)

Vorgegebener Code:

data Liste a = Ende | E a (Liste a)

revertiere :: (Liste a) -> (Liste a)

1. Ergebnisse der Aufrufe von (a) und (b):
   • (a): E 2 (E 5 (E 2 (E 3 (E 7))))
   • (b): E "Viel" (E "Er" (E "folg!" Ende))
2. Implementierung der Funktion:

   revertiere Ende = Ende
   revertiere (E x l) = haenge_an x (revertiere l)
   
   haenge_an :: a -> (Liste a) -> (Liste a)
   haenge_an x Ende = E x Ende
   haenge_an x (E y l) = E y (haenge_an x l)
   

3. Erklärung:
   Die Funktion revertiere revertiert eine Liste mit n Elementen, indem sie die hinteren n-1 Elemente revertiert und das erste Element hinten an diese anhängt.
4. Ad-hoc Polymorphie: Eine Funktion ist ad-hoc polymorph wenn die Typen eines oder meherer ihrer Parameter durch Typkontexte eingeschänkt sind.
5. Mikroskopische Ebene - Lineare Rekursion: revertiere ruft sich pro Zweig höchstens ein Mal auf und davon ist ein Aufruf nicht die äußerste Operation.

Aufgabe 2 (2*0.5+2+(6+8)+(3+4)+5*2 = 34 Punkte)

Vorgegebener Code:

data Liste a = Ende | E a (Liste a) deriving Show

f :: Ord a => (Liste a) -> (Liste a)
f = h . g

data Baum a     = Blatt
                | Knoten a (Baum a) (Baum a) deriving Show
type Suchbaum a = Baum a

g :: Ord a => (Liste a) -> (Suchbaum a)
h :: Ord a => (Baum a) -> (Liste a)

1. Ergebnisse der Aufrufe in (a) und (b):

Die Angabe lautete:

- g überführt eine Liste in einen Suchbaum: ist k Knoten eines Suchbaums mit Markierung m, so sind alle Markierungen im linken Teilbaum von k echt größer als m und alle Markierungen imrechten Teilbaum von k ehct kleiner als m; ein Suchbaum ist deshalb frei von Duplikaten: keine Markierung kommt mehrfach vor

1. • (a): Knoten 6 Blatt (Knoten 2 (Knoten 3 (Knoten 5 Blatt Blatt) Blatt) Blatt)(Hängt evt. von der eigenen Implementierung ab)

      Andere Meinung: es gibt zwei mögliche Reihenfolge
      - man arbeitet die Liste von außen nach innen ab: Knoten 5 (Knoten 6 Blatt Blatt) (Knoten 3 Blatt (Knoten 2 Blatt Blatt) Blatt)
      - man arbeitet die Liste von innen nach außen ab: Knoten 6 Blatt (Knoten 2 (Knoten 5 Blatt (Knoten 3 Blatt Blatt)) Blatt)

1. • (b): E 4 (E 6 (E 11 (E 15 Ende)))
2. Warum können g und h komponiert werden, obwohl der Bildtyp von g und der Argumenttyp von h namensverschieden sind?
   Suchbaum a ist ein Typsynonym, d.h. es ist kein neuer Typ, sondern nur ein anderer Name für Baum a und kann daher gleich verwendet werden.
3. Implementieren (a) von g und (b) von h:
   • (a):

     g Ende = Blatt
     g (E x l) = fuege_ein x (g l)
     
     fuege_ein :: Ord a => a -> (Suchbaum a) -> (Suchbaum a)
     fuege_ein x Blatt = Knoten x Blatt Blatt
     fuege_ein x (Knoten e bl br)
       | x < e     = Knoten e bl (fuege_ein x br)
       | x > e     = Knoten e (fuege_ein x bl) br
       | otherwise = Knoten e bl br
     

   • (b):

     h Blatt = Ende
     h (Knoten e l r) = verbinde (h r) (verbinde (E e Ende) (h l))
     
     verbinde :: (Liste a) -> (Liste a) -> (Liste a)
     verbinde Ende l = l
     verbinde l Ende = l
     verbinde (E x lr) l2 = E x (verbinde lr l2)
     

4. Erklärung:
   g erstellt aus dem letzten Listenelement einen Suchbaum, in den alle vorhergehenden Elemente eingefügt werden.
   h erstellt rekursiv Listen aus dem rechten Teilbaum, dem Knotenelement und dem linken Teilbaum, die dann konkateniert werden.
5. Genügt ... dem Hauptleitsatz funktionaler Programmierung? (Typen sollen nur so weit eingeschränkt sein, dass eine fehlerfreie Ausführung gewährleistet ist)
   • (a) Baum a
     Ja, der Typ a hat hier keinerlei Einschränkungen.
   • (b) Suchbaum a
     Ja, Suchbaum a ist gleichwertig zu Baum a und daher gilt dasselbe wie bei (a).
   • (c) g
     Ja, a ist nur auf Typen der Typklasse Ord beschränkt, was für die Erstellung des Suchbaums notwendig ist.
   • (d) h
     Nein, a ist auf Typen der Typklasse Ord beschränkt, obwohl das für die Funktion nicht notwendig ist.
   • (e) f
     Ja, da a in g auf Typen der Typklasse Ord beschränkt ist, muss das auch in f gelten.

(Pfusch)Lösung von Padraig zu den Implementierungen

f :: Ord a => (Liste a) -> (Liste a)
f = h . g

data Baum a = Blatt | Knoten a (Baum a) (Baum a) deriving Show
type Suchbaum a = Baum a

g :: Ord a => (Liste a) -> (Suchbaum a)
g l = g' l Blatt -- Baum baum = new Baum()

g' :: Ord a => (Liste a) -> (Suchbaum a) -> (Suchbaum a)
g' Ende b = b
g' (E a l) b = g' l (addNode a b)

addNode :: Ord a => a -> (Suchbaum a) -> (Suchbaum a)
addNode a Blatt = (Knoten a) Blatt Blatt
addNode a (Knoten b l r)
  | a > b = Knoten b (addNode a l) r
  | a < b = Knoten b l (addNode a r)
  | otherwise = Knoten b l r



h :: Ord a => (Baum a) -> (Liste a)
h b = convertListe (convertList b)

convertList :: (Baum a) -> [a]
convertList (Blatt) = []
convertList (Knoten a l r) = (convertList r) ++ [a] ++ (convertList l)

convertListe :: [a] -> (Liste a)
convertListe [] = Ende
convertListe (x:xs) = (E x (convertListe xs))

Aufgabe 3 (4 + 4 + 4 = 12 Punkte)

1. Richtig. Die Entfernung von newtype-Deklarationen würde die Ausdruckskraft und Mächtigkeit von Haskell nicht ändern. Das liegt daran, dass newtype in erster Linie ein Mittel zur Verbesserung der Typsicherheit und zur Leistungsverbesserung ist, aber nicht zur Erweiterung der grundsätzlichen Ausdruckskraft der Sprache. Alles, was man mit newtype machen kann, ist auch mit data möglich (kann aber zu Overhead führen).
2. Falsch, sie führen zwar zum selben Ergebnis, jedoch spielt die Ausführungsreihenfolge gerade bei Haskell eine große Rolle, weil so der Umgang mit unendlichen Strukturen ermöglicht wird.
3. Falsch, seine wichtigste wissenschaftliche Leistung war das Lambda-Kalkül.

Aufgabe 4 (5 + 8 + 2 = 15 Punkte)

1. Wenn e1, e2 ineinander konvertierbar sind, d.h. e1 ←→ e2, dann gibt es einen gemeinsamen λ-Ausdruck e, zu dem e1, e2 reduziert werden k ̈onnen, d.h. e1 →∗ e und e2 →∗ e. Informell: Wenn eine Normalform existiert, dann ist sie (bis auf α-Konversion) eindeutig bestimmt!
2. Wenn ein Ausdruck auf verschiedene Arten reduziert werden kann, führen alle Reduktionswege zu einem gemeinsamen Ergebnis. Die Konfluenzeigenschaft gewährleistet also die Eindeutigkeit der Auswertung von Lambda-Kalkül-Ausdrücken. Es stellt sicher, dass verschiedene Berechnungspfade zu konsistenten Ergebnissen führen und dass der Wert eines Ausdrucks unabhängig von der gewählten Reihenfolge der Reduktionsschritte ist.
3. Diamant- und Rauteneigenschaft

Aufgabe 5 (12 + 6 + 4 = 22 Punkte)

1. Die Funktion könnte beispielsweise so ausschauen:

   -- h ... Haendler
   -- m ... Markt
   -- a ... Artikel
   
   bb :: Haendler -> Markt -> Markt
   bb h m = \h' -> if h' == h
                   then \a' -> min_preis m a'
                   else m h'
       where
           preis h a = (m h) a
           min_preis m a = min (preis H1 a) (min (preis H2 a) (preis H3 a))
   
   -- minor adjustments (Padraig)
   
   bb :: Haendler -> Markt -> Markt
   bb h m = \h' -> (if h' == h 
                    then WK (\a' -> min_preis m a')
                    else m h')
     where 
       preis h a = (unpack (m h)) a
       min_preis m a = min (preis H1 a) (min (preis H2 a) (preis H3 a))
       unpack (WK fkt) = fkt
   

2. Mithilfe des Lambda-Kalküls (Zeile 6) wird der neue Markt so zurückgegeben, dass im Falle des angegebenen Händlers ein neuer Warenkatalog zurückgegeben wird (Zeile 7), der bei jedem Artikel einen neuen minimalen Preis auswählt.
3. Warenkatalog könnte auch ein newtype, oder noch besser, ein type (Synonym für die Funktion) sein: type Warenkatalog = (Artikel -> Preis)