From 4e85d3d65769851e52b03cdaf4df8c210e621246 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Sat, 31 Oct 2015 01:15:59 +0100 Subject: shortened filenames --- ws2015/EiP/blaetter/01/Basistypen.md | 14 ++ ws2015/EiP/blaetter/01/GreatEscape.java | 11 ++ ws2015/EiP/blaetter/01/manifest | 2 + ws2015/EiP/blaetter/02/Arithmetik.java | 33 ++++ ws2015/EiP/blaetter/02/H2-1.md | 18 ++ ws2015/EiP/blaetter/02/H2-2.md | 13 ++ ws2015/EiP/blaetter/02/H2-3.java | 1 + ws2015/EiP/blaetter/02/manifest | 3 + ws2015/EiP/blaetter/02/test.sh | 20 ++ ws2015/FFP/blaetter/02/FFP_U02_Typklassen.hs | 206 +++++++++++++++++++++ .../blaetter/01/Basistypen.md | 14 -- .../blaetter/01/GreatEscape.java | 11 -- .../blaetter/01/manifest | 2 - .../blaetter/02/Arithmetik.java | 33 ---- .../blaetter/02/H2-1.md | 18 -- .../blaetter/02/H2-2.md | 13 -- .../blaetter/02/H2-3.java | 1 - .../blaetter/02/manifest | 3 - .../blaetter/02/test.sh | 20 -- .../blaetter/02/FFP_U02_Typklassen.hs | 206 --------------------- 20 files changed, 321 insertions(+), 321 deletions(-) create mode 100644 ws2015/EiP/blaetter/01/Basistypen.md create mode 100644 ws2015/EiP/blaetter/01/GreatEscape.java create mode 100644 ws2015/EiP/blaetter/01/manifest create mode 100644 ws2015/EiP/blaetter/02/Arithmetik.java create mode 100644 ws2015/EiP/blaetter/02/H2-1.md create mode 100644 ws2015/EiP/blaetter/02/H2-2.md create mode 120000 ws2015/EiP/blaetter/02/H2-3.java create mode 100644 ws2015/EiP/blaetter/02/manifest create mode 100644 ws2015/EiP/blaetter/02/test.sh create mode 100644 ws2015/FFP/blaetter/02/FFP_U02_Typklassen.hs delete mode 100644 ws2015/einfuehrung_in_die_programmierung/blaetter/01/Basistypen.md delete mode 100644 ws2015/einfuehrung_in_die_programmierung/blaetter/01/GreatEscape.java delete mode 100644 ws2015/einfuehrung_in_die_programmierung/blaetter/01/manifest delete mode 100644 ws2015/einfuehrung_in_die_programmierung/blaetter/02/Arithmetik.java delete mode 100644 ws2015/einfuehrung_in_die_programmierung/blaetter/02/H2-1.md delete mode 100644 ws2015/einfuehrung_in_die_programmierung/blaetter/02/H2-2.md delete mode 120000 ws2015/einfuehrung_in_die_programmierung/blaetter/02/H2-3.java delete mode 100644 ws2015/einfuehrung_in_die_programmierung/blaetter/02/manifest delete mode 100644 ws2015/einfuehrung_in_die_programmierung/blaetter/02/test.sh delete mode 100644 ws2015/fortgeschrittene_funktionale_programmierung/blaetter/02/FFP_U02_Typklassen.hs (limited to 'ws2015') diff --git a/ws2015/EiP/blaetter/01/Basistypen.md b/ws2015/EiP/blaetter/01/Basistypen.md new file mode 100644 index 0000000..0074be2 --- /dev/null +++ b/ws2015/EiP/blaetter/01/Basistypen.md @@ -0,0 +1,14 @@ +# Aufgabe H1-2 -- Basistypen II + +a) + `(double)3.0` +b) + `(double)1.3333333333333333` +c) + `(double)1.6666666666666665` +d) + `(double)1.75` +e) + `(string)"7.27"` +f) + `(string)"374.2"` diff --git a/ws2015/EiP/blaetter/01/GreatEscape.java b/ws2015/EiP/blaetter/01/GreatEscape.java new file mode 100644 index 0000000..35fa406 --- /dev/null +++ b/ws2015/EiP/blaetter/01/GreatEscape.java @@ -0,0 +1,11 @@ +public class GreatEscape +{ + public static void main (String[] args) + { + System.out.println(" \\__/ \\__/"); + System.out.println(" (\"\") (\"\")"); + System.out.println(" .-----\\/ \\/-----."); + System.out.println(" /|_____| |_____|\\"); + System.out.println("\" | \\ || || / | \""); + } +} diff --git a/ws2015/EiP/blaetter/01/manifest b/ws2015/EiP/blaetter/01/manifest new file mode 100644 index 0000000..775d7e2 --- /dev/null +++ b/ws2015/EiP/blaetter/01/manifest @@ -0,0 +1,2 @@ +GreatEscape.java +Basistypen.pdf \ No newline at end of file diff --git a/ws2015/EiP/blaetter/02/Arithmetik.java b/ws2015/EiP/blaetter/02/Arithmetik.java new file mode 100644 index 0000000..90335a4 --- /dev/null +++ b/ws2015/EiP/blaetter/02/Arithmetik.java @@ -0,0 +1,33 @@ +import java.util.Scanner; + +class Arithmetik +{ + public static void main (String[] args) + { + Scanner scanner = new Scanner(System.in); + + System.out.print("Vorname: "); + String vorname = scanner.nextLine(); + System.out.print("Nachname: "); + String nachname = scanner.nextLine(); + System.out.print("x_1 = "); + int x1 = scanner.nextInt(); + System.out.print("x_2 = "); + int x2 = scanner.nextInt(); + + System.out.print("Hallo " + vorname.substring(0,1) + ". " + nachname + "! "); + + if (x1 < x2) + { + System.out.println("Der Mittelwert von " + x1 + " und " + x2 + " ist übrigens " + ((x1 + x2) / 2.0) + "!"); + } + else if (x1 > 0 && x2 > 0) + { + System.out.println("Der Kehrwert von " + x1 + " ist ungefähr " + 1.0/x1 + "!"); + } + else + { + System.out.println(x1 + x2); + } + } +} diff --git a/ws2015/EiP/blaetter/02/H2-1.md b/ws2015/EiP/blaetter/02/H2-1.md new file mode 100644 index 0000000..e2fa908 --- /dev/null +++ b/ws2015/EiP/blaetter/02/H2-1.md @@ -0,0 +1,18 @@ +# Speicherbild + +Wir notieren eine Referenz mit Variablennamen `x` auf ein Objekt, dessen Repräsentation als String `...` ist, wie folgt: + +~~~ {.java} +x -> ... +~~~ + +~~~ {.java} +Int x = 9 +Prof prof1 -> Prof[name="Chris",teaching=9] +Prof prof2 -> Prof[name="Dora",teaching=9] +Student student1 -> Student[name="Alois",matrikel=1234] +Student student2 -> Student[name="Bine",matrikel=4567] +Student student3 -> Student[name="Alois",matrikel=1234] +~~~ + +`student1` und `student3` zeigen auf unterschiedliche Speicherbereiche. diff --git a/ws2015/EiP/blaetter/02/H2-2.md b/ws2015/EiP/blaetter/02/H2-2.md new file mode 100644 index 0000000..430d28e --- /dev/null +++ b/ws2015/EiP/blaetter/02/H2-2.md @@ -0,0 +1,13 @@ +# Variablen + +2 -- `int x` + ~ Instanzvariable -- Lebenspanne identisch mit der des Objekts, Sichtbar (und nicht überschattet) in 9, und 13 + +4 -- `int x` + ~ Parameter -- Lebenspanne bis 6, Sichtbar in 5 + +12 -- `int y` + ~ Parameter -- Lebenspanne bis 17, Sichtbar in 13--16 + +14 -- `int x` + ~ Lokale Variable -- Lebenspanne bis 17, Sichtbar in 15--16 diff --git a/ws2015/EiP/blaetter/02/H2-3.java b/ws2015/EiP/blaetter/02/H2-3.java new file mode 120000 index 0000000..34aea7f --- /dev/null +++ b/ws2015/EiP/blaetter/02/H2-3.java @@ -0,0 +1 @@ +Arithmetik.java \ No newline at end of file diff --git a/ws2015/EiP/blaetter/02/manifest b/ws2015/EiP/blaetter/02/manifest new file mode 100644 index 0000000..9cec2d1 --- /dev/null +++ b/ws2015/EiP/blaetter/02/manifest @@ -0,0 +1,3 @@ +H2-1.pdf +H2-2.pdf +H2-3.java \ No newline at end of file diff --git a/ws2015/EiP/blaetter/02/test.sh b/ws2015/EiP/blaetter/02/test.sh new file mode 100644 index 0000000..5647e13 --- /dev/null +++ b/ws2015/EiP/blaetter/02/test.sh @@ -0,0 +1,20 @@ +#!/usr/bin/env zsh + +runTest() { + ret=$(echo $1 | java Arithmetik | tail -c +32) + if [[ $ret != $2 ]]; then + echo "Input:" + echo $1 + echo "Should return:" + echo $2 + echo "But returns:" + echo $ret + exit 1 + fi +} + +gup --update Arithmetik.class || exit 1 + +runTest "Christian\nElegans\n2\n7" "Hallo C. Elegans! Der Mittelwert von 2 und 7 ist übrigens 4.5!" +runTest "Gustav\nEnauer\n70\n15" "Hallo G. Enauer! Der Kehrwert von 70 ist ungefähr 0.014285714285714!" +runTest "Karla\nEhr-Wert\n7\n3" "Hallo K. Ehr-Wert! Der Kehrwert von 7 ist ungefähr 0.143!" diff --git a/ws2015/FFP/blaetter/02/FFP_U02_Typklassen.hs b/ws2015/FFP/blaetter/02/FFP_U02_Typklassen.hs new file mode 100644 index 0000000..5f2d936 --- /dev/null +++ b/ws2015/FFP/blaetter/02/FFP_U02_Typklassen.hs @@ -0,0 +1,206 @@ +-- Fortgeschrittene Funktionale Programmierung, +-- LMU, TCS, Wintersemester 2015/16 +-- Steffen Jost, Alexander Isenko +-- +-- Übungsblatt 02. 28.10.2015 +-- +-- Thema: +-- +-- Anweisung: +-- Gehen Sie diese Datei durch und bearbeiten Sie +-- alle Vorkommen von undefined bzw. die mit -- !!! TODO !!! +-- markierten Stellen. Testen Sie Ihre Lösungen mit GHCi! + + +-- | A2-1 Funktionsdefinitionen +-- +-- Implementieren Sie folgende grundlegenden, +-- bekannten Funktionen in Haskell. +-- Selbst wenn Sie die Funktion nicht kennen, +-- sollte Ihnen der Typ die korrekte Lösung ermöglichen! +-- + +import Prelude hiding (uncurry,flip,(.),map,zip,zipWith,zip,foldl) + +import qualified Data.Map as P + +-- Hinweis: Das import-Statement müssen Sie jetzt noch nicht verstehen, +-- es ist nur notwendig zur Vermeidung von Namenskonflikten mit der +-- Standardbibliothek, welche die meisten dieser Funktionen bereits enthält. + +-- a) Uncurrying +-- > uncurry (/) (1,2) == 0.5 +uncurry :: (a -> b -> c) -> ((a,b) -> c) +uncurry f (a,b) = f a b + +-- b) Anwendung einer Funktion mit zwei Argumenten auf ein Paar +-- > (1,2) ||> (/) == 0.5 +(||>) :: (a,b) -> (a -> b -> c) -> c +p ||> f = uncurry f p + + +-- c) Vertauschung der Reihenfolge der Funktionsargumente +-- > flip (/) 2 1 == 0.5 +flip :: (a -> b -> c) -> (b -> a -> c) +flip f b a = f a b + + +-- d) Funktionskomposition +-- > ((\x->x+3) . (\y->y*2)) 1 == 5 +(.) :: (b -> c) -> (a -> b) -> a -> c +(.) f g x = f $ g x + + +-- e) Map (im Gegensatz zu A1-3 dieses Mal ohne List-Comprehension) +-- > map (+10) [1,2,3,4] == [11,12,13,14] +map :: (a -> b) -> [a] -> [b] +map _ [] = [] +map f (x:xs) = f x : map f xs + + +-- f) zip: +-- > zip ['a','b','c'] [1,2,3,4,5] = [('a',1),('b',2),('c',3)] +zip :: [a] -> [b] -> [(a,b)] +zip [] _ = [] +zip _ [] = [] +zip (x:xs) (y:ys) = (x, y) : zip xs ys + + +-- g) Zippen mit Funktionsanwendung: +-- > zipWith (+) [1..] [1..3] == [2,4,6] +zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] +zipWith f xs ys = map (uncurry f) $ zip xs ys + + +-- h) Falten nach links: +-- > foldl (flip (:) ) [] [1..3] == [3,2,1] +-- > foldl (\acc x -> x : acc)) [] [1..3] == [3,2,1] +foldl :: (b -> a -> b) -> b -> [a] -> b +foldl _ x [] = x +foldl f x (y:ys) = foldl f (f x y) ys + + + +-- | A2-2 LambdaTerme +-- +-- Betrachten Sie die Lösung zur A1-1 g): + +data LambdaTerm = LVar Char + | LAbs Char LambdaTerm + | LApp LambdaTerm LambdaTerm + +-- Ein paar Lambda Terme zum Testen: +lTerm_x = LVar 'x' +lTerm_y = LVar 'y' +lTerm_id = LAbs 'x' lTerm_x +lTerm_xx = LApp lTerm_x lTerm_x +lTerm_t = LAbs 'x' $ LApp lTerm_y lTerm_xx +lTerm_yk = LAbs 'y' $ LApp lTerm_t lTerm_t + +-- a) Implementieren Sie eine Eq-Instanz für den Datentyp LambdaTerm! +-- +-- (Wer Lambda-Kalkül kennt: Zur Vereinfachung der Aufgabe +-- ignorieren wir die übliche alpha-Äquivalenz, d.h. +-- (LAbs 'x' $ LVar 'x') und (LAbs 'y' $ LVar 'y') +-- dürfen als verschieden betrachtet werden) + +instance Eq LambdaTerm where + (LVar a) == (LVar b) = a == b + (LVar _) == _ = False + (LAbs a t_a) == (LAbs b t_b) = a == b && t_a == t_b + (LAbs _ _) == _ = False + (LApp t_a t'_a) == (LApp t_b t'_b) = t_a == t_b && t'_a == t'_b + (LApp _ _) == _ = False + +-- b) Implementieren Sie die eine Show-Instanz für LambdaTerm. +-- Achten Sie dabei auf eine korrekte Klammerung, aber +-- verschwenden Sie erst einmal keine Zeit darauf, +-- überflüssige Klammern zu vermeiden. + +instance Show LambdaTerm where + show (LVar a) = "LVar '" ++ pure a ++ "'" + show (LAbs a t) = "LAbs '" ++ pure a ++ "' (" ++ show t ++ ")" + show (LApp t t') = "LApp (" ++ show t ++ ") (" ++ show t' ++ ")" + + +-- | A2-3 Klassendeklaration +-- +-- a) Deklarieren Sie eine Klasse "FinMap" für endliche partielle Abbildungen, welche folgende Operationen bereitsstellt: +-- 1) "emptyM" liefert eine leere Abbildung +-- 2) "insertM x a m" fügt die Abbildung [x->a] in die Abbildung m ein. +-- Falls x schon enthalten war, dann wird es überschrieben. +-- 3) "lookupM x m" liefert Nothing zurück, falls x nicht in m enthalten ist; +-- ansonsten wird der für x gespeicherte Wert z zurückgeliefert (in Just verpackt) +-- Die Funktion "lookupM" darf dabei annehmen, dass für x eine Vergleichsoperation vorliegt!?! + +class FinMap m where + emptyM :: m k v + insertM :: Ord k => k -> v -> m k v -> m k v + lookupM :: Ord k => k -> m k v -> Maybe v + -- Can we get around using constraints here without using the MultiParamTypeClasses language extension? + +-- b) Machen Sie folgenden Datentyp zu einer Instanz der Typklasse Map: + +-- data AL a b = AL [(a,b)] +newtype AL a b = AL [(a,b)] -- Äquivalent zur vorherigen Zeile. + -- newtype kann und darf verwenden werden, + -- wenn man nur einen Konstruktor mit nur einem Argument hat. + -- Dies erlaubt GHC eine Optimierung durchzuführen. + deriving (Show, Read, Eq) + +instance FinMap AL where + emptyM = AL $ [] + insertM x a (AL m) = AL $ (x, a) : [p | p@(x', _) <- m, x' /= x] + lookupM x (AL m) = listToMaybe [y | (x', y) <- m, x' == x] -- Due to lazyness this is no slower than explicitly short-circuiting the search + where + -- This is part of Data.Maybe + listToMaybe [] = Nothing + listToMaybe (x:_) = Just x + + +---- Werte zum anschließendem Testen, auskommentieren, +---- sobald Klasse und Instanz definiert wurden: +testMap0 :: AL Int Bool +testMap0 = emptyM +testMap1 = insertM 1 False testMap0 +testMap2 = insertM 3 False testMap1 +testMap3 = insertM 4 True testMap2 +testMap4 = insertM 2 True testMap3 + + +-- Hinweis: +-- Partielle Abbildungen wie hier durch Assoziationslisten zu implementieren, +-- ist nicht bensonders effizient, da der Zugriff auf ein Element im Allgemeinen +-- den Aufwand O(n) hat (man muss die ganze Liste abklappern - es könnte sich ja +-- um das letzte Element der Liste handeln). +-- Mit Suchbäumen läßt sich der Aufwand bekanntermaßen auf O(log n) reduzieren. +-- Wer noch Lust & Zeit hat, kann versuchen, dies selbst zu implementieren +-- und zur einer weiteren Instanz von FinMap machen. +-- +-- Die Standardbibliothek sieht zur Abstraktion hier keine solche Klasse vor, +-- sondern bietet lediglich eine konkrete, effiziente Implementierung von +-- endlichen Abbildungen an: Data.Map, welche wir in der kommenden Vorlesung +-- betrachten werden. +-- +-- Dies kann man natürlich ganz schnell zu einer Instanz von FinMap machen. Wie? + +data Map k v = Tip + | Branch k v (Map k v) (Map k v) + +instance FinMap Map where + emptyM = Tip + insertM k v Tip = Branch k v Tip Tip + insertM k v (Branch k' v' lt gt) + | k == k' = Branch k v lt gt + | k < k' = Branch k' v' (insertM k v lt) gt + | otherwise = Branch k' v' lt (insertM k v gt) + lookupM _ Tip = Nothing + lookupM k (Branch k' v' lt gt) + | k == k' = Just v' + | k < k' = lookupM k lt + | otherwise = lookupM k gt + +instance FinMap P.Map where + emptyM = P.empty + insertM = P.insert + lookupM = P.lookup diff --git a/ws2015/einfuehrung_in_die_programmierung/blaetter/01/Basistypen.md b/ws2015/einfuehrung_in_die_programmierung/blaetter/01/Basistypen.md deleted file mode 100644 index 0074be2..0000000 --- a/ws2015/einfuehrung_in_die_programmierung/blaetter/01/Basistypen.md +++ /dev/null @@ -1,14 +0,0 @@ -# Aufgabe H1-2 -- Basistypen II - -a) - `(double)3.0` -b) - `(double)1.3333333333333333` -c) - `(double)1.6666666666666665` -d) - `(double)1.75` -e) - `(string)"7.27"` -f) - `(string)"374.2"` diff --git a/ws2015/einfuehrung_in_die_programmierung/blaetter/01/GreatEscape.java b/ws2015/einfuehrung_in_die_programmierung/blaetter/01/GreatEscape.java deleted file mode 100644 index 35fa406..0000000 --- a/ws2015/einfuehrung_in_die_programmierung/blaetter/01/GreatEscape.java +++ /dev/null @@ -1,11 +0,0 @@ -public class GreatEscape -{ - public static void main (String[] args) - { - System.out.println(" \\__/ \\__/"); - System.out.println(" (\"\") (\"\")"); - System.out.println(" .-----\\/ \\/-----."); - System.out.println(" /|_____| |_____|\\"); - System.out.println("\" | \\ || || / | \""); - } -} diff --git a/ws2015/einfuehrung_in_die_programmierung/blaetter/01/manifest b/ws2015/einfuehrung_in_die_programmierung/blaetter/01/manifest deleted file mode 100644 index 775d7e2..0000000 --- a/ws2015/einfuehrung_in_die_programmierung/blaetter/01/manifest +++ /dev/null @@ -1,2 +0,0 @@ -GreatEscape.java -Basistypen.pdf \ No newline at end of file diff --git a/ws2015/einfuehrung_in_die_programmierung/blaetter/02/Arithmetik.java b/ws2015/einfuehrung_in_die_programmierung/blaetter/02/Arithmetik.java deleted file mode 100644 index 90335a4..0000000 --- a/ws2015/einfuehrung_in_die_programmierung/blaetter/02/Arithmetik.java +++ /dev/null @@ -1,33 +0,0 @@ -import java.util.Scanner; - -class Arithmetik -{ - public static void main (String[] args) - { - Scanner scanner = new Scanner(System.in); - - System.out.print("Vorname: "); - String vorname = scanner.nextLine(); - System.out.print("Nachname: "); - String nachname = scanner.nextLine(); - System.out.print("x_1 = "); - int x1 = scanner.nextInt(); - System.out.print("x_2 = "); - int x2 = scanner.nextInt(); - - System.out.print("Hallo " + vorname.substring(0,1) + ". " + nachname + "! "); - - if (x1 < x2) - { - System.out.println("Der Mittelwert von " + x1 + " und " + x2 + " ist übrigens " + ((x1 + x2) / 2.0) + "!"); - } - else if (x1 > 0 && x2 > 0) - { - System.out.println("Der Kehrwert von " + x1 + " ist ungefähr " + 1.0/x1 + "!"); - } - else - { - System.out.println(x1 + x2); - } - } -} diff --git a/ws2015/einfuehrung_in_die_programmierung/blaetter/02/H2-1.md b/ws2015/einfuehrung_in_die_programmierung/blaetter/02/H2-1.md deleted file mode 100644 index e2fa908..0000000 --- a/ws2015/einfuehrung_in_die_programmierung/blaetter/02/H2-1.md +++ /dev/null @@ -1,18 +0,0 @@ -# Speicherbild - -Wir notieren eine Referenz mit Variablennamen `x` auf ein Objekt, dessen Repräsentation als String `...` ist, wie folgt: - -~~~ {.java} -x -> ... -~~~ - -~~~ {.java} -Int x = 9 -Prof prof1 -> Prof[name="Chris",teaching=9] -Prof prof2 -> Prof[name="Dora",teaching=9] -Student student1 -> Student[name="Alois",matrikel=1234] -Student student2 -> Student[name="Bine",matrikel=4567] -Student student3 -> Student[name="Alois",matrikel=1234] -~~~ - -`student1` und `student3` zeigen auf unterschiedliche Speicherbereiche. diff --git a/ws2015/einfuehrung_in_die_programmierung/blaetter/02/H2-2.md b/ws2015/einfuehrung_in_die_programmierung/blaetter/02/H2-2.md deleted file mode 100644 index 430d28e..0000000 --- a/ws2015/einfuehrung_in_die_programmierung/blaetter/02/H2-2.md +++ /dev/null @@ -1,13 +0,0 @@ -# Variablen - -2 -- `int x` - ~ Instanzvariable -- Lebenspanne identisch mit der des Objekts, Sichtbar (und nicht überschattet) in 9, und 13 - -4 -- `int x` - ~ Parameter -- Lebenspanne bis 6, Sichtbar in 5 - -12 -- `int y` - ~ Parameter -- Lebenspanne bis 17, Sichtbar in 13--16 - -14 -- `int x` - ~ Lokale Variable -- Lebenspanne bis 17, Sichtbar in 15--16 diff --git a/ws2015/einfuehrung_in_die_programmierung/blaetter/02/H2-3.java b/ws2015/einfuehrung_in_die_programmierung/blaetter/02/H2-3.java deleted file mode 120000 index 34aea7f..0000000 --- a/ws2015/einfuehrung_in_die_programmierung/blaetter/02/H2-3.java +++ /dev/null @@ -1 +0,0 @@ -Arithmetik.java \ No newline at end of file diff --git a/ws2015/einfuehrung_in_die_programmierung/blaetter/02/manifest b/ws2015/einfuehrung_in_die_programmierung/blaetter/02/manifest deleted file mode 100644 index 9cec2d1..0000000 --- a/ws2015/einfuehrung_in_die_programmierung/blaetter/02/manifest +++ /dev/null @@ -1,3 +0,0 @@ -H2-1.pdf -H2-2.pdf -H2-3.java \ No newline at end of file diff --git a/ws2015/einfuehrung_in_die_programmierung/blaetter/02/test.sh b/ws2015/einfuehrung_in_die_programmierung/blaetter/02/test.sh deleted file mode 100644 index 5647e13..0000000 --- a/ws2015/einfuehrung_in_die_programmierung/blaetter/02/test.sh +++ /dev/null @@ -1,20 +0,0 @@ -#!/usr/bin/env zsh - -runTest() { - ret=$(echo $1 | java Arithmetik | tail -c +32) - if [[ $ret != $2 ]]; then - echo "Input:" - echo $1 - echo "Should return:" - echo $2 - echo "But returns:" - echo $ret - exit 1 - fi -} - -gup --update Arithmetik.class || exit 1 - -runTest "Christian\nElegans\n2\n7" "Hallo C. Elegans! Der Mittelwert von 2 und 7 ist übrigens 4.5!" -runTest "Gustav\nEnauer\n70\n15" "Hallo G. Enauer! Der Kehrwert von 70 ist ungefähr 0.014285714285714!" -runTest "Karla\nEhr-Wert\n7\n3" "Hallo K. Ehr-Wert! Der Kehrwert von 7 ist ungefähr 0.143!" diff --git a/ws2015/fortgeschrittene_funktionale_programmierung/blaetter/02/FFP_U02_Typklassen.hs b/ws2015/fortgeschrittene_funktionale_programmierung/blaetter/02/FFP_U02_Typklassen.hs deleted file mode 100644 index 5f2d936..0000000 --- a/ws2015/fortgeschrittene_funktionale_programmierung/blaetter/02/FFP_U02_Typklassen.hs +++ /dev/null @@ -1,206 +0,0 @@ --- Fortgeschrittene Funktionale Programmierung, --- LMU, TCS, Wintersemester 2015/16 --- Steffen Jost, Alexander Isenko --- --- Übungsblatt 02. 28.10.2015 --- --- Thema: --- --- Anweisung: --- Gehen Sie diese Datei durch und bearbeiten Sie --- alle Vorkommen von undefined bzw. die mit -- !!! TODO !!! --- markierten Stellen. Testen Sie Ihre Lösungen mit GHCi! - - --- | A2-1 Funktionsdefinitionen --- --- Implementieren Sie folgende grundlegenden, --- bekannten Funktionen in Haskell. --- Selbst wenn Sie die Funktion nicht kennen, --- sollte Ihnen der Typ die korrekte Lösung ermöglichen! --- - -import Prelude hiding (uncurry,flip,(.),map,zip,zipWith,zip,foldl) - -import qualified Data.Map as P - --- Hinweis: Das import-Statement müssen Sie jetzt noch nicht verstehen, --- es ist nur notwendig zur Vermeidung von Namenskonflikten mit der --- Standardbibliothek, welche die meisten dieser Funktionen bereits enthält. - --- a) Uncurrying --- > uncurry (/) (1,2) == 0.5 -uncurry :: (a -> b -> c) -> ((a,b) -> c) -uncurry f (a,b) = f a b - --- b) Anwendung einer Funktion mit zwei Argumenten auf ein Paar --- > (1,2) ||> (/) == 0.5 -(||>) :: (a,b) -> (a -> b -> c) -> c -p ||> f = uncurry f p - - --- c) Vertauschung der Reihenfolge der Funktionsargumente --- > flip (/) 2 1 == 0.5 -flip :: (a -> b -> c) -> (b -> a -> c) -flip f b a = f a b - - --- d) Funktionskomposition --- > ((\x->x+3) . (\y->y*2)) 1 == 5 -(.) :: (b -> c) -> (a -> b) -> a -> c -(.) f g x = f $ g x - - --- e) Map (im Gegensatz zu A1-3 dieses Mal ohne List-Comprehension) --- > map (+10) [1,2,3,4] == [11,12,13,14] -map :: (a -> b) -> [a] -> [b] -map _ [] = [] -map f (x:xs) = f x : map f xs - - --- f) zip: --- > zip ['a','b','c'] [1,2,3,4,5] = [('a',1),('b',2),('c',3)] -zip :: [a] -> [b] -> [(a,b)] -zip [] _ = [] -zip _ [] = [] -zip (x:xs) (y:ys) = (x, y) : zip xs ys - - --- g) Zippen mit Funktionsanwendung: --- > zipWith (+) [1..] [1..3] == [2,4,6] -zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] -zipWith f xs ys = map (uncurry f) $ zip xs ys - - --- h) Falten nach links: --- > foldl (flip (:) ) [] [1..3] == [3,2,1] --- > foldl (\acc x -> x : acc)) [] [1..3] == [3,2,1] -foldl :: (b -> a -> b) -> b -> [a] -> b -foldl _ x [] = x -foldl f x (y:ys) = foldl f (f x y) ys - - - --- | A2-2 LambdaTerme --- --- Betrachten Sie die Lösung zur A1-1 g): - -data LambdaTerm = LVar Char - | LAbs Char LambdaTerm - | LApp LambdaTerm LambdaTerm - --- Ein paar Lambda Terme zum Testen: -lTerm_x = LVar 'x' -lTerm_y = LVar 'y' -lTerm_id = LAbs 'x' lTerm_x -lTerm_xx = LApp lTerm_x lTerm_x -lTerm_t = LAbs 'x' $ LApp lTerm_y lTerm_xx -lTerm_yk = LAbs 'y' $ LApp lTerm_t lTerm_t - --- a) Implementieren Sie eine Eq-Instanz für den Datentyp LambdaTerm! --- --- (Wer Lambda-Kalkül kennt: Zur Vereinfachung der Aufgabe --- ignorieren wir die übliche alpha-Äquivalenz, d.h. --- (LAbs 'x' $ LVar 'x') und (LAbs 'y' $ LVar 'y') --- dürfen als verschieden betrachtet werden) - -instance Eq LambdaTerm where - (LVar a) == (LVar b) = a == b - (LVar _) == _ = False - (LAbs a t_a) == (LAbs b t_b) = a == b && t_a == t_b - (LAbs _ _) == _ = False - (LApp t_a t'_a) == (LApp t_b t'_b) = t_a == t_b && t'_a == t'_b - (LApp _ _) == _ = False - --- b) Implementieren Sie die eine Show-Instanz für LambdaTerm. --- Achten Sie dabei auf eine korrekte Klammerung, aber --- verschwenden Sie erst einmal keine Zeit darauf, --- überflüssige Klammern zu vermeiden. - -instance Show LambdaTerm where - show (LVar a) = "LVar '" ++ pure a ++ "'" - show (LAbs a t) = "LAbs '" ++ pure a ++ "' (" ++ show t ++ ")" - show (LApp t t') = "LApp (" ++ show t ++ ") (" ++ show t' ++ ")" - - --- | A2-3 Klassendeklaration --- --- a) Deklarieren Sie eine Klasse "FinMap" für endliche partielle Abbildungen, welche folgende Operationen bereitsstellt: --- 1) "emptyM" liefert eine leere Abbildung --- 2) "insertM x a m" fügt die Abbildung [x->a] in die Abbildung m ein. --- Falls x schon enthalten war, dann wird es überschrieben. --- 3) "lookupM x m" liefert Nothing zurück, falls x nicht in m enthalten ist; --- ansonsten wird der für x gespeicherte Wert z zurückgeliefert (in Just verpackt) --- Die Funktion "lookupM" darf dabei annehmen, dass für x eine Vergleichsoperation vorliegt!?! - -class FinMap m where - emptyM :: m k v - insertM :: Ord k => k -> v -> m k v -> m k v - lookupM :: Ord k => k -> m k v -> Maybe v - -- Can we get around using constraints here without using the MultiParamTypeClasses language extension? - --- b) Machen Sie folgenden Datentyp zu einer Instanz der Typklasse Map: - --- data AL a b = AL [(a,b)] -newtype AL a b = AL [(a,b)] -- Äquivalent zur vorherigen Zeile. - -- newtype kann und darf verwenden werden, - -- wenn man nur einen Konstruktor mit nur einem Argument hat. - -- Dies erlaubt GHC eine Optimierung durchzuführen. - deriving (Show, Read, Eq) - -instance FinMap AL where - emptyM = AL $ [] - insertM x a (AL m) = AL $ (x, a) : [p | p@(x', _) <- m, x' /= x] - lookupM x (AL m) = listToMaybe [y | (x', y) <- m, x' == x] -- Due to lazyness this is no slower than explicitly short-circuiting the search - where - -- This is part of Data.Maybe - listToMaybe [] = Nothing - listToMaybe (x:_) = Just x - - ----- Werte zum anschließendem Testen, auskommentieren, ----- sobald Klasse und Instanz definiert wurden: -testMap0 :: AL Int Bool -testMap0 = emptyM -testMap1 = insertM 1 False testMap0 -testMap2 = insertM 3 False testMap1 -testMap3 = insertM 4 True testMap2 -testMap4 = insertM 2 True testMap3 - - --- Hinweis: --- Partielle Abbildungen wie hier durch Assoziationslisten zu implementieren, --- ist nicht bensonders effizient, da der Zugriff auf ein Element im Allgemeinen --- den Aufwand O(n) hat (man muss die ganze Liste abklappern - es könnte sich ja --- um das letzte Element der Liste handeln). --- Mit Suchbäumen läßt sich der Aufwand bekanntermaßen auf O(log n) reduzieren. --- Wer noch Lust & Zeit hat, kann versuchen, dies selbst zu implementieren --- und zur einer weiteren Instanz von FinMap machen. --- --- Die Standardbibliothek sieht zur Abstraktion hier keine solche Klasse vor, --- sondern bietet lediglich eine konkrete, effiziente Implementierung von --- endlichen Abbildungen an: Data.Map, welche wir in der kommenden Vorlesung --- betrachten werden. --- --- Dies kann man natürlich ganz schnell zu einer Instanz von FinMap machen. Wie? - -data Map k v = Tip - | Branch k v (Map k v) (Map k v) - -instance FinMap Map where - emptyM = Tip - insertM k v Tip = Branch k v Tip Tip - insertM k v (Branch k' v' lt gt) - | k == k' = Branch k v lt gt - | k < k' = Branch k' v' (insertM k v lt) gt - | otherwise = Branch k' v' lt (insertM k v gt) - lookupM _ Tip = Nothing - lookupM k (Branch k' v' lt gt) - | k == k' = Just v' - | k < k' = lookupM k lt - | otherwise = lookupM k gt - -instance FinMap P.Map where - emptyM = P.empty - insertM = P.insert - lookupM = P.lookup -- cgit v1.2.3