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

Lösungsvorschlag 1

Aufgabe 1 (2*0.5+10+14 = 15 Punkte)

1.1:

a) E 7 (E 9 (E 9 Ende))

b) E "Viel" (E "Er" (E "Folg" (E "!" Ende)))

1.2:

streiche :: Ord a => (Liste a) -> (Liste a) -> (Liste a)
streiche Ende _ = Ende
streiche (E x xs) ys = if x `myelem` ys 
    then streiche xs ys else E x (streiche xs ys)


myelem :: Ord a => a -> (Liste a) -> Bool
myelem _ Ende = False
myelem x (E y ys) = if x == y then True else myelem x ys

1.3:

Die Funktion streiche checkt jedes Element der ersten Liste und überprüft ob es in der zweiten Liste vorkommt. Dies geschieht mittels der myelem Funktion. Befindet sich das Element nicht in der zweiten Liste wird es an das Ergebnis gehängt und der Tail der Liste wird weiter rekursiv untersucht.

Aufgabe 2 (2+2+6+2+2+5 = 19 Punkte)

2.1: Summentyp: Mindestens zwei Konstruktoren, mindestens ein nicht nullstelliger Konstruktor. Konstruktoren sind Ende und E, wobei E nicht nullstellig, sondern einstellig ist.

2.2: E 4 (E 2 (E 0 (E 3 (E 2 ( E 4 Ende))))) würde in infix folgendermasen ausschauen: 4 `E` ( 2 `E` ( 0 `E` ( 3 `E` ( 2 `E` ( 4 `E` Ende)))))

2.3: die deriving Klauseln führt Haskell vollautomatisch aus, mittels instance Eq... kann man dies selbst manuell übernehmen.

data Liste a = Ende | E a (Liste a) deriving (Eq,Ord,Show) --Variante 1 mit deriving / vollautomatisch

-- Variante 2 - manuell
instance Eq Liste where
    (==) Ende Ende = True
    (==) (E x xs) (E y ys) = x == y && xs == ys
    (==) _ _ = False

instance Ord Liste where
    (<=) Ende Ende = True
    (<=) Ende _ = True
    (<=) _ Ende = False
    (<=) (E x xs) (E y ys) = x <= y && xs <= ys

instance Show Liste where
    show Ende = "Ende"
    show (E x xs) = show x ++ " " ++ show xs

2.4:

• Ende :: Liste a
• E :: a -> Liste a -> Liste a

2.5: ad-hoc polymorph: Eine Funktion in Haskell heißt ad hoc polymorph (oder unecht polymorph oder überladen), wenn die Typen eines oder mehrerer ihrer Parameter angegeben durch Typvariablen durch Typkontexte eingeschr ̈ankt Werte aller durch den Typkontext zugelassenen Typen als Argument zulassen.

2.6: Der Hauptleitsatz fordert, Funktionen, Datentypen stets so allgemein wie möglich zu halten, sie nicht mehr als nötig einzuschränken, nicht mehr als für fehlerfreie Auswertung erforderlich ist.

Aufgabe 3 (6+(1+3)+5 = 15 Punkte)

Versuch 1:

3.1:

data OuterNode = O Int String 
data InnerNode = I Int ((Int, Int) -> Bool)
data Baum = OuterNode | Baum InnerNode Baum

3.2:

a) O 3 "Fun"
b) (O 6 "Haskell" (I 42 \(x,y) -> mod x 42 == y)(O 6 "Brooks" (I 17 \(x,y) -> x>y) O 5 "Curry"))

3.3: Hätte gesagt ja. Angabe fordert Int's und Funktionen (Int, Int) -> Bool. Somit ist der Baum so allgemein wie möglich gewählt und genügt somit dem Hauptleitsatz der funktionalen Programmierung

Versuch 2:

3.1 Bin mir unsicher ob die obere Antwort stimmt, zumindest hat es bei mir nicht funktioniert

data Baum = B Int String | K Baum Int ((Int, Int) -> Bool) Baum

3.2 (Versuch 2)

(K (B  "Haskell") 42 (\(x,y) -> mod x 42 == y) (K (B 6 "Brooks") 17 (\(x,y)-> x > y)(B 5 "Curry")))

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

4.1: Die Erstellung eines formalen Berechnungsmodelles, welches zeigt was alles berechenbar ist.

4.2: Ja. Das Lamdakalkül ist die Basis aller funtkionalen Programmeirsprachen und Turing-Mächtig.

4.3: Basis aller Funktionalen Programmiersprachen.

Aufgabe 5 (5+5+5 = 15 Punkte)

5.1: Falsch: type-Deklarationen dienen der besseren Lesbarkeit. Sie sind Aliase für primitive Typen

5.2: Falsch: Nicht jeder λ-Ausdruck kann in eine Normalform überführt werden.

5.3: Falsch: f wird eine Funktion übergeben und G stattdessen zwei Parameter, somit müssen die Implementierungen der beiden auch verschieden sein. (Not sure tbh)

Aufgabe 6 (12+6 = 18 Punkte)

6.1: Implementierung:

type Nat1 = Int
type Euro = Nat1
type Preis = Euro

data Artikel = A1 | A2 | A3 | A4 | A5 deriving (Eq, Show)
type Warenkatalog = (Artikel -> Preis)

data Händler = H1 | H2 | H3 deriving (Eq, Show)
type Markt = (Händler -> Warenkatalog)

type Bestbieter = (Artikel -> (Artikel, Händler, Preis))

g :: Markt -> Bestbieter 
g m a = (a, h, p) where
    h = head [h | h <- [H1, H2, H3], (m h) a == p]
    p = minimum [p | p <- [m H1 a, m H2 a, m H3 a]]


-- Beispielmarkt:

markt1 :: Markt
markt1 H1 = \a -> case a of
    A1 -> 1
    A2 -> 2
    A3 -> 3
    A4 -> 4
    A5 -> 0 -- cheapest 
markt1 H2 = \a -> case a of
    A1 -> 2
    A2 -> 3
    A3 -> 4
    A4 -> 5
    A5 -> 6
markt1 H3 = \a -> case a of
    A1 -> 3
    A2 -> 4
    A3 -> 5
    A4 -> 6
    A5 -> 7

-- Testaufruf: g markt1 A1

--Alternativlösung mit anonymer Funktion:

g' :: Markt -> Bestbieter
g' m = \a -> (a, h, p) where
        h = head [h | h <- [H1, H2, H3], (m h) a == p]
        p = minimum [p | p <- [m H1 a, m H2 a, m H3 a]]

-- where klauseln sind in lambda funktionen nicht gestattet, stattdessen kann man let verwenden
g :: Markt -> Bestbieter 
g m = \x ->
    let h = head [h | h <- [H1, H2, H3], (m h) x == p]
        p = minimum [p | p <- [m H1 x, m H2 x, m H3 x]]
    in (x, h, p)

1.3: Kurz und Knackig wird hier die sogenannte listenkomprehension von haskell verwendet um eine funktion zu generieren, die einen Artikel nimmt und das Bestpreis Tripel ausspuckt.

liebe grüße an die haskell homies <3

\(^^)/

Lösungsvorschlag von Simplex

Aufgabe 1 (2*0.5+10+14 = 15 Punkte)

1. Welches Ergebnis liefern die Aufrufe von (a) und (b)? (a): E 7 (E 9 (E 9 Ende)) (b): E "Viel" (E "Er" (E "Folg" (E "!" Ende)))
2. Implementierung der Funktion:

   data Liste a = Ende | E a (Liste a) deriving (Eq,Ord,Show)
   
   streiche :: Ord a => (Liste a) -> (Liste a) -> (Liste a)
   streiche Ende _ = Ende
   streiche list1@(E el1 l1) list2@(E el2 l2)
       | not (pruefeListe el1 list2) = (E el1 (streiche l1 list2))
       | otherwise                   = streiche l1 list2
   
   pruefeListe :: Ord a => a -> (Liste a) -> Bool
   pruefeListe el (Ende) = False
   pruefeListe el (E lel l)
       | el == lel = True
       | otherwise = pruefeListe el l
   

3. Die Funktion streicht prüft jedes Element der ersten Liste list1 mit allen Elementen aus der zweiten Liste list2. Hierfür wurde die Funktion pruefeListe erzeugt, welche das übergebene Element el mit allen Elementen der Liste (zweiter Parameter) überprüft. Sollte das einzelne Element mit dem head-Element der übergebenen Liste übereinstimmen, so gibt die Funktion True zurück, ansonsten wird am Ende der Rekursion Falsezurückgegeben.

Aufgabe 2 (2+2+6+2+2+5 = 19 Punkte)

Gegeben sind die Deklarationen von Liste a und streiche aus Aufgabe 1.

1. Von welcher Variante eines algebraischen Typs ist Liste a? Geben Sie sie an und begründen Sie Ihre Antwort.
   • Summentyp: Es handelt sich hier um einen (echten) rekursiven Summentyp, da der Datentyp die Voraussetzungen (min. zwei Konstruktoren, mindestens ein nicht nullstelliger Konstruktor) erfüllt. Die Konstruktoren sind:
     • Ende: nullstellig
     • E: einstellig
2. Welche Darstellung hat der Listenwert (E 4 (E2 (E 0 (E 3 (E 2 (E 4 Ende)))))) wenn die Konstruktoren, wo das möglich ist, in Infix-Weise verwendet werden? Geben Sie die entsprechende Darstellung an.
   • 4 `E` (2 `E` (0 `E` (3 `E` (2 `E` (4 `E` Ende)))))

--Simplex 20:16, 27. Feb. 2023 (CET)

Materialien

Neues Material hinzufügen

L

• Loesungsvorschlag 2023-01-19.zip (details)