TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2022-01-13 (Lösungsvorschlag)

Aufgabe 1 (8+4+2 = 14 Punkte)

Ganzzahlige Polynome

$\sum _{i=0}^{n}c_{i}x^{i}$

über der Variablen $x$ lassen sich durch die Liste ihrer ganzzahligen Koeffizienten

$[c_{n},\dots \,c_{2},c_{1},c_{0}]$

darstellen; die Koeffizienten $c_{0},c_{1},\dots ,c_{n}$und die Variable $x$ nehmen also ausschließlich ganzzahlige Werte

an.

1. Schreiben Sie eine Rechenvorschrift pw, die den Wert solcher Polynome für beliebige Stellen $x$ berechnet; pw soll rekursiv sein oder sich auf eine rekursive Funktion abstützen. Verwenden Sie aussagekräftige Typsynonyme und geben Sie die Signatur von pw an. Gibt es Fälle, die eine Ausnahmebehandlung erfordern? Wenn ja, behandeln Sie sie im Panikmodus.
2. Erklären Sie knapp, aber gut nachvollziehbar, wie ihre Implementierung vorgeht.
3. Von welchem Rekursionstyp ist Ihre Implementierung von pw bzw. die etwaiger Hilfsfunktionen, auf die sich Ihre Implementierung von pw abstützt? Begründen Sie Ihre Antwort.

-- 1.1

type Koeffizient = Integer

type Polynom = [Koeffizient]

pw :: Polynom -> Integer -> Integer
pw [] x = 0
pw (h : t) x = h * (x ^ length t) + pw t x

-- Es gibt keine Ausnahmefaelle, sowohl positive als auch negative Zahlen koennen Koeffizienten sein
-- Polynome koennen an jeder Stelle ausgewertet werden

-- 1.2
-- Es wird immer der erste Koeffizent genommen und dort der Wert an der Stelle x ausgewertet.
-- Danach wird das Ergebnis zum restlichen, ausgewerteten Polynom addiert.

-- 1.3.
-- Es ist eine lineare Rekursion. Jeder Schritt ruft sich selber null bis einmal auf.
-- Die oberste Funktion ist das +, deshalb ist es keine triviale Rekursion.

Aufgabe 2 (2*6+2*3+2*3 = 24 Punkte)

Für Aufgabe 2 kann die Funktion pw aus Aufgabe 1 als gegeben vorausgesetzt werden. Eine Stelle $w$ heißt Wurzel eines ganzzahligen Polynoms gdw (genau dann, wenn) gilt: $\sum _{i=0}^{n}c_{i}w^{i}=0$

1. Schreiben Sie zwei curryfizierte Rechenvorschriften w1, w2, die angewendet auf ein ganzzahliges Polynom $p$ in der Darstellung aus Aufgabe 1, eine ganze Zahl $k$ und eine ganze Zahl $l{\text{ }}$ in aufsteigender Anordnung die Liste der Wurzeln $w$ von $p$ mit $k\leq w\leq l$ liefern. Verwenden Sie aussagekräftige Typsynonyme und geben Sie die syntaktischen Signaturen von w1, w2 vollständig, aber nicht überflüssig geklammert, an. Wenden Sie, wenn nötig, dieselbe Ausnahmebehandlung wie in Aufgabe 1 an und implementieren Sie
   • w1 schlicht rekursiv.
   • w2 als Realisierung des Generator/Filter-Prinzips.
2. Erklären Sie knapp, aber gut nachvollziehbar, wie ihre Implementierungen von
   • w1
   • w2

   vorgehen.

3. Geben Sie die
   • currifizierte
   • uncurrifizierte

   Lesart der Signatur von entweder w1 oder w2 an.

type Koeffizient = Integer
type Polynom = [Koeffizient]
type Nullstelle = Integer

w1 :: Polynom -> (Integer -> (Integer -> [Nullstelle]))
w1 poly k l
  | k > l = []
  | pw poly k == 0 = [k] ++ (w1 poly (k + 1) l)
  | otherwise = w1 poly (k + 1) l

w2 :: Polynom -> (Integer -> (Integer -> [Nullstelle]))
w2 poly k l
  | k > l = error "k must be <= 0"
  | otherwise = [n | n <- [k .. l], pw poly n == 0]

-- Alternative für w2
w2 :: Polynom -> (Integer -> (Integer -> [Nullstelle]))
w2 poly k l
  | k > l = erro "k must be <= 0"
  | otherwise = filter (\x -> pw poly x == 0) [k..l]

Die erste Implementierung überprüft immer, ob untere Schranke k eine Nullstelle ist. Danach geht es rekursiv mit k+1 weiter, bis k > l.

Die zweite Implementierung generiert die Werte zwischen k und l, überprüft ob diese Nullstellen sind und gibt sie abhängig davon in eine Liste. Hier ist der Fall k > l als Fehler definiert.

Hinweis: w1 ist linear und nicht schlicht rekursiv (bei einem Zweig ist der rekursive Aufruf nicht die äußerste Operation (++ ist im 2. Zweig die äußerste Operation) Alternative Lösung:

w1 :: (Polynom -> (Integer -> (Integer -> [Nullstelle])))
w1 poly k l = w1' poly k l []
  where
    w1' poly k l r
      | k > l = r
      | pw poly k == 0 = w1' poly (k + 1) l (r ++ [k])
      | otherwise = w1' poly (k + 1) l r

Hinweis: bei w1 und w2 sind die Signaturen nicht vollständig geklammert. Es fehlen jeweils die Klammern um die gesamte Signatur:

w1,w2 :: (Polynom -> (Integer -> (Integer -> [Nullstelle])))

Curryfiziertes w1:

w1 :: Polynom -> Integer -> Integer -> [Nullstelle]

w1 ist eine 1-stellige Funktion, die Polynom-Werte auf Funktionen abbildet, die Integer-Werte auf Funktionen abbildet, die Integer-Werte auf eine Liste von Nullstellen-Werten abbildet.

Uncurryfiziertes w1:

w1 :: (Polynom, Integer, Integer) -> [Nullstelle]

w1 ist eine 3-stellige Funktion, die Tupel aus Polynom-, Integer- und Integer-Werten auf eine Liste von Nullstellen-Werten abbildet.

Aufgabe 3 (2*1+2+2*3+2*2+3*4 = 26 Punkte)

Gegeben sind die Funktionen f und g mit:

f :: Num a => a -> a -> a
f x y = (((x + y) * (x - y)) + (x * y))

g :: (a -> a) -> [a] -> [a]
g _ [] = []
g h (x:xs) = (((h . h) x) : (g h xs))

1. Geben Sie die Polymorphietypen von
(a) f
(b) g

möglichst genau an.

2. Richtig oder falsch? Der Typ von g kann verallgemeinert werden zu:

g :: (a -> b) -> [a] -> [b]

Begrunden Sie Ihre Antwort.

3. Richtig oder falsch?
Bei Auswertung jedes gultigen Aufrufs von
(a) f
(b) g
wird der exakt selbe Code ausgefuhrt. Begrunden Sie Ihre Antwort jeweils.

4. Welche Klammern können im Rumpf von
(a) f
(b) g
weggelassen werden, ohne die Bedeutung zu verändern oder syntaktische Korrektheit zu verlieren?
Geben Sie die minimal geklammerten Rumpfe von f und g an und begründen Sie Ihre Antwort.

5. Geben Sie jeweils die ersten 6 Schritte der Auswertung des Ausdrucks:

2 + 3 + f (3 + 5) (9 - 2 * 3) * 6 ‘div‘ 2

bei
(a) rechtsapplikativer
(b) nicht fauler rechtsnormaler
(c) fauler rechtsnormaler
Auswertung an. Ein Schritt ist dabei ein Expansionsschritt oder eine Operatoranwendung eines Simplifikationsschritts. Ein Expansionsschritt konsumiert alle Argumente der expandierten Funktion. Simplifikation geht bei gleicher Operatorpriorität rechtsassoziativ vor, wenn nicht explizit angegebene Klammerung anderes verlangt.

3.1 f ist ad-hoc Polymorph g ist echt Polymorph

3.2 Der Typ von g kann nicht weiter verallgemeinert werden weil (h.h) das Ergebnis von h wieder in h reingibt. Also muss der Typ zumindest (a -> a) sein.

3.3 Bei einem Aufruf von f wird nicht immer der selbe Code ausgeführt. Addition kann für verschiedene Num s verschieden implementiert sein. z.B. Int und Matrix Bei jedem Aufruf von g wird der exakt selbe Code ausgeführt. Die Funktion ist echt Polymorph.

3.4 Klammern bei f: Mathematische Operatoren haben die * vor + Reihenfolge

f x y = (x + y) * (x - y) + x * y

Klammern bei g: Äußere Klammern braucht man nicht und Funktionsapplikation bindet stärker als :

g h (x:xs) = (h . h) x : g h xs

3.5

a) rechtsapplikativ (rechts-innerst; Argumente ausgewertet übergeben)

2 + 3 + f (3 + 5) (9 - 2 * 3) * 6 ‘div‘ 2

(S) 2 + 3 + f (3 + 5) (9 - 2 * 3) * 3
(S) 2 + 3 + f (3 + 5) (9 - 6) * 3
(S) 2 + 3 + f (3 + 5) (3) * 3
(S) 2 + 3 + f (8) (3) * 3
(E) 2 + 3 + ((8 + 3) * (8 - 3) + 8 * 3) * 3
(S) 2 + 3 + ((8 + 3) * (8 - 3) + 24) * 3

b) nicht fauler rechtsnormal (rechts-äußerst; Argumente unausgewertet übergeben)

2 + 3 + f (3 + 5) (9 - 2 * 3) * 6 ‘div‘ 2

(S) 2 + 3 + f (3 + 5) (9 - 2 * 3) * 3
(E) 2 + 3 + (((3 + 5) + (9 - 2 * 3)) * ((3 + 5) - (9 - 2 * 3)) + (3 + 5) * (9 - 2 * 3))  * 3
(S) 2 + 3 + (((3 + 5) + (9 - 2 * 3)) * ((3 + 5) - (9 - 2 * 3)) + (3 + 5) * (9 - 6))  * 3
(S) 2 + 3 + (((3 + 5) + (9 - 2 * 3)) * ((3 + 5) - (9 - 2 * 3)) + (3 + 5) * 3)  * 3
(S) 2 + 3 + (((3 + 5) + (9 - 2 * 3)) * ((3 + 5) - (9 - 2 * 3)) + 8 * 3)  * 3
(S) 2 + 3 + (((3 + 5) + (9 - 2 * 3)) * ((3 + 5) - (9 - 2 * 3)) + 24)  * 3

c) fauler rechtsnormaler (rechts-äußerst; Argumente unausgewertet übergeben; gleiche Ausdrücke gleichzeitig auswerten)

2 + 3 + f (3 + 5) (9 - 2 * 3) * 6 ‘div‘ 2

(S) 2 + 3 + f (3 + 5) (9 - 2 * 3) * 3
(E) 2 + 3 + (((3 + 5) + (9 - 2 * 3)) * ((3 + 5) - (9 - 2 * 3)) + (3 + 5) * (9 - 2 * 3))  * 3
(S) 2 + 3 + (((3 + 5) + (9 - 6)) * ((3 + 5) - (9 - 6)) + (3 + 5) * (9 - 6))  * 3
(S) 2 + 3 + (((3 + 5) + 3) * ((3 + 5) - 3) + (3 + 5) * 3)  * 3
(S) 2 + 3 + ((8 + 3) * (8 - 3) + 8 * 3)  * 3
(S) 2 + 3 + ((8 + 3) * (8 - 3) + 24)  * 3

Aufgabe 4 (1+10+5 = 16 Punkte)

Für rationale Zahlen $p$ und $q$ gilt:

• $p$ und $q$ sind gleich gdw $p$ und $q$ sind wertgleich (z.B.: ${\frac {2}{3}}$ ist wertgleich zu ${\frac {4}{6}}$ ist wertgleich zu ${\frac {8}{12}}$).
• $p$ ist kleiner/größer $q$ gdw $p$ ist wertkleiner/wertgrößer als $q$.
• $p$ ist kleiner/größer oder gleich $q$ gdw $p$ ist wertkleiner/wertgrößer als $q$ oder wertgleich zu $q$.
• $p$ ist in Normalform gdw Zähler und Nenner von $p$ sind vollständig gekürzt und höchstens der Zähler ist kleiner als Null; Normalformdarstellung der Null ist ${\frac {0}{1}}$.

Rationale Zahlen lassen sich wie folgt modellieren:

data ZN = Zaehler | Nenner deriving Eq
newtype Q = Q (ZN -> Int)

1. Gibt es Q-Werte, die keine rationale Zahl darstellen? Wenn ja, welche?
2. Schreiben Sie eine Haskell-Rechenvorschrift nf :: Q -> Q die ihr Argument in Normalform überführt. Sehen Sie eine Fehlerbehandlung vor, wenn das Argument keine rationale Zahl darstellt.
3. Erklären Sie knapp, aber gut nachvollziehbar, wie ihre Implementierung von nf vorgeht.

-- Hilfreiche Info: Q hat eine Funktion die entweder Zaehler oder Nenner akzeptiert. Und dann wird der dazugehörige Wert ausgespuckt. 
-- Also z.B. 
q2 = Q (\x -> case x of Zaehler -> 8
                        Nenner -> 12)
-- Und dann, wenn man Zaehler in die Funktion reingibt, wird 8 ausgespuckt.
-- Wenn man Nenner reingibt, wird 12 zurückgegeben. 
-- Siehe auch: Beispiel 5

-- 4.1
-- Ja, wenn Q Nenner == 0 ist, dann ist es eine Division durch Null. Das ist in den rationalen Zahlen undefiniert. Weiters kann die Funktion (ZN -> Int) für den Zaehler, Nenner oder beide nicht definiert sein.

-- 4.2

nf :: Q -> Q
nf (Q x)
  | n == 0 = error "Something is fishy ::<>"
  | n == 1 = Q x
  | n < 0 && z < 0 = nf (Q (\a -> - (x a)))
  | n < 0 = nf (Q (\a -> - (x a)))
  | otherwise = (Q (\a -> (x a) `div` ggt))
  where
    n = x Nenner
    z = x Zaehler
    ggt = head [y | y <- [m, (m -1) .. 1], n `mod` y == 0 && z `mod` y == 0]
    m = max (abs n) (abs z)

-- 4.3
-- Am Anfang werden Sonderfälle bzw. triviale Fälle behandelt. (Division durch 0, Nenner == 1)
-- Dann werden negative Fälle auf positive zurückgeführt
-- Am Ende wird der größte gemeinsame Teiler von Zähler und Nenner berechnet. Durch diesen wird dividiert.

andere Lösung für 4.2

nf :: Q -> Q
nf (Q f)
    | f Nenner == 0 = error "keine rationale Zahl"
    | otherwise = Q ((\g zn -> case zn of
                        Zaehler -> div (f Zaehler) g * signum (f Nenner)
                        Nenner -> abs (div (f Nenner) g)) (gcd (f Zaehler) (f Nenner)))

Aufgabe 5 (3*4+4+4 = 20 Punkte)

Für Aufgabe 5 kann die Funktion nf aus Aufgabe 4 als gegeben vorausgesetzt werden.

1. Machen Sie den Typ der rationalen Zahlen Q aus Aufgabe 4 zu einer Instanz der Typklassen:
   • Eq, indem Sie die Funktion (==) implementieren.
   • Ord, indem Sie die Funktion (<=) implementieren.
   • Show, indem Sie die Funktion show implementieren. Rationale Zahlen sollen dabei in Normalform ausgegeben werden, wobei Zähler und Nenner durch einen Schrägstrich getrennt sind, wie nachstehend am Beispiel von q1, q2 mit übereinstimmender Normalform gezeigt ist:

   q1 :: Q
   q2 :: Q
   q1 = Q (\x -> case x of Zaehler -> 2 
                           Nenner -> 3)
   q2 = Q (\x -> case x of Zaehler -> 8
                           Nenner -> 12)
   
   show q1 ->> "2/3"
   show q2 ->> "2/3"
   

Sehen Sie eine verschleiernde Fehlerbehandlung vor, wenn Argumente von Funktionen keine rationale Zahlen darstellen.

1. Erklären Sie knapp, aber gut nachvollziehbar, wie ihre Implementierungen der Instanzfunktionen vorgehen und warum die Fehlerbehandlung verschleiernd ist.
2. Ist statt einer verschleierndern auch eine transparente Fehlerbehandlung mit Auffangwerten in Aufgabe 5.1 möglich? Begründen Sie Ihre Antwort für die verschiedenen Instanzfunktionen.

-- 5.1
-- Hilfsfunktion die ich mir definiert habe
unQ :: Q -> ZN -> Int
unQ (Q a) = a

isQ :: Q -> Bool
isQ (Q x) = not (x Nenner == 0)

instance Eq Q where
  (==) a b
    | not (isQ a) || not (isQ b) = False
    | otherwise =
      unQ (nf a) Nenner == unQ (nf b) Nenner
        && unQ (nf a) Zaehler == unQ (nf b) Zaehler

instance Ord Q where
  (<=) (Q a) (Q b)
    | not (isQ (Q a)) || not (isQ (Q b)) = False
    | nA == nB = zA <= zB
    | otherwise = zA * nB <= zB * nA
    where
      nA = a Nenner
      zA = a Zaehler
      nB = b Nenner
      zB = b Zaehler

instance Show Q where
  show a
    | not (isQ a) = "0/1"
    | otherwise = show (unQ (nf a) Zaehler) ++ "/" ++ show (unQ (nf a) Nenner)

-- 5.2
-- Eq vergleicht Zähler und Nenner der Normalform.
-- Bei ungueltigen Werten wird False zurueckgegegben, genau so wie bei ungleichen Werten.
-- Also ist es verschleiernd.

-- Ord "ausmultipliziert" die Brueche und vergleicht das Ergebnis.
-- z.B. 2/3 <= 7/9 ist das gleiche wie 2*9 <= 7*3
-- False ist sowohl Fehlerwert als auch gueltiger Rueckgabewert, somit ist es verschleiernd.

-- Show gibt Zaehler und Nenner aus, mit / dazwischen
-- Bei einem Fehler wird "0/1" zurueckgegeben, genau so wie wenn man die Rationale Zahl 0 reingibt.
-- Also ist es verschleiernd.

-- 5.3
-- Bei Eq und Ord ist es nicht moeglich, es gibt zwei moegliche Rueckgabewerte und beide koennen bei normalen Funktionsaufrufen entstehen
-- Bei Show koennte man z.B. "cats are cute" als transparenten Fehlerwert definieren, weil dieser nie bei normalem Gebrauch entstehen kann.