TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2021-01-14

Lösungsvorschlag (wip). Die erklärenden Textpassagen sind natürlich bei einer tatsächlichen Prüfung nur dort notwendig, wo explizit Erklärungen gefragt sind - und selbst dort wo sie gefragt sind, sind hier sie hier übermäßig ausführlich.

Aufgabe 1 ((1+1)+10+6 = 18 Punkte)

Angabe

Zwei Zeichenreihen heißen umstellungsgleich gdw.: die beiden Zeichenreihen können durch Ändern der Reihenfolge ihrer Zeichen ineinander überführt werden. 1) Geben Sie je ein Paar von Zeichenreihen an, die

• a) umstellungsgleich
• b) nicht umstellungsgleich sind.

2) Schreiben Sie eine uncurryfizierte Haskell-Wahrheitswertfunktion sind_ug einschließlich ihrer syntaktischen Signatur, die angewendet auf ein Paar von Zeichenreihen bestimmt, ob die Zeichenreihen umstellungsgleich sind.

3) Erklären Sie knapp, aber gut nachvollziehbar, wie ihre Wahrheitswertfunktion vorgeht.

Lösungsvorschlag

1) Die Beschreibung von 'umstellungsgleich' lässt sich umdeuten als: "Zwei Strings sind umstellungsgleich, wenn sie die genau die selben Buchstaben, jeweils gleich oft (aber in beliebiger Reihenfolge) enthalten". Ich interpretiere "Paar von Zeichenreihen" als ein tatsächliches Haskell-Paar, als den Typen (String, String).

• a) ("abc", "cba")
• b) ("abc", "abcde")

2)

import Data.List

sind_ug :: (String, String) -> Bool
sind_ug (s1, s2) = (sort s1) == (sort s2)

alternative 1:

 qsort :: String -> String
 qsort (x:xs) = (qsort [y | y <- xs, y < x]) ++ [x] ++ (qsort [ y | y <- xs, y > x])
 qsort [] = []

 sind_ug :: (String, String) -> Bool
 sind_ug (a, b) = (qsort a) == (qsort b)

alternative 2:

sindUg :: (String, String) -> Bool
sindUg (a,b) = gleichLang a b && pruefeUg a b 

entferneAusListe :: String -> Char -> String
entferneAusListe (a:as) b = if a == b then as else a : entferneAusListe as b  

gleichLang :: String -> String -> Bool 
gleichLang a b = length a == length b

kommtVor :: String -> Char -> Bool 
kommtVor [] _ = False 
kommtVor (a:as) b = (a == b) || kommtVor as b 

pruefeUg :: String -> String -> Bool
pruefeUg [] [] = True
pruefeUg _ [] = False
pruefeUg [] _ = False
pruefeUg (a:as) b = kommtVor b a && pruefeUg as (entferneAusListe b a)

3) Mein sind_ug nutzt aus, dass String ein Typalias von [Char] ist, und dass Char Element der Typklasse Ord ist. Mit der sort Funktion aus dem dem Data.List Modul (teil des base package, welches bei Übung und Prüfung erlaubt ist) bringen wir die beiden Strings in eine "kanonische Form" (konkret: alphabetisch sortiert) und vergleichen diese kanonischen Formen direkt mit == . Die beiden ursprünglichen Strings sind umstellungsgleich, gdw die beiden kanonischen Formen gleich sind.

Die Klammern um sort sX sind hier tatsächlich überflüssig, aber im Zweifelsfall sind zu viele besser als zu wenige.

Aufgabe 2 (4+6 = 10 Punkte)

Angabe

Gegeben sind folgende Typ- und Instanzdeklarationen:

type Info a = [a]
data Baum a = B (Info a)
              | K (Baum a) (Info a,Info a) (Baum a)
instance (Ord a,Show a) => Eq (Baum a) where
 B xs       == B ys           = xs == ys
 B _        == K _ _ _        = False
 K _ _ _    == B _            = False
 K b1 ps b2 == K b1' ps' b2'  = b1 == b1' && ps == ps' && b2 == b2'

Geben Sie jeweils das Zutreffende an und ergänzen Sie anstelle der Auslassungspunkte (...) die Begründungen: In der Instanzdeklaration für Baum a

1) kann die Kontextbedingung (Ord a,Show a) =>

• a) weggelassen werden
• b) nicht weggelassen werden
• c) nicht weggelassen werden, aber vereinfacht werden bis hin zu ...

weil ...

2) haben die verschiedenen Vorkommen von ==

• a) dieselbe
• b) nicht dieselbe

Bedeutung, weil ... und sind dabei jeweils vom Typ ... bzw. den Typen ...

Lösungsvorschlag

1) nicht weggelassen werden, aber vereinfacht werden bis hin zu Eq a =>, weil die Implementatierung von (==) :: Baum a -> Baum a -> Bool nur den Gleichheitsvergleich (==) auf den ((Tupel von) Listen von) a benutzt - und keinen Größenvergleich (etwa <=) oder die "to string" funktion show.

2) nicht dieselbe Bedeutung, weil zwar immer die grobe Bedeutung "sind erstes und zweites Argument gleich" überprüft bzw. definiert werden, aber aufgrund der unterschiedlichen Argument-Typen tatsächlich unterschiedliche Implementierungen von (==) zum Einsatz kommen. Die verschiedenen (==) sind dabei teils vom Typ Baum a -> Baum a -> Bool, [a] -> [a] -> Bool, sowie ([a],[a]) -> ([a],[a]) -> Bool

Extra Anmerkung: für jeden Typ a, der elem der Eq-Typklasse ist, ist in Haskell auch automatisch das (==) auf [a] und (a,a) definiert. Nämlich mit den "natürlichen" Bedeutungen "beide Listen haben die gleichen Elemente, in der selben Reihenfolge", bzw. "die beiden ersten Komponenten sind gleich und die beiden zweiten Komponenten ebenso"

Aufgabe 3 (6+6+6 = 18 Punkte)

Angabe

1) Was haben normale und faule (Ausdrucks-) Auswertung gemeinsam, worin stimmen sie überein?

2) Was unterscheidet sie, worin stimmen sie nicht überein?

3) Welche Gewissheiten ergeben sich für den Programmierer aus den Gemeinsamkeiten und Unterschieden für die Programmierung in einer funktionalen Programmiersprache mit fauler Auswertung?

Lösungsvorschlag

1) Argumente werden nur ausgewertet, wenn sie unbedingt benötigt werden und die Auswertung terminiert bei allen Ausdrücken, für die es irgendeine terminierende Auswertungsfolge gibt.

2) Die normale Auswertung wertet Ausdrücke so oft aus, wie sie verwendet (und gebraucht) werden. Die faule Auswertung dagegen nur (maximal) einmal.

3) Bei der Programmierung mit fauler Auswertung sind Mehrfachvorkommen eines Ausdrucks irrelevant für die Laufzeit. Auch können konzeptionell unendliche Strukturen/Zwischenergebnisse benutzt werden (etwa: unendliche Listen), wenn diese tatsächlich nur endlich weit ausgewertet werden müssen (a la take 50 $ some_infinite_list)

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

Angabe

Gegeben ist die Funktion f:

f x y z = if (((x*x) - 42) > 0) then x * (y+y) else x*y*z

und der Funktionsterm: f (5*(3+2)) (2+3*5) (3+5).

Wie oft wird der Ausdruck

1) (5*(3+2)) bei

• a) applikativer
• b) normaler
• c) fauler

Auswertung von f (5*(3+2)) (2+3*5) (3+5) ausgewertet?

2) (2+3*5) bei

• a) applikativer
• b) normaler
• c) fauler

Auswertung von f (5*(3+2)) (2+3*5) (3+5) ausgewertet?

3) (3+5) bei

• a) applikativer
• b) normaler
• c) fauler

Auswertung von f (5*(3+2)) (2+3*5) (3+5) ausgewertet?

Lösungsvorschlag

1)

• a) 1
• b) 3
• c) 1

2)

• a) 1
• b) 2
• c) 1

3)

• a) 1
• b) 0
• c) 0

Aufgabe 5 (3+2+2 = 7 Punkte)

Angabe

1) Welches ist der allgemeinste Typ von f aus Aufgabe 4? Begründen Sie Ihre Antwort.

2) Ist der allgemeinste Typ von f aus Aufgabe 4 monomorph oder polymorph? Falls polymorph, geben Sie die Polymorphieart möglichst genau an und erklären Sie, woran die Polymorphieart hier zu erkennen ist.

3) Welches ist der allgemeinste Typ von f aus Aufgabe 4, wenn die Bedingung (((x*x) - 42) > 0) im Fallunterscheidungsausdruck durch (((x*x) - 42) /= 0) ersetzt wird? Begründen Sie Ihre Antwort.

Lösungsvorschlag

1)

f :: (Ord a, Num a) => a -> a -> a -> a
f x y z = if (((x*x) - 42) > 0) then x * (y+y) else x*y*z

Doofe aber praxisnahe Erklärung: "weil GHCi bei :t f diese Signatur ausspuckt". Testkompatible Erklärung: Da die 3 Parameter x, y, z mit numerischen Operationen (+, -, *) untereinander verknüpft werden, müssen alle 3 den selben Typ haben, und dieser Typ muss Element der Typklasse Num sein. Der Größer-Vergleich von (x*x) - 42) mit 0 erfordert von dem Typen zusätzlich, Element von Ord zu sein.

2) Er ist polymorph - mehr als ein Typ kann für die Typvariable a in f's Signatur einstehen. (Ich denke) Genauer gesagt handelt es sich um Ad-Hoc Polymorphie, da die Typvariable nicht für beliebige, sondern nur für bestimmte Typen stehen kann - jene die (durch eine instance declaration) zu Elementen der Typklassen Ord und(!) Num gemacht wurden.

3)

f :: (Num a) => a -> a -> a -> a
f x y z = if (((x*x) - 42) /= 0) then x * (y+y) else x*y*z

Der Größenvergleich fällt weg, womit die Ord-Einschränkung nicht mehr gebraucht wird. Stattdessen reicht auch ein Typ der Eq-Element ist ((Eq a, Num a) => ...). Alle Elemente von Num sind gezwungenermaßen auch Element von Eq, weswegen man das "Eq a" hier weglassen kann. (siehe auch Typklassenhierachie in den Folien.)

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

Angabe

Die charakteristische Funktion $\mathrm {X} _{M}:\mathbb {Z} \to \{wahr,falsch\}$ einer Menge ganzer Zahlen $M$ ist definiert durch:

$\mathrm {X} _{M}(z)=_{df}{\begin{cases}wahr&{\text{falls }}z\in M\\falsch&{\text{falls }}z\notin M\end{cases}}$

Eine charakteristische Funktion repräsentiert damit auf eindeutige Weise eine Menge ganzer Zahlen $M_{\mathrm {X} }\subseteq \mathbb {Z}$ definiert durch:

$M_{\mathrm {X} }=_{df}\{z\in \mathbb {Z} |\mathrm {X} _{M}(z)=wahr\}$

Mengen ganzer Zahlen können deshalb durch ihre charakteristische Funktionen repräsentiert und modelliert werden. In Haskell ist das auf folgende Weise möglich:

type Zett = Integer
type CharFunk = Zett -> Bool
type Menge = CharFunk

Schreiben Sie Haskell-Rechenvorschriften für folgende Mengenoperationen:

1) Elementeigenschaft: $z\in M$

ist_Element_von :: Zett -> Menge -> Bool

2) Mengenvereinigung: $M_{1}\cup M_{2}=_{df}\{m|m\in M_{1}\lor m\in M_{2}\}$

vereinigung :: Menge -> Menge -> Menge

3) Mengendifferenz: $M_{1}\backslash M_{2}=_{df}\{m|m\in M_{1}\land m\notin M_{2}\}$

differenz :: Menge -> Menge -> Menge

Die Funktionen vereinigung und differenz müssen so definiert sein, dass ihre Resultate unmittelbar als Mengenargument von ist_Element_von verwendet werden können.

Lösungsvorschlag

1)

 ist_Element_von :: Zett -> Menge -> Bool 
 ist_Element_von z m = m z

2)

 -- vereinigung :: (Integer -> Bool) -> (Integer -> Bool) -> (Integer -> Bool)
 vereinigung :: Menge -> Menge -> Menge
 vereinigung  m1 m2 = \ x -> (m1 x) || (m2 x) -- m3

3)

 differenz:: Menge -> Menge -> Menge
 differenz m1 m2 = \ x -> (m1 x) && (not(m2 x)) -- m3

Aufgabe 7 (4+4 = 8 Punkte)

Angabe

Mit den Bezeichnungen und Typen von Aufgabe 6: Implementieren Sie folgende Mengenoperationen oder begründen Sie informatisch präzise, wenn das nicht möglich ist, warum nicht:

1) Komplementmenge zu einer Grundmenge $G:\mathrm {K} _{G}(M)=_{df}\{m\in G|m\notin M\}$

komplement :: Menge -> Menge (zur Grundmenge Z)

2) Mengengleichheit: $M_{1}=M_{2}=_{df}m\in M_{1}\Leftrightarrow m\in M_{2}\}$

sind_gleich :: Menge -> Menge -> Bool

Lösungsvorschlag

1) Anmerkung: In der Angabe ist mit "Grundmenge Z" wohl präziser der Typ "Zett = Integer", oder aber die Menge der Ganzen Zahlen mit dem Symbol $\mathbb {Z}$, gemeint.

type Zett = Integer
type CharFunk = Zett -> Bool
type Menge = CharFunk


-- type is equivalent to: (Zett -> Bool) -> (Zett -> Bool)
komplement :: Menge -> Menge
komplement m1 = \x -> not(m1 x)

2) Die Funktion sind_gleich ist nicht implementierbar, da die Equivalenz von zwei Funktionen im Allgemeinen unentscheidbar ist. Siehe z.B. https://stackoverflow.com/questions/1132051/is-finding-the-equivalence-of-two-functions-undecidable

Aufgabe 8 (6+4+3+1+(2+2) = 18 Punkte)

Angabe

1) Implementieren Sie f als Haskell-Funktion höherer Ordnung f über dem Typsynonym Z, wobei das Resultat von f von funktionalem Wert sein muss:

type Z = Integer
f :: (Z -> Z) -> (Z -> Z)

2) Erklären Sie knapp, aber gut nachvollziehbar, wie ihre Implementierung für f vorgeht.

3) Geben Sie Implementierungen für g1, g2, g3 an, so dass die geforderte Eigenschaft gilt:

• (a) ∀ z ∈ Z. f g1 z = z∗(z+1)/2

• (b) ∀ z ∈ Z. f g2 z = 0

• (c) ∀ z ∈ Z. f g3 z = 1

4) Sind die Implementierungen für g1, g2, g3 eindeutig bestimmt? Begründen Sie Ihre Antwort.

5) Geben Sie die

• (a) curryfizierte

• (b) uncurryfizierte

Lesart von f an.

Lösungsvorschlag

1)

type Z = Integer


f :: (Z -> Z) -> (Z -> Z)
f g z = f_helper g z 0 0


f_helper :: (Z -> Z) -> Z -> Z -> Z -> Z
f_helper g z i summe
    | i > betrag z = summe
    | otherwise = f_helper g z (i+1) (summe + (g i))

betrag :: Z -> Z
betrag i
    | i < 0 = i * (-1)
    | otherwise = i

oder:

f :: (Z->Z)->(Z->Z)
f g = \z -> sum [g i | i <- [0..|z|]]

Wobei |*| per Angabe definiert ist. Für kompilierbaren Code könnte |z| einfach durch 'abs z' ersetzt werden.

2)

Der alternative Lösungsvorschlag geht folgendermaßen vor:

Die Funktion f angewandt auf die Funktion g liefert eine anonyme Funktion zurück, welche angewandt auf einen Integer z folgendermaßen vorgeht:

Zunächst wird mittels List-comprehension eine Liste von Integern von 0 bis zum Betrag von z erstellt und die Funktion g einzeln auf jeden Wert angewandt.

Anschließend werden die Einträge der so entstandenen Liste mittels der Funktion sum aufsummiert.

3)

a)

 (*1)

b)

 (*0)

c)

 (\z -> if z == 0 then 1 else 0)

4) Nein, es gibt zb folgende Alternativen:

a)

 (\z -> 0*z + z)

b)

 (\z -> z-z)

c)

 (\z -> if z == 0 && True then 1 else 0)

5) a) Curryfizierte Leseart: Die Funktion f bildet eine Funktion, welche Integer auf Integer abbildet, auf eine Funktion ab, welche Integer auf Integer abbildet. b) Uncurryfizierte Leseart: Die Funktion f bildet einen Integer, unter Zuhilfenahme einer Funktion, welche Integer auf Integer abbildet, auf einen Integer ab.