Aufgabe 1

Geben Sie für folgende Haskell-Ausdrücke jeweils an, ob sie korrekt sind, sowie ggf. einen zugehörigen Typen:

• 1.1

• (1.1)

• (1,1)

• true

• 'string'

• "c"

• ['1', '2', '3', '4']

Lösung 1

::

1.1 :: Float oder
1.1 :: Double
(1.1) :: Float oder Double, ist genau das gleiche
(1,1) :: (Int, Int) ist Tupel, da Komma!
true nicht typkorrekt, da kleingeschrieben
'string' nicht typkorrekt, da einfache Hochkomma
"c" :: String
['1', '2', '3', '4'] :: String oder
['1', '2', '3', '4'] :: [Char]

Aufgabe 1 - Ergänzung

Geben Sie für folgende Haskell-Ausdrücke jeweils an, ob sie korrekt sind, sowie den allgemeinsten Typ:

• 1.1

• (1.1) s.o.

• (1,1)

• true True

• 'string' 's'

• "c"

• ['1', '2', '3', '4']

Lösung 1 mit allgemeinstem Typ

1.1 :: (Fractional a) => a
(1,1) :: (Num a, Num b) => (a, b) 2 Typvariablen, da z.B. Int+Float
True :: Bool
's' :: Char
"c" :: String
['1', '2', '3', '4'] :: String

Aufgabe 2

Bestimmen Sie jeweils den allgemeinsten Typ der folgenden Haskell-Funktionen:

• not

• (<)

• (>=)

• (^)

Lösung 2

not :: Bool -> Bool

(<) :: (Ord a) => a -> a -> Bool

(>=) :: (Ord a) => a -> a -> Bool Ord impliziert bereits Eq

(^) :: (Num a, Integral b) => a -> b -> a

Aufgabe 3

Bestimmen Sie jeweils den allgemeinsten Typ der folgenden Haskell-Ausdrücke:

• (+1)

• (/0)

• ((^) 3)

• (^3)

• 2^3

Lösung 3

(+1) :: (Num a) => a -> a
(/0) :: (Fractional a) => a -> a
syntaktisch korrekt
((^) 3) :: (Integral a, Num b) => a -> b 
(^)::(Integral b, Num a) => a -> b -> a
(^3) :: (Num a) => a -> a
2^3 :: (Num a) => a

Aufgabe 4 (1)

Erzeugen Sie mittels Mengenkomprehension folgende Listen:

• Die unendliche Liste aller Zahlen den Form n⁴-2n, wobei n eine gerade, natürliche Zahl ist.
• Die unendliche Liste aller natürlichen Zahlen, die bei Division mit 11 den Rest 3 und bei Division mit 13 den Rest 7 lassen.
• Es wird vermutet, dass jede natürliche Zahl, die selbst keine Primzahl ist, als Summe zweier Primzahlen darstellbar ist. Geben Sie für jede natürliche Zahl n alle Tupel der Form (n, (p₁, p₂)) an, mit p₁ und p₂ Primzahlen, und p₁ + p₂ = n.

Lösung 4 (1)

[n^4-2*n | n <- [2,4..]]

[n | n <- [1..], n `mod` 11 == 3, n `mod` 13 == 7]

[(n, (p, (n-p))) | n <- [1..], p <- [1..(n `div` 2)], 
	not(isPrime n), isPrime p, isPrime (n-p)]

Aufgabe 4 (2)

• Die unendliche Liste der Noten, d.h.

  [1.0,1.3,1.7,2.0,2.3,2.7,...]

• Alle Werte, die sich mit bis zu drei verschiedenen Euro-Münzen darstellen lassen.

Lösung 4 (2)

[z+d | z <- [1..], d <- [0,0.3,0.7]]

[x+y+z | x <- [0,0.01,0.02,0.05,0.10,0.20,0.50,1.00,2.00], 
			y <- [0,0.01,0.02,0.05,0.10,0.20,0.50,1.00,2.00], 
			z <- [0.01,0.02,0.05,0.10,0.20,0.50,1.00,2.00],
			(x == 0 && y == 0) || (x < y && y < z)]

Aufgabe 5

Klausuraufgabe SS11-2

Bestimmen Sie jeweils den Typ der folgenden Haskell-Ausdrücke:

('1', '2':"3", 4 < 5)

[(last, tail), (head, take 5)]

[(+), (-)]

[map (const True), map not]

Lösung 5

Klausuraufgabe SS11-2

Bestimmen Sie jeweils den Typ der folgenden Haskell-Ausdrücke:

('1', '2':"3", 4 < 5) :: (Char, String, Bool)

[(last, tail), (head, take 5)] :: [ ([a] -> a, [b] -> [b]) ]

[(+), (-)] :: Num a => [a -> a -> a]

[map (const True), map not] :: [ [Bool] -> [Bool] ]

Aufgabe 6 (1)

Definieren Sie folgende Funktionen. Verwenden Sie wenn nötig explizite Rekursion.

addPair (a,b) (c,d) = (a+c, b+d)

Aufgabe 6 (2)

map :: (a -> b) -> [a] -> [b]

Eine Funktion, eine übergebene Funktion auf alle Listenelemente anwendet.

map f (x:xs) = f x : map f xs
map _ [] = []

Aufgabe 6 (3)

zip :: [a] -> [b] -> [(a,b)]

Eine Funktion, die zwei Listen zu einer Liste von Paaren zusammensetzt.

zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip _ _ = []

unzip :: [(a,b)] -> ([a],[b])

Eine Umkehrfunktion zum o.g. zip.

unzip ((x,y):ls) = (x:xs, y:ys)
    where (xs, ys) = unzip ls
unzip [] = ([],[])

Aufgabe 6 (4)

addPairs :: [(Int, Int)] -> (Int, Int)

Eine Funktion, die eine Liste von Tupel erhält und deren Komponenten paarweise addiert.

addPairs [] = (0,0)
addPairs ((a,b):xs) = (a+c, b+d)
    where (c,d) = addPairs xs

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

Eine Funktion, die als Verallgemeinerung der Funktion zip zwei Listen mittels einer übergebenen Funktion zu einer zusammenfügt.

zipWith f (x:xs) (y:ys) = (f x y) : zipWith f xs ys
zipWith _ _ _ = []

Aufgabe 7 (1)

Definieren Sie folgende Funktionen mit Hilfe von foldl oder foldr:

length :: [a] -> Int

Eine Funktion, die die Anzahl der Elemente einer Liste zurückgibt.

length = foldr (\x y -> 1+y) 0
length' = foldl (\x y -> x+1) 0

quadratsumme :: Integer -> Integer

Eine Funktion, die die Summe der Quadrate aller Zahlen von 1 bis n ausrechnet.

quadratsumme n = foldr (\x y -> x^2 + y) 0 [1..n]
quadratsumme' n = foldl (\x y -> x + y^2) 0 [1..n]

Aufgabe 7 (2)

reverse :: [a] -> [a]

Eine Funktion, die Reihenfolge einer Liste umkehrt.

reverse = foldr (\x y -> y++[x]) []
reverse' = foldl (\x y -> [y]++x) []

fak :: Integer -> Integer

Eine Funktion, die die Fakultät der Zahl n berechnet.

fak n = foldr (*) 1 [1..n]

Aufgabe 8

Über einen rekursiven Datentyp soll die häusliche Verkabelung von Elektro-Geräten abgebildet werden. Ein Stecker führt entweder auf ein Geraet (Attribut Name) oder eine Steckdosenleiste (Attribut Plaetze).

              /\             Steckdosenleiste 5
             /  \
            /    \
           /      \
  Geraet "TV"    /|\         Steckdosenleiste 3
                / | \        
               /  |  \
              /   |   \
             /    |    \
            /     |     \
  Geraet "Hifi"   |    Geraet "Telefon"
         Geraet "Kühlschrank"

Lösung 8

type Plaetze = Int
data Stecker = Steckdosenleiste Plaetze [Stecker]
             | Geraet String
             
steckerBeispiel = Steckdosenleiste 5 
                    [Geraet "TV", Steckdosenleiste 3 
                      [Geraet "Hifi", Geraet "Telefon", 
                        Geraet "Kühlschrank"]
                    ]

Aufgabe 8 - Ergänzung

Geben Sie eine Funktion ueberbelegt :: Stecker -> Bool an, die True zurückgibt, falls es eine Steckdosenleiste gibt, an die mehr Geräte oder Steckdosenleisten angeschlossen sind, als sie Plätze hat.

ueberbelegt :: Stecker -> Bool
ueberbelegt stecker = 
  not (foldStecker 
        (\string -> True) 
        (\plaetze leiste -> and leiste 
                              && plaetze >= length leiste) 
      stecker)

Aufgabe 9: Huffman-Codierung (1)

Bei der Huffman-Codierung handelt es sich um ein einfaches Datenkompressionsverfahren. Dabei wird ausgenutzt, dass Zeichen in einem Text unterschiedlich oft vorkommen. So erhalten häufig auftretende Buchstaben kurze Codewörter und seltene Buchstaben längere. Um die optimale Codelänge zu erhalten, bilden die Buchstaben anhand ihrer Häufigkeit die Blätter eines binären Entscheidungsbaums.

Aufgabe 9: Huffman-Codierung (2)

Beispiel:

         /\
        /  \
   (0) /    \ (1)
      /      \
     a       /\
            /  \
       (0) /    \ (1)
          /      \
         /\       d
        /  \
   (0) /    \ (1)
      /      \
     b        c
     

So lässt sich 'b' durch den Code '100' darstellen, der häufigste Buchstabe 'a' wird durch '0' codiert.

Erstellen Sie einen Datentyp 'HuffmanTree' und geben Sie die Definition des oben gezeigten Binärbaums an.
Hinweis: Gehen Sie davon aus, dass der linke Ast des Baums stets implizit durch '0' codiert wird, der rechte durch '1'.

Lösung 9: Huffman-Codierung (2)

data HuffmanTree = Node HuffmanTree HuffmanTree
                 | Bst Char
  deriving (Eq, Ord, Show)

huffmanBeispiel :: HuffmanTree
huffmanBeispiel = Node (Bst 'a') 
                    (Node (Node (Bst 'b') (Bst 'c')) (Bst 'd'))

Aufgabe 9: Huffman-Codierung (3)

Definieren Sie für diesen Datentypen rekursiv eine Funktion buchstaben :: HuffmanTree -> Int, die die Anzahl der im HuffmanTree hinterlegten Buchstaben zurückliefert.

buchstaben :: HuffmanTree -> Int
buchstaben (Bst _)    = 1
buchstaben (Node l r) = buchstaben l + buchstaben r
-- buchstaben huffmanBeispiel == 4

Aufgabe 9: Huffman-Codierung (4)

Definieren Sie für diesen Datentypen eine fold-Funktion foldHuffman!

foldHuffman :: (Char -> a) -> (a -> a -> a) -> HuffmanTree -> a
foldHuffman bf nf = m
    where m (Bst c) = bf c
          m (Node left right) = nf (m left) (m right)

Aufgabe 9: Huffman-Codierung (5)

Definieren Sie die o.g. buchstaben Funktion über foldHuffman!

buchstaben :: HuffmanTree -> Integer
buchstaben = foldHuffman (\x -> 1) (+)

Aufgabe 9: Huffman-Codierung (6)

Definieren Sie über foldHuffman eine Funktion elemHuffman :: Char -> HuffmanTree -> Bool, die prüft, ob ein Zeichen im HuffmanTree gespeichert ist!

elemHuffman :: Char -> HuffmanTree -> Bool
elemHuffman char = foldHuffman (\c -> char == c) (||)

Skript

... zum Repetitorium gibt's hier:
fnogatz.github.io/talks/pdp-rep-12/haskell/

Credits

Thanks to Benjamin Erb for the html5slides and uulm template.

Title image: Miran Lipovača under CC BY-NC-SA 3.0