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

Aufgabe 1

1. Zwei Nat-Werte $m$ und $n$ sind gleich gdw. die Anzahl der Succ vor Null gleich ist.

2. Ein Nat-Wert $m$ ist echt größer als ein Nat-Wert $n$ gdw. die Anzahl der Succ vor Null größer ist.

Aufgabe 2

module Prüfung where
import Data.List

data Nat = Null | Succ Nat deriving (Eq,Ord)

plus :: Nat -> Nat -> Nat 
plus Null y = y 
plus (Succ x) y = Succ (plus x y) -- recursively adds succs from x to y

minus :: Nat -> Nat -> Nat 
minus x y
 | x < y = Null
 | x == y = Null

minus (Succ x) (Succ y) = minus x y -- recursively removes succs
minus x (Null) = x

mal :: Nat -> Nat -> Nat 
mal (Succ x) y = (plus y (mal x y)) -- recursively adds y for x times
mal (Null) y = Null

type Quotient = Nat 
type Rest = Nat 
data QR = QR Quotient Rest deriving Show

durch :: Nat -> Nat -> QR 
durch x (Null) = error "division by Zero" 
durch x y
 | x < y = QR Null x 
 | x == y = QR (Succ Null) Null 
durch x y = (plusQR (QR (Succ Null) Null) (durch (minus x y) y)) 
-- checks if x bigger then y and adds 1 to quotient result. In case x smaller, returns x as rest

plusQR :: QR -> QR -> QR 
plusQR (QR x y) (QR z f) = QR (plus x z) (plus y f) --helper function to sum results

Aufgabe 3

1. Es gibt keine Werte die nicht als Resultat vorkommen könnten. Daher wäre jeder Rückgabewert außer einem Programmabbruch verschleiernd.

2. Da der Ergebnistyp geändert werden darf, könnte ein Wert hinzugefügt werden, der bei normaler Ausführung nicht benötigt wird.

Aufgabe 4

instance Show Nat where
  show (Succ (Succ (Succ (Succ (Succ (Succ x)))))) = "++++ " ++ show (Succ x)
  show (Succ (Succ (Succ (Succ (Succ Null))))) = "++++"
  show (Succ x) = "|" ++ show x
  show (Null) = ""

Wenn mehr als 5 Succ dann ++++ mit Space
Wenn genau 5 Succ dann ++++
Wenn mindestens ein Succ dann |
Wenn null dann fertig ... das ganze rekursiv

Andere Meinung: Der Fall show Null ist hier nicht abgedeckt. Dazu würde es dann eine Abänderung an der Logik brauchen. Ich habe das ganze so implementiert:

instance Show Nat where
  show Null = "Null"
  show (Succ (Succ (Succ (Succ (Succ Null))))) = "++++"
  show (Succ (Succ (Succ (Succ (Succ a))))) = "++++ " ++ show a
  show (Succ Null) = "|"
  show (Succ x) = "|" ++ show x

Aufgabe 5

--f :: (Integer, Integer) -> Integer

fhelp :: Integer -> Integer -> Integer -> Integer 
fhelp z zs current
 | current <= z || (z <= 0) && (current <= (z*(-1))) = (current ^ zs) + (fhelp z zs (current +1))
 | otherwise = 0

fmap :: Integer -> Integer -> Integer 
fmap x y
 | x<=0 = sum (map (^y) [0..(x*(-1))])
 | otherwise = sum (map (^y) [0..x])


ffold :: Integer -> Integer -> Integer 
ffold x y
 | x<=0 = foldl (+) 0 (map (^y) [0..(x*(-1))])
 | otherwise = foldl (+) 0 (map (^y) [0..x])

Anderer Lösungsvorschlag

-- mit direkt rekursiver Hilfsfunktion helper
f_1 :: (Integer, Integer) -> Integer
f_1 (x, y) = helper [0..(abs x)] (abs y)

helper :: [Integer] -> Integer -> Integer
helper [] _ = 0
helper (l:ls) y = l^y + helper ls y

-- Listenkomprehension und sum
f_2 :: (Integer, Integer) -> Integer
f_2 (x,y) = sum [z^(abs y) | z <- [0..(abs x)]]

-- Listenkomprehension und fold
f_3 :: (Integer, Integer) -> Integer
f_3 (x,y) = foldl (+) 0 [z^(abs y) | z <- [0..(abs x)]]

Aufgabe 6

Allgemeinster Typ von k:

k :: ((a,b,c) -> d) -> a -> b -> c -> d

1. Klammerungen

-- a
k :: ((a,b,c) -> d) -> a -> b -> c -> d

-- b
k :: (((a,b,c) -> d) -> (a -> (b -> (c -> d))))

2. Der allgemeinste Typ ist paramterisch / echt / uneingeschränkt polymorph.

3.

-- (i)
(f(x,y,z))

-- (ii)
((((k f) x) y) z)

4. $\underbrace {\underbrace {f} _{::(a,b,c)\to d}\underbrace {(\underbrace {x} _{::a},\underbrace {y} _{::b},\underbrace {z} _{::c})} } _{d}$

5.

k (\(x,y,z) -> x*y+z) (2+3) (3*5) (7-5)

-- linksnormal (Argumente unausgewertet übergeben)

(E) ->> (2+3)*(3*5)+(7-5)
(S) ->> 5*(3*5)+(7-5)
(S) ->> 5*15+(7-5)
(S) ->> 75+(7-5)
(S) ->> 75+2
(S) ->> 77

-- linksapplikativ (Argumente ausrechnen und dann expandieren)

(S) ->> (\(x,y,z) -> x*y+z) 5 (3*5) (7-5)
(S) ->> (\(x,y,z) -> x*y+z) 5 15 (7-5)
(S) ->> (\(x,y,z) -> x*y+z) 5 15 2
(E) ->> 5*15+2
(S) ->> 75+2
(S) ->> 77

6.

k ist eine Funktion die eine Funktion und ihre Parameter erhält und die übergebenen Parameter in ein Tupel zusammenfasst. Somit ist sie ähnlich zur Funktion curry (lediglich mit mehr Parametern) siehe Vergleich der Typsignaturen:

Prelude> :t k
k :: ((a, b, c) -> d) -> a -> b -> c -> d

Prelude> :t curry
curry :: ((a,b) -> c) -> a -> b -> c