TU Wien:Funktionale Programmierung VU (Knoop)/Mögliche Prüfungsfragen WS0708

Alle Angaben ohne Gewähr, kein Anspruch auf Vollständigkeit.

Alle Fragen hier sind frei erfunden und entstammen keinem Prüfungsordner.

Welche Notationen für Funktionen sind in Haskell möglich?

• in Form "bedingter Gleichungen" (Funktionsparameter werden mit Bedingungen überprüft, untereinanderstehende "|")
• Lambda-artig (anonyme Funktionen)
• gleichungsorientiert (if-then-else)
• where/let Konstrukt
• musterbasiert

Wozu werden Wildcards in Funktionen eingesetzt?

Um für Funktionsparameter, die beliebige Werte annehmen können und auf die Berechnung der Funktion keinen Einfluss haben, keine Namen vergeben zu müssen (gute Namen sind knapp ;-)

Was bedeutet bei Funktionssignaturen in Haskell "der Typkonstruktor ist rechtsassoziativ"?

Das bedeutet, dass bei nicht vorhandenen Klammern in der Funktionssignatur Typenabbildungen von rechts nach links zu Stande kommen. (Für mich sehr schwer zu formulieren, am besten ein Beispiel geben)

Zeichnen Sie in nachfolgender Funktionssignatur die Klammern ein, die wegen der Rechtsassoziativität der Typkonstruktoren weggelassen wurden.

Angabe:

fun :: Int -> (Int -> Int -> Int) -> Int -> Int

Lösung:

fun :: (Int -> ((Int -> (Int -> Int)) -> (Int -> Int)))

Schreiben Sie folgendes Signaturschema in Worten nieder.

bla :: Int -> (Int -> Int) -> Int

bla ist eine Funktion, die ganze Zahlen auf Abbildungen ganzer Zahlen in sich auf ganze Zahlen abbildet, welche wiederum auf ganze Zahlen abgebildet werden.

Welchem der beiden Signaturschemata folgt die Funktion (*) (Multiplikation) mit ihrer gewöhnlichen Bedeutung? Begründen Sie warum!

f :: Int -> (Int -> Int)
g :: (Int -> Int) -> Int

Lösung: f, weil nicht eine Abbildung selbst auf einen Wert abgebildet wird, sondern weil zuerst ein Wert auf eine (Zwischen-) Abbildung abgebildet wird, die wiederum auf einen Ergebniswert abbildet. (Ersatzwörter für "abbilden" sind willkommen!)

Warum sind die Klammereinsparungsregelen in Funktionssignaturen für den Typkonstruktor zugunsten der Rechtsassoziativität und nicht der Linksassoziativität gefallen?

Die Anwendung einer Funktion auf ein Argument liefert wegen der Rechtsassoziativität immer wieder eine Funktion zurück, und zwar die Funktion von den restlichen Argumenten aufs Endergebnis. Funktionen mit mehreren Argumenten haben also in der Regel eher "rechtsassoziative" Typen, z.B.:

 (a -> (b -> c))

Der Fall

 ((a -> b) -> c)

ist weniger häufig, deswegen ist es natürlicher, Klammern rechtsassoziativ einzusparen.

Außerdem ist die Funktionsapplikation linksassoziativ, und das ergibt eine hübsche Dualität. Hübsche Dualitäten sind bei Theoretikern beliebt.

Betrachten Sie die Funktionssignatur der Funktion crazy und nachfolgenden Ausdruck. Welchen Typ hat der Ausdruck?

Funktion:

crazy :: String -> String -> Int -> String

Ausdruck:

crazy "Eva" "Adam"

Lösung:

crazy "Eva" "Adam" :: Int -> String

Zeichnen Sie im Ausdruck der vorhergehenden Frage die automatisch weggelassenen Klammern wie in Haskell vereinbart ein. Welcher Assoziativität folgen Funktionsterme, wenn Klammern weggelassen werden?

 ((crazy "Eva") "Adam")

Linksassoziativität.

Wann wird eine Funktion als curryfiziert bezeichnet?

Eine Funktion kann als curryfiziert klassifiziert werden, wenn die Konsumation von Argumenten nicht in Form von gebündelten Tupeln erfolgt.

Was ist der entscheidende Vorteil von curryfizierten Funktionen gegenüber uncurryfizierten?

Curryfizierte Funktionen können partiell ausgewertet werden und als Ergebnis wiederum eine Funktion liefern.

Was bedeutet Rekursion?

Eine Rechenvorschrift heißt rekursiv, wenn sie in ihrem Rumpf (direkt oder indirekt) aufgerufen wird.

In welchen zwei groben Strukturen lässt sich Rekursion betrachten?

• Mikroskopische Struktur: betrachtet einzelne Rechenvorschriften und die syntaktische Gestalt der rekursiven Aufrufe.
• Makroskopische Struktur: betrachtet Systeme von Rechenvorschriften und ihre gegenseitigen Aufrufe.

Welche Rekursionstypen in der mikroskopischen Struktur kennen Sie?

• Repetitive Rekursion (pro Zweig maximal ein rekursiver Aufruf, als äußerste Operation)
• Lineare Rekursion (wiederum pro Zweig maximal ein rekursiver Aufruf, allerdings nicht als äußerste Operation)
• Geschachtelte Rekursion (rekursive Aufrufe enthalten weitere rekursive Auffrufe als Argumente)
• Baumartige Rekursion (pro Zweig mehrere rekursive Aufrufe nebeneinander)

Was bedeutet indirekte Rekursion in der makroskopischen Struktur?

Wechselseitige Aufrufe von zwei oder mehr Funktionen.

Wie könnte die in der Vorlesung besprochene Berechnung der Fibonacci-Zahlen effizienter gestaltet werden, sodass keine/weniger Mehrfachberechnungen durchgeführt werden?

fib :: Integer -> Integer
fib n
  | n == 0   = 0
  | n == 1   = 1
  | otherwise  = fib (n-1) + fib (n-2)

Eine mögliche Lösung:

fib2 :: Integer -> Integer
fib2 n
  | n == 0    = 0
  | n == 1    = 1
  | n == 2    = 1
  | otherwise = f1 + f2
      where (f1,f2) = sumup (0,1) n 1

sumup :: (Integer,Integer) -> Integer -> Integer -> (Integer,Integer)
sumup (f1,f2) n i
  | i < (n-2)  = sumup (f2,f1+f2) n (i+1)
  | otherwise  = (f2,f1+f2)

Zeichnen Sie den Aufrufgraphen zu Ihrer Lösung aus dem vorigen Beispiel!

Ein Kreis für fib2, ein Kreis für sumup. Eine Kante von fib2 nach sumup, eine Kante von sumup im Kreis zu sich selbst zurück.

Welche drei grundlegenden Typmuster können Sie unterscheiden?

• Aufzählungstypen (endlich viele verschiedene Werte, Beispiel Jahreszeiten)
• Produkttypen (=Verbundtypen, möglicherweise unendlich viele Tupelwerte, Beispiel Person)
• Summentypen (=Vereinigungstypen, Vereinigung von unterschiedlichen Typen, Beispiel Verkehrsmittel)

Benennen Sie in folgendem Beispiel eines algebraischen Datentyps in Haskell die Komponenten, aus denen sich dieser zusammensetzt!

data Baum = Nil | Blatt Int | Stamm Baum Baum

• data: Schlüsselwort zur Einleitung eines algebraischen Datentyps
• Baum: Typname
• Nil: Konstruktor, nullstellig
• Blatt: Konstruktor, einstellig
• Stamm: Konstruktor, zweistellig
• |: Vereinigung der "Untertypen"

Wie unterscheiden sich Typsynonyme von algebraischen Datentypen in Haskell?

Typsynonyme führen nur neue Namen für bestehende Datentypen ein, können aber im Gegensatz zu algebraischen Datentypen keine neuen Datenstrukturen beschreiben, sondern dienen vor allem dem besseren Programmverständnis und der Dokumentation.

Betrachten Sie folgendes Beispiel in Haskell. Welchen Fehler erzeugt der Aufruf der Funktion rechteckFlaeche in der letzten Zeile?

type Laenge          = Float
type Breite          = Float
type Flaeche         = Float
type Geschwindigkeit = Float

rechteckFlaeche :: Laenge -> Breite -> Flaeche
rechteckFlaeche l b = l * b
l :: Laenge
l = 5
g :: Geschwindigkeit
g = 100

rechteckFlaeche l g

Lösung: Gar keinen. Da Typsynonyme keine zusätzliche Typsicherheit bringen, kann g (vom Typ Geschwindigkeit, der wiederum Float entspricht) problemlos in der Funktion rechteckFlaeche verwendet werden (dort wird mit dem Typ Breite auch nur ein Synonym für Float erwartet).

Wodurch unterscheiden sich Produkttypen von Tupeltypen?

Tupeltypen sind als Typsynonyme für Tupel aufzufassen, während Produktypen algebraische Datentypen (mit Konstruktor) sind.

Wie kennzeichnet sich parametrische Polymorphie?

Statt konkreter Typen beinhaltet eine Funktionssignatur Typvariablen (=Typparameter), die Platzhalter für beliebige Typen sind.

Warum ist parametrische Polymorphie erstrebenswert?

Weil sie einfache Wiederverwendung von Rechenvorschriften und Funktionsnamen ermöglicht, und eine Mehrfachimplementierung von gleich strukturierten Funktionen für verschiedene Typen vermieden werden kann, was in weiterer Folge auch zu einer einfacheren Wartung und höherer Effizienz beiträgt.

Wie definiert sich ein polymorpher Typ?

Ein (Daten-) Typ T heißt polymorph, wenn bei der Deklaration von T der Grundtyp oder die Grundtypen der Elemente (in Form einer oder mehrerer Typvariablen) als Parameter angegeben werden.

Was ist Ad-hoc Polymorphie?

Ad-hoc Polymorphie oder "Überladung" bezeichnet die Mehrfachimplementierung von Funktionen gleichen Namens für verschiedene Typen. Die Funktionalität der Funktionen ähnelt sich typischerweise, während die Implementierung sich aber mehr oder weniger stark unterscheidet. Im Gegensatz zur parametrischen Polymorphie wird also nicht derselbe Code für verschiedene Typen wiederverwendet.

Wie wird Ad-hoc Polymorphie in Haskell angewandt?

Mittels Typklassen, die die zu überladenden Funktionssignaturen spezifizieren, und Instanzen, die diese Funktionen für einen gewünschten Typ implementieren.

Warum können in Haskell nicht alle möglichen Typen automatsich zu Instanzen der Typklasse Eq (stellt die Vergleichsfunktion "==" bereit) gemacht werden?

Weil durch die Behandlung von Funktionen als first class citizens (also die Gleichstellung von Funktionen als Typen) die Funktion "==" auch für alle Funktionen definiert werden müsste. Dies ist aber im allgemeinen algorithmisch nicht möglich, "Gleichheit von Funktionen ist unentscheidbar".

Erzeugen Sie mittels Listenkomprehension in Haskell eine Liste, die alle Vielfachen der Zahl 7, sowie alle zweistelligen Zahlen die die Ziffer 7 beinhalten, zwischen 1 und 100 (inklusive) enthält.

[ n | n <- [1..100], (n `mod` 7 == 0) || (n `mod` 10 == 7) || ( n >= 70 && n < 80 ) ]

Anm.: Vielfache sind 7, 14, 21, etc., Zahlen die die Ziffer 7 beinhalten sind 7, 17, 27, 71, etc.

Was sind Funktionen höherer Ordnung?

Funktionen höherer Ordnung (=Funktionale) sind spezielle Funktionen, die als Parameter und/oder Resultate wiederum Funktionen erwarten bzw. liefern.

Betrachten Sie folgende Funktion. Können Sie diese unter der Zuhilfenahme von operator sections und Funktionskompositionen verkürzen?

plusDoppelt :: Int -> Int -> Int
plusDoppelt a b = a * 2 + b

Lösung:

plusDoppelt :: Int -> Int -> Int
plusDoppelt = (+) . (*2)

Welchen Typ hat im folgenden magicType?

magicType = let
            pair x y z = z x y
            f y = pair y y
            g y = f (f y)
            h y = g (g y)
            in h (\x->x)

Keine Ahnung.

Laut Hugs:

magicType :: ((((((((a -> a) -> (a -> a) -> b) -> b) -> (((a -> a) -> (a -> a) -> b) -> b) -> c) -> c) -> 
(((((a -> a) -> (a -> a) -> b) -> b) -> (((a -> a) -> (a -> a) -> b) -> b) -> c) -> c) -> d) -> d) -> 
(((((((a -> a) -> (a -> a) -> b) -> b) -> (((a -> a) -> (a -> a) -> b) -> b) -> c) -> c) -> 
(((((a -> a) -> (a -> a) -> b) -> b) -> (((a -> a) -> (a -> a) -> b) -> b) -> c) -> c) -> d) -> d) -> e) -> e

Ich glaube die Kernaussage des Beispiels (aus den Folien) ist, dass es einen Typ hat, der ermittelt werden kann.

Was bedeutet referentielle Transparenz?

Referentielle Transparenz ist dann gegeben, wenn der Wert eines Ausdrucks nur von seiner Umgebung (=seinen Teilausdrücken) abhängt und nicht vom Zeitpunkt seiner Auswertung oder von seiner Position im Programm.