Übungen zu Haskell

Aufgabe 1

Typisierung einfacher Werte

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

Angabe des Typs erfolgt nach 

::
.

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 Hochkommata
"c" :: String
['1', '2', '3', '4'] :: String oder
['1', '2', '3', '4'] :: [Char]

Aufgabe 1 - Ergänzung

Typisierung einfacher Werte mit Typklassen

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

Typisierung vordefinierter Funktionen

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

(**) :: Fractional a => a -> a -> a

Aufgabe 3

Typisierung partieller vordefinierter Funktionen

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

Listenerzeugung

Aufgabe 4 (1)

Erzeugen Sie mittels Listenkomprehension folgende Listen:

  • Die unendliche Liste aller Zahlen der Form n^4-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, (p1, p2)) an, mit p1 und p2 Primzahlen, und p1 + p2 = 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 *

Typbestimmung zusammengesetzter Ausdrücke

Aufgabe 5 (1)

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 5 (2)

Klausuraufgabe SS12-2 und SS12-1

Gegeben seien die folgenden Funktionsdefinitionen. Bestimmen Sie jeweils den allgemeinsten Typ der Funktionen:

f :: (Eq a) => a -> [[a]] -> Bool
f x y = any (==x) (concat y)

g :: (Num a, Enum a) => a -> a -> [a]
g u v = map (\(x,y) -> x * y) (zip [u..v] [u..v])

h :: (Ord a) => a -> Maybe a -> Bool
h x (Just y) = x < y
h x (Nothing) = False

Aufgabe 6

Komposition von Rekursionsfunktionen

Aufgabe 6 (1)

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

addPair :: (Int, Int) -> (Int, Int) -> (Int, Int)
Eine Funktion, die die Kompontenten zweier Tupel paarweise addiert.
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 6 (5)

concat :: [[a]] -> [a]
Eine Funktion, die eine Liste aus Listen zu einer Liste zusammenfügt.
concat []     = []
concat (x:xs) = x ++ concat xs
splitAt :: Int -> [a] -> ([a], [a])
Eine Funktion, die eine Liste nach der angegebenen Position in zwei Teillisten aufspaltet.
splitAt n xs = (take n xs, drop n xs)

splitAt' 0 xs     = ([], xs)
splitAt' _ []     = ([], [])
splitAt' n (x:xs) = (x:as, bs)
  where (as,bs) = splitAt' (n-1) xs

Aufgabe 7

Faltungen auf Listen

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

Rekursive Datentypen

Aufgabe 8

Bei der Huffman-Codierung handelt es sich um ein einfaches Datenkompressionsverfahren. Hierbei werden Buchstaben anhand ihrer Häufigkeiten in einem Binärbaum abgespeichert, in dessen Blätter jeweils ein Buchstabe und seine Häufigkeit gespeichert wird.

                    /\                                       Node
        ___________/  \________
       /\                     /\                             Node
      /  \             ______/  \_____
     /    \           /\              \                      Node
    / Char 651 'a'   /  \              \
   /                /  Char 435 'u'     \
Char 615 't'       /                 Char 978 'n'
            Char 253 'm'

Definiere einen Datentyp für diesen Huffman-Tree und gib die Beispielinstanz an!

Lösung 8

type Quantity = Integer
data HuffmanTree = Node HuffmanTree HuffmanTree
                 | Char Quantity Char
  deriving (Eq, Ord, Show)


bsp = Node
        (Node (Char 615 ’t’) (Char 651 ’a’))
        (Node
          (Node (Char 253 ’m’) (Char 435 ’u’))
          (Char 978 ’n’)
        )

Ergänzung zu Aufgabe 8

Rekursive Datentypen

Aufgabe 8 - Ergänzung (1)

Schreibe Funktion quantitySum :: HuffmanTree -> Integer als Instanz von foldHuffmanTree, welche die Summe aller im übergebenen Huffman-Tree gespeicherten Quantity-Werte zurückliefert.

quantitySum :: HuffmanTree -> Integer
quantitySum = foldHuffmanTree const (+)

Aufgabe 8 - Ergänzung (2)

Definiere eine nicht-rekursive Funktion chars :: HuffmanTree -> [(Char,Quantity)], die eine Liste aller im übergebenen Huffman-Tree gespeicherten Buchstaben sowie ihrer absoluten Häufigkeiten zurückliefert. Die Reihenfolge ist dabei beliebig.

chars :: HuffmanTree -> [(Char,Quantity)]
chars = foldHuffmanTree (\q c -> [(c,q)]) (++)

Aufgabe 9

fold auf rekursiven Datentypen

Aufgabe 9 (1)

Gegeben sei der folgende Datentyp MathExpr, mit dem einfache mathematische Terme beschrieben werden können:

type Value = Int

data MathExpr = Value Value
              | Plus MathExpr MathExpr
              | Mal MathExpr MathExpr
              | Fakultaet MathExpr

Geben Sie den Term (3+4)*7! als Instanz dieses Typs an!

bsp = Mal (Plus (Value 3) (Value 4)) (Fakultaet (Value 7))

Aufgabe 9 (2)

type Value = Int
data MathExpr = Value Value
              | Plus MathExpr MathExpr
              | Mal MathExpr MathExpr
              | Fakultaet MathExpr

Definieren Sie rekursiv eine Funktion calcRec :: MathExpr -> Value, die den Term evaluiert, also den berechneten Wert zurückliefert.

Lösung 9 (2)

calcRec :: MathExpr -> Value
calcRec (Value v) = v
calcRec (Plus a b) = (calcRec a) + (calcRec b)
calcRec (Mal a b) = (calcRec a) * (calcRec b)
calcRec (Fakultaet n) = fak m
  where m = calcRec n
        fak 0 = 1
        fak n = n * fak (n-1)

Aufgabe 9 (3)

type Value = Int
data MathExpr = Value Value
              | Plus MathExpr MathExpr
              | Mal MathExpr MathExpr
              | Fakultaet MathExpr

Definieren Sie die fold-Funktion foldME!

foldME :: (Value -> a) ->
               (a -> a -> a) -> (a -> a -> a) -> (a -> a) ->
               MathExpr -> a
              
foldME vf pf mf ff = m
  where m (Value v)     = vf v
        m (Plus p q)    = pf (m p) (m q)
        m (Mal p q)     = mf (m p) (m q)
        m (Fakultaet n) = ff (m n)

Aufgabe 9 (4)

foldME :: (Value -> a) -> 
            (a -> a -> a) -> (a -> a -> a) -> (a -> a) -> 
            MathExpr -> a
foldME vf pf mf ff = m
  where m (Value v)     = vf v
        m (Plus p q)    = pf (m p) (m q)
        m (Mal p q)     = mf (m p) (m q)
        m (Fakultaet n) = ff (m n)

Definieren Sie die Function values :: MathExpr -> [Value] als Instanz von foldME, welches eine Liste aller im Termbaum enthaltenen Werte (Value's) zurückliefert. Die Reihenfolge ist unerheblich.

values :: MathExpr -> [Value]
values = foldME (\v -> [v]) (++) (++) id

Aufgabe 9 (5)

foldME :: (Value -> a) -> 
            (a -> a -> a) -> (a -> a -> a) -> (a -> a) -> 
            MathExpr -> a
foldME vf pf mf ff = m
  where m (Value v)     = vf v
        m (Plus p q)    = pf (m p) (m q)
        m (Mal p q)     = mf (m p) (m q)
        m (Fakultaet n) = ff (m n)

Definieren Sie die nicht-rekursive Function calc :: MathExpr -> Value, die den Wert des übergebenen Terms berechnet.

calc :: MathExpr -> Value
calc = foldME id (+) (*) fak
  where fak 0 = 1
        fak n = n * fak (n-1)

Skript