program编程设计辅导、辅导Java，c++程序、Python编程辅导
辅导留学生 Statis
Blatt 0
Ludwig-Maximilians-Universität München 3. Juli 2021
Institut für Informatik
Programmierung und Modellierung in Haskell,
SoSe 21
Probe-Prüfung
Organisatorische Hinweise:
1) Prüfungsaufgaben ausarbeiten
Die Aufgaben müssen auf der Online-Plattform GATE https://gate.ifi.lmu.de/ ausgearbeitet
werden.
Nur die auf GATE eingetragenen Lösungen werden korrigiert. Sonstige Dokumente (wie Notizen
auf dem Prüfungsheft, Bilddateien, oder Umwandlungen des Prüfungsheftes als Word- oder PDFDokument)
werden nicht korrigiert.
2) Unterschrift üben und abgeben
Die Semestral- und Nachprüfung wird nur von den Studierenden korrigiert und benotet, die eine
Eigenständigkeitserklärung abgeben. Dieser Vorgang kann in der Probe-Prüfung mit Hilfe eines
Unterschriften-Übungsblattes geübt werden. Die Vorlage dazu befindet sich auf Uni2work https://
uni2work.ifi.lmu.de/ und muss bis spätestens 23:59 Uhr des Probe-Prüfungstages auf Uni2work
unterzeichnet als PDF-Datei hochgeladen werden.
3) Entwerten
Sie können Ihr Prüfungsheft entwerten, sodass Sie keine Note bekommen, indem Sie die entsprechend
bezeichnete Aufgabe in GATE bearbeiten und Ihre Entscheidung durch Auswahl der Option “Ich
beantrage, dass mein Prüfungsheft ”entwertet”, d. h. nicht korrigiert und nicht benotet, wird.”
entsprechend kundtun.
4) Hilfsmittel
Hilfsmittel sind nicht nötig, können sogar hinderlich sein und sollten nicht verwendet werden. Es
ist jedoch sinnvoll, einen Haskell-Editor und einen Haskell-Übersetzer (wie den Glasgow Haskell
Compiler ghc) zu verwenden.
Viel Erfolg!
© 2021 Die Mitarbeiter der Lehr- und Forschungseinheit PMS, IfI. Alle Rechte vorbehalten.
Veröffentlichung und Vervielfältigung, auch auszugsweise, nur mit Genehmigung der Urheber.
Programmierung und Modellierung in Haskell, Probe-Prüfung, 3. Juli 2021 Blatt 1
Aufgabe 1 Typsignaturen (1+1+1 Punkte)
a) Geben Sie in Haskell-Notation einen Lambda-Ausdruck an, der den Typ
(b -> c) -> (a -> b) -> a -> c
hat. Benutzen Sie nicht den Operator (.) zur Funktionskomposition.
\f g x -> ( )
b) Geben Sie die Haskell-Typsignatur einer beliebigen einstelligen Funktion p mit polymorphem Typ
an. Verwenden Sie dabei ausschließlich den polymorphen Typ a.
p ::
c) Geben Sie die Haskell-Typsignatur einer beliebigen Funktion u in uncurried Form an, deren curried
Form die drei Argumente a, b und c und das erste Element als Rückgabewert hat.
u :: ( ) -> c
© 2021 Die Mitarbeiter der Lehr- und Forschungseinheit PMS, IfI. Alle Rechte vorbehalten.
Veröffentlichung und Vervielfältigung, auch auszugsweise, nur mit Genehmigung der Urheber.
Programmierung und Modellierung in Haskell, Probe-Prüfung, 3. Juli 2021 Blatt 2
Aufgabe 2 Rekursion (1+1+1 Punkte)
Das innere Produkt zweier Vektoren ~x, ~y ist definiert als
Xn
i=1
xi
· yi
.
Ein Vektor soll in Haskell durch eine nicht-leere endliche Liste repräsentiert werden.
a) Schreiben Sie eine rekursive, aber nicht endrekursive Haskell-Funktion
iprod :: Num a =>[a] -> [a] -> a
die das innere Produkt zweier Vektoren ausgibt. Dabei soll bei unterschiedlicher Länge der Vektoren
der kürzere Vektor so behandelt werden, als wären seine fehlenden Werte gleich null. Verwenden Sie
dafür von den Listenfunktionen nur den Listenkonstruktor (:); head und tail sind nicht erlaubt.
iprod :: Num a => [a] -> [a] -> a
iprod xs [] =
iprod [] ys =
iprod ( ) ( ) = * + iprod
b) Geben Sie eine endrekursive Haskell-Funktion iprod' an, die sich wie iprod verhält. Sie dürfen
dafür die Listenfunktionen (:), null, head und tail verwenden.
iprod ' :: Num a => [a] -> [a] -> a
iprod ' xs ys = ip xs ys
where ip xs ys akk =
if xs || null
then
else ip ( ) ( ) akk +( )*( )
c) Realisieren Sie unter Verwendung der Listenfunktionen zip und entweder foldl oder foldr einen
Lambda-Ausdruck in Haskell-Notation, den Sie iprod'' nennen und der sich sich wie iprod und
iprod' verhält.
iprod '' :: Num a => [a] -> [a] -> a
iprod '' = \xs ys -> (\(a, b) r -> r + * )
0 (zip )
© 2021 Die Mitarbeiter der Lehr- und Forschungseinheit PMS, IfI. Alle Rechte vorbehalten.
Veröffentlichung und Vervielfältigung, auch auszugsweise, nur mit Genehmigung der Urheber.
Programmierung und Modellierung in Haskell, Probe-Prüfung, 3. Juli 2021 Blatt 3
Aufgabe 3 Auswertung (1+1+1 Punkte)
a) Gegeben seien die Haskell-Definitionen
index = \n -> -4
f = \n -> if n<0 then n*n else sqrt n
und folgende Haskell-Ausdrücke:
index (f (f (index 0)))
index (f (f ((\n -> -4) 0)))
• Ist dieser Auswertungsschritt korrekt für die applikative Auswertungsreihenfolge?
Ja Nein
• Ist dieser Auswertungsschritt korrekt für die normale Auswertungsreihenfolge?
Ja Nein
b) Gegeben seien die folgenden Haskell-Definitionen:
index = \n -> -4
f = \n -> if n<0 then n*n else sqrt n
Der Ausdruck index (f (f (index 0))) soll in normaler Auswertungsreihenfolge ausgewertet
werden. Kreuzen Sie bitte in der folgenden Liste die Antwort an, deren Ausdruck entsprechend
dieser Reihenfolge unmittelbar auf den gegebenen Ausdruck folgt:
1. index (f (f ((\n -> (-4)) 0)))
2. (-4)
3. (\n -> (-4)) (f (f (index 0)))
4. (\n -> (-4)) (f (f (-4)))
5. Keine der obigen Möglichkeiten, korrekt ist:
c) Gegeben sei folgende Haskell-Definition:
wurzel = \x -> sqrt x
Ergänzen Sie den folgenden Auswertungsschritt entsprechend der verzögerten Auswertungsreihenfolge.
(\n -> if n<0 then n*n else wurzel n) a
if then else
© 2021 Die Mitarbeiter der Lehr- und Forschungseinheit PMS, IfI. Alle Rechte vorbehalten.
Veröffentlichung und Vervielfältigung, auch auszugsweise, nur mit Genehmigung der Urheber.
Programmierung und Modellierung in Haskell, Probe-Prüfung, 3. Juli 2021 Blatt 4
Aufgabe 4 Binärbäume (1+2 Punkte)
Gegeben sei die folgende Definition des polymorphen Datentyps BB:
data BB a = L | K (BB a) a (BB a)
wobei BB für Binärbaum, L für leerer Baum und K für Knoten steht.
a) Formulieren Sie einen Haskell-Wert w dieses Typs BB, sodass der Prefix-Tiefendurchlauf des Baumes
folgende Werteliste ergibt: ["/=","*","2","3","5"]. Die Listenelemente sind bezüglich ihrer Stelligkeit
als Haskell-Syntaxelemente zu verstehen, d.h. die Zeichenkette "/=" ist als Ungleich-Operator
zu verstehen und hat damit die Stelligkeit 2.
w = K (K (K L " " L) " " (K L " " L))
" " (K "5" L)
b) Geben Sie die Werteliste l für den Infix-Tiefendurchlauf an, und werten Sie den damit repräsentierten
Ausdruck nach Haskell-Regeln aus.
l = [" ", " ", "3", " ", " "]
Auswertung:
© 2021 Die Mitarbeiter der Lehr- und Forschungseinheit PMS, IfI. Alle Rechte vorbehalten.
Veröffentlichung und Vervielfältigung, auch auszugsweise, nur mit Genehmigung der Urheber.
Programmierung und Modellierung in Haskell, Probe-Prüfung, 3. Juli 2021 Blatt 5
Aufgabe 5 Polymorphie (1+1+1 Punkte)
Gegeben sei die folgende (zu Aufgabe 4 identische) Definition des polymorphen Datentyps BB:
data BB a = L | K (BB a) a (BB a)
wobei BB für Binärbaum, L für leerer Baum und K für Knoten steht.
a) Realisieren Sie eine Haskell-Funktion mit der folgenden Typsignatur, die den Baum vom Typ BB
von rechts nach links mit dem angegebenen zweistelligen Operator auf einen Wert reduziert. Dabei
soll die Infix-Notation verwendet werden, das heisst der Lambda-Ausdruck
(\x xs -> concat ["(", show x, xs, ")"]) und der Baum K (K L 2 L) 1 (K (K L 4 L) 3 L)
angewendet auf foldrBB soll den Wert "(2(1(4(3))))" ergeben.
foldrBB :: (a -> b -> b) -> b -> BB a -> b
foldrBB f b = b
foldrBB f b ( l a r) =
f (f (foldrBB ))
b) Geben Sie die notwendigen Haskell-Definitionen, um aus dem Typ BB unter Verwendung der Funktion
foldrBB einen Typ der Typklasse Foldable zu schaffen. In jeder Lücke darf nur ein Bezeichner
wie zum Beispiel BB, Foldable, foldrBB usw. stehen.
instance where
=
c) Vervollständigen Sie das untenstehende Haskell-Codefragment, welches die Summe der im Binärbaum
b = K (K L 2 L) 1 (K (K L 4 L) 3 L) enthaltenen Zahlen berechnet.
summiere :: Foldable t => t Int -> Int
summiere = (+) 0
sumBB :: Int
sumBB = let b = K (K L 2 L) 1 (K (K L 4 L) 3 L) in summiere b
© 2021 Die Mitarbeiter der Lehr- und Forschungseinheit PMS, IfI. Alle Rechte vorbehalten.
Veröffentlichung und Vervielfältigung, auch auszugsweise, nur mit Genehmigung der Urheber.
Programmierung und Modellierung in Haskell, Probe-Prüfung, 3. Juli 2021 Blatt 6
Aufgabe 6 Datentypen (1+1+1 Punkte)
Eine einfach verkettete Liste wird repräsentiert durch eine Menge von Knoten, die jeweils ein Element
von einem nicht näher spezifizierten Typ a speichern sowie einen weiteren Knoten der Liste. Eine Liste
oder ein Teil davon kann auch leer sein, und wird dann durch einen Sentinel (spezieller Knoten ohne
Datenelemente) repräsentiert.
a) Definieren Sie in Haskell einen rekursiven Datentyp LinkedList mit den Konstruktoren ListElem
und ListSentinel. Verwenden Sie dafür keine eingebauten Datentypen wie Liste, Tupel oder ähnliches.
data LinkedList = ListElem ( a)
| ;
b) Definieren Sie eine Haskell-Funktion listToLL :: [a] -> LinkedList a, die eine Liste von Elementen
des Typs a in die Datenstruktur LinkedList überführt.
listToLL :: [a] -> LinkedList a
listToLL = ListSentinel
listToLL ( :xs) = x ( )
c) Erstellen Sie eine Haskell-Funktion
showLL :: Show a => LinkedList a -> String
mit der der Inhalt einer LinkedList ausgegeben werden kann. Zwischen den Elementen der LinkedList
wird als Trennelement die Zeichenkette ">>>" (ohne Anführungszeichen) eingefügt. Achten Sie
darauf, dass bei der Ausgabe die Trennelemente nur zwischen den Elementen vorkommen und nicht
vor bzw. nach den Randelementen auftreten. Beispielsweise ist das Ergebnis des Funktionsaufrufes
showLL (listToLL [1..8]) die Zeichenkette "1>>>2>>>3>>>4>>>5>>>6>>>7>>>8".
showLL :: Show a => LinkedList a -> String
showLL = ""
showLL (ListElem ) = show a
showLL (ListElem ) = concat [ a, ">>>", rest]
© 2021 Die Mitarbeiter der Lehr- und Forschungseinheit PMS, IfI. Alle Rechte vorbehalten.
Veröffentlichung und Vervielfältigung, auch auszugsweise, nur mit Genehmigung der Urheber.
Programmierung und Modellierung in Haskell, Probe-Prüfung, 3. Juli 2021 Blatt 7
Aufgabe 7 Typklassen (1+1+1 Punkte)
Gegeben seien die folgenden Typsignaturen.
append2 :: ( Applicative f, Monoid (f a)) => f a -> f a -> f a
append2 x m = ...
twice :: (Foldable t, Applicative t, Monoid (t a)) => t a -> t a
twice ls = ...
a) Vervollständigen Sie die Haskell-Funktion append2, sodass der monoidale Wert x zweimal von links
mit dem monoidalen Wert m verknüpft wird. Wenn beispielsweise der applikative Funktor f die
Liste ist, so soll append2 [1] [2] den Wert [1, 1, 2] ergeben.
Nehmen Sie keine weiteren Funktionen an außer jenen, die durch die angegebenen Typklassen
definiert sind. Verwenden Sie keine zusätzlichen Hilfsfunktionen und lediglich explizite Parameter.
append2 :: ( Applicative f, Monoid (f a)) => f a -> f a -> f a
append2 x m = x ` ` ` ` m
b) Unter der Verwendung der Funktion append2 vervollständigen Sie die Haskell-Funktion twice,
sodass alle Werte im faltbaren, applikativen Funktor t verdoppelt werden. Beispielsweise ergibt
twice [1, 2, 3] den Wert [1, 1, 2, 2, 3, 3]. Formulieren Sie Hilfsfunktionen als LambdaAusdrücke
mit ausschließlich expliziten Parametern.
twice :: (Foldable t, Applicative t, Monoid (t a)) => t a -> t a
twice ls = (\l r -> append2 ( l) ) ls
c) Unter Verwendung der Funktion append2 und (.) formulieren Sie die Funktion twice als HaskellFunktion
höherer Ordnung ohne explizite Parameter. Verwenden Sie auch keine expliziten Parameter
in Lambda-Ausdrücken.
twice :: (Foldable t, Applicative t, Monoid (t a)) => t a -> t a
twice = ( . pure)
© 2021 Die Mitarbeiter der Lehr- und Forschungseinheit PMS, IfI. Alle Rechte vorbehalten.
Veröffentlichung und Vervielfältigung, auch auszugsweise, nur mit Genehmigung der Urheber.
Programmierung und Modellierung in Haskell, Probe-Prüfung, 3. Juli 2021 Blatt 8
Aufgabe 8 Monaden (1+1+1 Punkte)
Gegeben sei das folgende Haskell-Codefragment.
data Expr = Num Double
| Add Expr Expr
| Sub Expr Expr deriving Show
eval :: Expr -> Maybe Double
eval (Num a) = if a<0 then Nothing else Just a
eval (Add a b) = case eval a of
Nothing -> Nothing
Just a' -> case eval b of
Nothing -> Nothing
Just b' -> Just (a' + b')
a) Formulieren Sie diesen Haskell-Code mit monadischen do-Blöcken. Nennen Sie diese Funktion
evalDo.
evalDo :: Expr -> Maybe Double
evalDo (Num a) = if a<0 then Nothing else return a
evalDo (Add a b) =
<-
<-
return (a'+b')
b) Formulieren Sie obigen Haskell-Code als monadische Ausdrücke unter Verwendung der Funktionen
return und bind (>>=) anstelle der do-Notation. Nennen Sie diese Funktion evalBd. Verwenden
Sie zur Ausformulierung von evalBd nicht die Funktion evalDo.
evalBd :: Expr -> Maybe Double
evalBd (Num a) = if a<0 then Nothing else return a
evalBd (Add a b) = a >>= ->
>>= \b' -> (a' + )
c) Formulieren Sie eine Haskell-Regel mit return und bind (>>=), die es ermöglicht, zwei Ausdrücke
voneinander zu subtrahieren. Dabei soll der entstehende Ausdruck nie kleiner als null werden.
So ergibt zum Beispiel evalBd (Num 7 `Sub` Num 5) den Wert Just 2.0, die Auswertung von
evalBd (Num 2 `Sub` Num 3) jedoch Nothing.
evalBd :: Expr -> Maybe Double
evalBd (Sub a b) =
>>= \a' ->
>>= \b' -> if a'-b'<0
then
else return ( )
© 2021 Die Mitarbeiter der Lehr- und Forschungseinheit PMS, IfI. Alle Rechte vorbehalten.
Veröffentlichung und Vervielfältigung, auch auszugsweise, nur mit Genehmigung der Urheber.