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

Für die Aufgabenstellungen, siehe [1]

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

1.1: a) Richtig b) Falsch

1.2:

data Klammer = A | Z deriving Eq
type Klammerfolge = [Klammer]

ist_kg :: Klammerfolge -> Bool
ist_kg [] = error "Leere Klammerfolge!"
ist_kg kf
 | ist_kg_r kf 0 == 0 = True
 | otherwise = False

ist_kg_r :: Klammerfolge -> Int -> Int
ist_kg_r [] counter = counter
ist_kg_r (x:xs) counter
 | counter < 0 = (-1)
 | x == A = ist_kg_r xs (counter+1)
 | otherwise = ist_kg_r xs (counter-1)

1.3: Fehlerbehandlung mit Panikmodus, weil sowohl True als auch False Rückgabewerte bei regulären Berechnungen sein können.

Aufgabe 2 (2+8+4+2*2 = 18 Punkte)

2.1: Nein, das kann nicht ausgenutzt werden. Um die Listen sortieren zu können, müssten die Listenelemente größenvergleichbar sein. Der Typklassen-Constraint ```Eq a =>``` erlaubt aber nur Gleichheits-Vergleiche. Mit dem strengeren Constraint ```Ord a =>``` wäre ein Nutzen von Sortierung möglich.

2.2:

import Data.List

sind_ae :: Eq a => [a] -> [a] -> Bool
sind_ae [] [] = True
sind_ae _ [] = False
sind_ae [] _ = False
sind_ae (h:rest1) list2 = if contained then sind_ae rest1 list2rest else False
    where list2rest = delete h list2
          contained = length list2 == length list2rest

2.2 (Alternativlösung):

import Data.List

sind_ae :: Eq a => [a] -> [a] -> Bool
sind_ae [] [] = True
sind_ae _ [] = False
sind_ae [] _ = False
sind_ae l1 l2
 | (length l1) == (length l2) = sind_ae_r l1 l2
 | otherwise = False

sind_ae_r :: Eq a => [a] -> [a] -> Bool
sind_ae_r [] l2 = True
sind_ae_r (x:xs) l2
 | x `elem` l2 = sind_ae_r xs (delete x l2)
 | otherwise = False

Anmerkung zu den Lösungen, die Data.List für die delete Funktion importieren: Alternativ könnte man ohne den Import auskommen (würde mich nicht wundern, wenn es dafür nicht die volle Punktezahl gäbe), indem man eine Listenkonkatenation in die Rekursion füttert: Am Beispiel der Alternativlösung etwa:

sind_ae_r :: Eq a => [a] -> [a] -> Bool
sind_ae_r [] l2 = True
sind_ae_r (x:xs) l2
 | x `elem` l2 = sind_ae_r xs [y | y <- l2, not(y==x)]
 | otherwise = False

Hab vor dem Speichern noch überlegt, ob dann nicht auch sind_ae [3,3,3] [3,3,3] False zurückgeben würde - bei meiner Implementierung nicht, weil sie auch auf den Basisfall zweier leerer Listen zurückführt. Kann aber unerwünschte Effekte haben, weil Data.List.delete nur jeweils ein Element löscht und die Listenkonkatenation sämtliche gleiche Elemente rausnimmt.

Anmerkung zu Data.List Punkteabzug: Laut Discord/TUWEL-Forum (https://tuwel.tuwien.ac.at/mod/forum/discuss.php?d=294577) ist es erlaubt, ohne mit Punkteabzug rechnen zu müssen, irgendwelche Module zu importieren, falls dies nicht explizit verboten wird per Angabenstellung (was bisher noch nie passiert ist).

2.3: Der erste Zweig ist der positive base-case - die leere Liste ist 'ähnlich' der leeren Liste, und alle anderen ähnlichen Listen-Paare werden auf diesen Fall zurückgeführt. Die beiden Zweige danach fangen nicht-ähnliche Listen ab. Der direkt rekursive Schritt passiert im letzten Zweig: das erste Element der ersten liste wird genommen, und per 'delete :: (Eq a) => a -> [a] -> [a]' (aus Data.List) wird dieses Element aus der zweiten Liste gelöscht, wenn es denn dort drinnen ist. Der boolean 'contained' checkt, ob das Element drinnen war. War es drinnen, wird sind_ae rekursiv mit den nun kürzeren Listen aufgerufen, war es nicht drinnen, sind die Listen nicht ähnlich.

2.4: a) Repetitive Rekursion, weil pro Zweig höchstens ein rekursiver Aufruf und dieser als äußerste Operation existiert. b) Ad-hoc polymorph, weil Typvariable und Typkontext erkennbar ist.

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

3.1: Baumartige Rekursion, weil pro Zweig mehrere rekursive Aufrufe nebeneinander vorkommen.

3.2: F, B, K

3.3: F: 1-stellig, B: 2-stellig, K: 3-stellig

3.4: a) 1 und zwar F b) 2 und zwar B und K c) 0

3.5: T1, T2 und T3 sind Typkonstruktoren. F, B und K sind Datenwertkonstruktoren.

F :: (a -> a -> a) -> T1 a
B :: a -> a -> T2 a
K :: T2 a -> [a] -> T2 a -> T2 a

3.6: Mit Haskell überprüft:
data/newtype T1 a = F(a -> a -> a)
data T2 a = B a a | K (T2 a) [a] (T2 a)
type T3 a = [a]

3.7: a) Falsch, weil sowohl data als auch newtype möglich ist. b) Richtig c) Richtig

Aufgabe 4 (3*1+3*1+3*1+8+4 = 21 Punkte)

4.1: a) 6*x+2 b) 20*x^3-6*x+2 c) 9.42*x^2-2.72

4.2: f1: [3,2,5] f2: [5,0,-3,2,0] f3: [3.14,0,-2.71,1.57] f1': [6,2] f2': [20,0,-6,2] f3': [9.42,0,-2.71]

4.3: a) Falsch b) Richtig und zwar: f(x) = 0 c) Richtig und zwar: f(x) = 0*x+0

4.4:

type Koeffizient = Double
type RatFunktion = [Koeffizient]

abl :: RatFunktion -> RatFunktion
abl rf = take ((length rf)-1) (abl_r rf True ((length rf)-1))

abl_r :: RatFunktion -> Bool -> Int -> RatFunktion
abl_r [] b i = []
abl_r (x:xs) b i
 | x == 0 && b = abl_r xs True (i-1)
 | otherwise = (x*(fromIntegral i)):(abl_r xs False (i-1))

Andere Lösung:

type Koeffizient = Double
type RatFunktion = [Koeffizient]

abl :: RatFunktion -> RatFunktion
abl [] = []
abl a
    | length a == 1 = [0]
    | head a == 0 = abl (tail a)
    | otherwise = (init [ a * fromIntegral i | (a,i) <- zip a [((length a)-1), (length a)-2..0]])

Eine einfachere Lösung:

type Koeffizient = Double
type RatFunktion = [Koeffizient]

abl :: RatFunktion -> RatFunktion
abl [k]     = [0]
abl [k1,k2] = [k1]
abl (0:ks)  = abl ks
abl (k:ks)  = k*(fromIntegral (length ks)) : abl ks
abl []      = []

Andere Lösung (da m.m.n die einfachere Lösung oben nicht funktional ist. Gegenbeispiel [0,0,4,3,0,2]:

type Koeffizient = Double
type RatFunktion = [Koeffizient]
abl :: RatFunktion -> RatFunktion
abl (x:xs) = if x == 0 then abl xs else abl_r ([x] ++ xs)
abl [] = []

abl_r :: RatFunktion -> RatFunktion
abl_r (x:xs) = [x * fromIntegral(length xs)] ++ abl xs
abl_r [] = []

4.5: Führende 0er werden gestrichen ohne in den Panikmodus zu wechseln.

Aufgabe 5 (3*1+5+5+2*2.5 = 18 Punkte)

5.1: a) [] b) RF 0 ([0]!!) c) RF 2 ([3.14,2.71,1.57]!!)

5.2:

t :: RatFunktion -> RatFunktion'
t rf = RF ((length rf)-1) ((reverse rf) !!)

5.3:

t' :: RatFunktion' -> RatFunktion
t' (RF i f) = t'' (RF i f) []
 where
  t'' (RF i f) rf
   | i < 0 = rf
   | otherwise = t'' (RF (i-1) f) ((f i):rf)

andere Lösung

t' :: RatFunktion' -> RatFunktion
t' (RF 0 f) = [f 0]
t' (RF n f) = (f n):(t' (RF (n-1) f))

Materialien

Neues Material hinzufügen

P

• Prüfung 2023-01-19 (Lösungsvorschlag)