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

Die Angaben sind hier jetzt nicht nochmal beschrieben. Ihr findet sie hier [1]

Aufgabe 1 (10+(4+4)+1 = 19 Punkte)

Mit "verschleiernde Fehlerbehandlung" meint der Prof, dass am Ergebnis eines qs-Aufrufs NICHT erkennbar sein soll, ob das Argument valid war. Nicht valide Argumente sind der Beschreibung entsprechend negative Zahlen.

1)

 qs :: Int -> Int
 qs n
   | n < 0     = 0
   | n < 10    = n
   | otherwise = lastDigit n + qs (n `div` 10)


 -- n modulo 10. In other words: gets right-most digit of "normal" decimal representation of n
 lastDigit :: Int -> Int
 lastDigit n = n `mod` 10

2) qs fängt invalide Argumente im ersten guard ab und bildet sie verschleiernd auf 0 ab. n < 10 bildet den base case valider Aufrufe ("n ist einstellig/eine Ziffer"). Der otherwise-Zweig berechnet die letzte Ziffer von mehrstelligen n und addiert diese zum Ergebnis des rekursiven Aufrufs, in welchem der "kleinere" Fall qs (n ohne der letzten Ziffer), berechnet wird. Die Fehlerbehandlung ist verschleiernd da das valide Argument 0 auch zum Wert 0 führt.

Extra Info: Statt div und mod könnte man hier auch die leicht unterschiedlichen Funktionen quot und rem [2] verwenden.

3) Es handelt sich um 'Lineare Rekursion'. Per Definition: "Pro Zweig höchstens ein rekursiver Aufruf, davon mindestens einmal nicht als äußerste Operation." (im rekursiven Zweig ist "+" die äußerste Operation).

Aufgabe 2 ((8+4)+(4+2)+2 = 20 Punkte)

1)

 qs :: Int -> Int
 qs n = sum ziffern_von_n
   where ziffern_von_n = [ z | i <- [0..((zz n) - 1)], let z = lastDigit $ n `div` (10^i)]
         zz :: Int -> Int
         zz m
           | m < 0      = 0
           | m < 10     = 1
           | otherwise  = 1 + zz (m `div` 10)

Die verschleiernde Fehlerbehandlung kommt dadurch zustande kommen, dass sum [0..(-1)] = sum [] = 0 gilt. Sie ist nach der selben Logik verschleiernd wie in Aufgabe 1.

Alternative Schreibweise:

qs :: Int -> Int
qs n = sum ziffern_von_n
  where ziffern_von_n = [ (n `div` (10^i)) `mod` 10 |  i <- [0..((zz n) - 1)] ]

zz :: Int -> Int
zz m
    | m < 0      = 0
    | m < 10     = 1
    | otherwise  = 1 + zz (m `div` 10)

2) qs: [0..((zz n) - 1)] konstruiert die Liste der Zahlen "0 bis (#Ziffern von n) - 1". Für jedes dieser i's wird mittels skalieren von n die "i-te Ziffer" berechnet (Hier könnte leicht ein off-by-one Fehler oder ähnliches reinkriechen). Genau genommen werden die Ziffern "von rechts nach links" konstruiert - also für n = 147 etwa [7, 4, 1].

zz: Funktionert nach dem selben Schema wie qs aus Aufgabe 1, nur dass die Ziffern_anzahl_ inkrementiert wird, statt die tatsächlichen Ziffern zu addieren.

3) [0, 4, 0, 6, 5, 1]. Begründung siehe oben.

Aufgabe 3 (2+(3+3)+(1+1) = 10 Punkte)

1)

 data PeanoN = Null | Nf PeanoN

2)

 instance Eq PeanoN where
   (==) Null Null = True
   (==) Null _    = False
   (==) _    Null = False
   (==) (Nf n1) (Nf n2) = n1 == n2
  
 instance Ord PeanoN where
   (<=) Null Null = True
   (<=) Null _    = True
   (<=) _    Null = False
   (<=) (Nf n1) (Nf n2) = n1 <= n2

3) Tatsächlich ja: Bei Eq ist das vielleicht offensichtlicher: beim automatisch abgeleiteten (==) wird die Struktur der beiden Argumente ("Schicht für Schicht"/"Konstruktor für Konstruktor") gecheckt - stimmt die Struktur genau überein, sind sie gleich. Bei Ord ist es trickier: da ist zusätzlich die Reihenfolge der Konstruktoren bei der data-Deklaration relevant. Z.B. wird data Day = Mo | Tu | We | ... als Mo < Tu < We < ... interpretiert. Definiert man PeanoN wie oben, ergibt sich dadurch die korrekte Semantik. Würde man die Konstruktorreihenfolge aber vertauschen (data PeanoN = Nf PeanoN | Null), würde die automatische Ableitung schief gehen.

Aufgabe 4 (4+4+9+1 = 18 Punkte)

1. siehe [3]

 ((((((\f p x y -> (if ((p x) y) then ((f x) + (succ y)) else ((f (pred y)) - x))) (\z -> (z+1))) (\q r -> (q < r))) (2+(3*5))) 5) - 3)

Aufgabe 5 ((0.5+0.5)+5+4 = 10 Punkte)

1)

-- a)
sieger [Schere,Stein,Schere,Papier] [Papier,Papier,Papier,Papier] ->> Sieger_ist Alice

-- b)
sieger [Stein,Schere,Papier] [Stein,Papier,Schere] ->> Unentschieden

2)

 data Schere_Stein_Papier = Schere | Stein | Papier
 data Kind = Alice | Bob
 type Spielzuege_Alice = [Schere_Stein_Papier]
 type Spielzuege_Bob = [Schere_Stein_Papier]
 data Sieger = Sieger_ist Kind | Unentschieden

3)

Die Wahl ist eindeutig, weil newtype genau einen Konstruktor verlangen würde.

Aufgabe 6 ((10+4)+6+3 = 23 Punkte)

  data Schere_Stein_Papier = Schere | Stein | Papier
  data Kind = Alice | Bob deriving (Show)
  type Spielzuege_Alice = [Schere_Stein_Papier]
  type Spielzuege_Bob = [Schere_Stein_Papier]
  data Sieger = Sieger_ist Kind | Unentschieden deriving (Show)
  
  gewinn :: Schere_Stein_Papier -> Schere_Stein_Papier -> Int
  gewinn Schere Papier = 1
  gewinn Schere Stein = -1
  
  gewinn Stein Schere = 1
  gewinn Stein Papier = -1
  
  gewinn Papier Stein = 1
  gewinn Papier Schere = -1
  
  gewinn _ _ = 0
  
  acc :: Spielzuege_Alice -> Spielzuege_Bob -> Int
  acc (a:ax) (b:bx) = (gewinn a b) + (acc ax bx)
  acc _ _ = 0
  
  sieger :: Spielzuege_Alice -> Spielzuege_Bob -> Sieger
  sieger a b
    | (acc a b) > 0 = Sieger_ist Alice
    | (acc a b) < 0 = Sieger_ist Bob
    | otherwise = Unentschieden