program编程设计代做、代写Java，c++程序、Python编程代做

日期：2021-07-21 11:36

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.