Wir berechnen die Fakultät \(n! = \prod_{i=1}^n i\).

-- Aufgabe 2(a)
fac :: Int -> Int
fac 0 = 1
fac n = n * fac (n-1)

Wir summieren Fakultäten auf, d.h. berechnen \(\operatorname{sumFacs}(n,m) = \sum_{i=n}^m i!\). Dabei können wir wahlweise die obere Grenze oder die untere Grenze "rausziehen".

-- Aufgabe 2(b)
sumFacs :: Int -> Int -> Int
sumFacs n m
  | n > m = 0
  | otherwise = fac n + sumFacs (n+1) m

sumFacs' :: Int -> Int -> Int
sumFacs' n m
  | n > m = 0
  | otherwise = fac m + sumFacs' n (m-1)

Wir berechnen die Fibonacci-Zahlen und nutzen dafür die bereits gegebene Rekursionsvorschrift \(f_n = f_{n-1} + f_{n-2}\) mit den Startwerten \(f_0 = 1\) und \(f_1 = 1\).

fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Wenn man mittels :set +s die Laufzeitmessung in GHCi aktiviert und fib n für große n versucht zu berechnen, wird man feststellen, dass das sehr lange dauert. Daher kann man eine alternative Variante implementieren, die drei "Speicherplätze" nutzt und somit ein iteratives Verfahren nachahmt (vgl. Slides).

fib' :: Int -> Int
fib' n = fib_help 1 1 n

fib_help :: Int -> Int -> Int -> Int
fib_help x _ 0 = x
fib_help x y n = fib_help y (x+y) (n-1)

Wir berechnen den Binomialkoeffizienten \(\binom{n}{k} = \frac{n!}{k! \ (n-k)!}\). Man beachte dabei, dass die Integer-Division in Haskell mit der Funktion div erfolgen muss. Man kann die Funktion durch `div` auch in Infixnotation zwischen die Operanten schreiben.

bincoeff :: Int -> Int -> Int
bincoeff n k = fac n ‘div‘ (fac (n-k) * fac k)
    where
        fac n
            | n < 1     = 1
            | otherwise = n * fac (n-1)

1. Produkt einer Liste

   prod :: [Int] -> Int
   prod []     = 1
   prod (x:xs) = x * prod xs

2. eine Liste umkehren

   rev :: [Int] -> [Int]
   rev [] = []
   rev (x:xs) = rev xs ++ [x]

3. Elemente einer Liste löschen

   excl :: Int -> [Int] -> [Int]
   excl _  []    = []
   excl y (x:xs)
       | x == y    = excl y xs
       | otherwise = x : excl y xs

4. Sortierung einer Liste prüfen

   isOrd' :: [Int] -> Bool
   isOrd' [] = True
   isOrd' [x] = True
   isOrd' (x:y:xs) = x <= y && isOrd' (y:xs)

5. (sortierte) Listen zusammenfügen

   merge :: [Int] -> [Int] -> [Int]
   merge [] ys = ys
   merge xs [] = xs
   merge (x:xs) (y:ys)
     | x < y = x : merge xs (y:ys)
     | otherwise = y : merge (x:xs) ys

6. (unendliche) Liste der Fibonacci-Zahlen

   fib :: Int -> Int
   fib 0 = 1
   fib 1 = 1
   fib n = fib (n-1) + fib (n-2)
   
   fib' :: Int -> Int
   fib' i = stack 1 1 i
       where 
           stack f0 f1 0 = f0
           stack f0 f1 i = stack f1 (f0 + f1) (i-1)
   
   fibs :: [Int]
   fibs = fibAppend 0
   where fibAppend x = fib x : fibAppend (x+1)
   
   fibs' :: [Int]
   fibs' = fib_stack 1 1
       where
         fib_stack x y =  x : fib_stack y (x+y)

   Testen kann man diese Funktion beispielsweise mittels take 7 fibs, was uns die ersten sieben Fibonacci-Zahlen zurückgibt. take ist dabei eine Funktion aus der Standard-Bibliothek Prelude vom Typ take :: Int -> [Int] -> [Int], siehe auch hier. Man kann nun zwischen den beiden Varianten fibs und fibs' umschalten und die Laufzeitunterschiede vergleichen.

Die Collatz-Folge ist eine relativ einfach definierte Folge, deren Verhalten aber erstaunlich wenig erforscht ist. Die sogenannte Collatz-Vermutung geht davon aus, dass - egal welchen Startwert man wählt - man irgendwann stets in einen Zyklus \( 1 \to 4 \to 2 \to 1\) kommt. Dementsprechend sind wir in dieser Aufgabe auf der Suche nach dem Index, für den wir in diesen Zyklus einsteigen. Mehr Informationen erfahrt ihr in folgendem Video.

cnext :: Int -> Int
cnext n
    | n `mod` 2 == 0 = n `div` 2
    | otherwise      = 3 * n + 1

ck :: Int -> Int
ck 1 = 1
ck n = 1 + ck (cnext n)

cmax :: Int -> Int
cmax 0 = 0
cmax n = max (cmax (n-1)) (ck n) -- oder cmax (n-1) ‘max‘ ck n
    where max a b
        | a > b     = a
        | otherwise = b

collatz :: Int -> [Int]
collatz 1 = [1]
collatz n = n : collatz (cnext n)

1. Präfix-Test

   isPrefix :: String -> String -> Bool
   isPrefix [] _ = True
   isPrefix _ [] = False
   isPrefix (p:ps) (c:cs) = p == c && isPrefix ps cs

2. Vorkommen eines Patterns zählen

   countPattern :: String -> String -> Int
   countPattern "" "" = 1
   countPattern _  "" = 0
   countPattern ps ccs@(c:cs)
       | isPrefix ps ccs = 1 + countPattern ps cs
       | otherwise       = countPattern ps cs

1. Beispielbaum

   mytree :: BinTree
   mytree = Branch 0 
             ( Nil )
             ( Branch 3 
               ( Branch 1 Nil Nil )
               ( Branch 5 Nil Nil )
             )

2. Test auf Baumgleichheit

   equal :: BinTree -> BinTree -> Bool
   equal Nil              Nil              = True
   equal Nil              (Branch y l2 r2) = False
   equal (Branch x l1 r1) Nil              = False
   equal (Branch x l1 r1) (Branch y l2 r2) = (x == y) && (equal l1 l2) && (equal r1 r2)

3. Schlüssel in einen (Such-)Baum einfügen

   insert :: BinTree -> [Int] -> BinTree
   insert t     [] = t
   insert t (n:ns) = insert t' ns
     where
       t' = insertSingle t n
       insertSingle Nil            n = Branch n Nil Nil
       insertSingle (Branch x l r) n
         | n < x     = Branch x (insertSingle l n) r
         | otherwise = Branch x l                  (insertSingle r n)

4. Levelorder-Traversierung

   unwind :: BinTree -> [Int]
   unwind t = go [t]
     where
         go []                  = []
         go ( Nil           : ts) = go ts
         go ((Branch x l r) : ts) = x : go (ts ++ [l,r])

Produkt der Quadratzahlen aller geraden Elemente einer Liste

f :: [Int] -> Int
f xs = foldr product 1 (map square (filter even' xs))
  where
    even' x = mod x 2 == 0
    square x = x * x
    product x y = x * y

f' :: [Int] -> Int
f' xs = foldr (*) 1 (map (^2) (filter even xs))

f'' :: [Int] -> Int
f'' = foldr (*) 1 . map (^2) . filter even

f''' :: [Int] -> Int
f''' = foldr (*) 1 . map (^2) . filter ((== 0) . (`mod` 2))

Hinweise: In Haskell werden Funktionen, die in Infix (also zwischen den Argumenten, z.B. +, -, /, ==, &&) benutzt werden, in Klammern notiert (z.B. (+) :: Int -> Int -> Int). D.h. Operatoren werden wie alle anderen Funktionen behandelt, wenn man sie klammert, z.B. in (+) 2 1 == 3. Andere Funktionen können auch Infix benutzt werden, indem sie durch Backticks `...` umgeben werden, z.B. 5 `mod` 2 == 1 statt mod 5 2 == 1. Mittels partieller Applikation kann man bei Infixfunktionen einen Wert an den zweiten (rechten) Operanden binden, so ist `mod` 2 beispielsweise eine Funktion, die für alle Eingabewerte den Restbetrag der Division durch 2 berechnet. Der Operator . ist die Funktionskomposition, also berechet (== 0) . (`mod` 2) zuerst den Restbetrag der Division durch 2 und testet diesen Wert dann der Gleichheit mit 0. Die entstehende Funktion gibt also genau für alle geraden Eingabewerte den Wert True zurück.

Liste von links falten

foldleft :: (Int -> Int -> Int) -> Int -> [Int] -> Int
foldleft f x []     = x
foldleft f x (y:ys) = foldleft f (f x y) ys

Die Funktion ist als foldl in der Standarbibliothek Prelude enthalten.

1. Beispielbaum

   mytree :: Tree Char
   mytree = Node ’a’ [ 
               Node ’b’ [ Node ’c’ [], Node ’d’ [] ] ,
               Node ’e’ [ Node ’f’ [] ],
               Node ’g’ []
             ]

2. Baum auf ungerade Anzahl an Kindern testen

   oddTree :: Tree a -> Bool
   oddTree (Node _ []) = True
   oddTree (Node _ ts) = oddTrees ts && (length ts ‘mod‘ 2 == 1)
     where 
       oddTrees :: [Tree a] -> Bool
       oddTrees []       = True
       oddTrees (t : ts) = oddTree t && oddTrees ts

3. Pre-Order-Traversierung

   preOrder :: Tree a -> [a]
   preOrder (Node x ts) = x : preOrderTrees ts
     where
       preOrderTrees []       = []
       preOrderTrees (t : ts) = preOrder t ++ preOrderTrees ts
     
   -- alternativ mit Prelude:
   preOrder :: Tree a -> [a]
   preOrder (Node x ts) = x : concatMap preOrder ts

Achtung: die Zeilenangaben in den SLD-Refutationen können zwischen Übungsnotizen und Folien sowie den Lösungen hier abweichen.

1. Abbildung der Kantenrelation des gegebenen Graphen durch ein Prädikat edge

   edge(1, 4).
   edge(1, 2).
   edge(3, 2).
   edge(4, 3).
   edge(1, 1).

2. Pfade als zweistelliges Prädikt path

   path(U, U).
   path(U, W) :- edge(U, V), path(V, W).

3. SLD-Refutationen für das Goal ?- path(4, X).

              ?- path(4,X).
   { X = 4 }  ?- .                          % 7 

              ?- path(4,X).
              ?- edge(4,W), path(W,X).     % 8
   { W = 3 }  ?- path(3,X).                % 5
   { X = 3 }  ?- .                         % 6 

              ?- path(4,X).
              ?- edge(4,W), path(W,X).     % 8 
   { W = 3 }  ?- path(3,X).                % 5
              ?- edge(3,U), path(U,X).     % 8 
   { U = 2 }  ?- path(2,X).                % 4
   { X = 2 }  ?- .                         % 7 

   Damit ist also \( X \in \{ 2,3,4 \} \).

1. Prädikat even, das alle geraden Zahlen enthält

   even(0).
   even(s(s(N))) :- even(N).

2. Prädikt div2, dass alle Paare \( ( n, \lfloor \frac n 2 \rfloor ) \) enthält

   div2(0, 0).
   div2(s(0), 0).
   div2(s(s(N)), s(M)) :- div2(N, M).

3. SLD-Refutation für das Goal ?- div2(<3>, <1>).

   ?- div2(<3>, <1>).
   ?- div2(<1>, 0)           % 12
   ?- .                      % 11 

Achtung: die Zeilenangaben in den SLD-Refutationen können zwischen Übungsnotizen und Folien sowie den Lösungen hier abweichen.

1. Prüfen der Teillisteneigenschaft durch ein Prädikat sublist

   nat (0).
   nat(s(X)) :- nat(X).
   
   listnat ([]).
   listnat ([X|XS]) :- nat(X), listnat(XS).
   
   prefix([]    , Ys )    :- listnat(Ys).
   prefix([X|Xs], [X|Ys]) :- nat(X), prefix(Xs, Ys).
   
   sublist(Xs   , [Y|Ys]) :- nat(Y), sublist(Xs, Ys).
   sublist(Xs   , Ys )    :- prefix(Xs, Ys).

2. SLD-Refutationen für das Goal ?- sublist([<4>|XS], [<5>, <4>, <3>]).

                   ?-  sublist ([<4>|Xs], [<5>, <4>, <3>]).
                   ?-  nat(<5>), sublist ([<4>|Xs], [<4>, <3>]). % 6
                   ?-* nat(0), sublist ([<4>|Xs], [<4>, <3>]).   % 2
                   ?-  sublist ([<4>|Xs], [<4>, <3>]).           % 1
                   ?-  prefix ([<4>|Xs], [<4>, <3>]).            % 7
                   ?-  nat(<4>), prefix(Xs , [<3>]).             % 10
                   ?-* nat(0), prefix(Xs , [<3>]).               % 2
                   ?-  prefix(Xs , [<3>]).                       % 1
   {Xs = []}       ?-  listnat ([<3>]).                          % 9
                   ?-  nat(<3>), listnat ([]).                   % 5
                   ?-* nat(0), listnat ([]).                     % 2
                   ?-  listnat ([]).                             % 1
                   ?-  .                                         % 4

                   ?-  sublist ([<4>|Xs], [<5>, <4>, <3>]).
                   ?-  nat(<5>), sublist ([<4>|Xs], [<4>, <3>]). % 6
                   ?-* nat(0), sublist ([<4>|Xs], [<4>, <3>]).   % 2
                   ?-  sublist ([<4>|Xs], [<4>, <3>]).           % 1
                   ?-  prefix ([<4>|Xs], [<4>, <3>]).            % 7
                   ?-  nat(<4>), prefix(Xs , [<3>]).             % 10
                   ?-* nat(0), prefix(Xs , [<3>]).               % 2
                   ?-  prefix(Xs , [<3>]).                       % 1
   {Xs=[<3>|Xs1]}  ?-  nat(<3>), prefix(Xs1 , []).               % 10
                   ?-* nat(0), prefix(Xs1 , []).                 % 2
                   ?-  prefix(Xs1 , []).                         % 1
   {Xs1 = []}      ?-  listnat ([]).                             % 9
                   ?-  .                                         % 4

1. Evaluierung eines binären Termbaums mit dem Prädikat eval

   sum(0, Y, Y) :- nat(Y).
   sum(s(X), Y, s(S)) :- sum(X, Y, S).
   
   eval( X         , X ) :-  nat(X).
   eval( plus (L,R), X ) :-  eval(L, LE), eval(R, RE), sum(LE, RE,  X).
   eval( minus(L,R), X ) :-  eval(L, LE), eval(R, RE), sum(RE,  X, LE).

2. SLD-Refutation für das Goal ?- insert(<t1>, <t2>, X).

   Ausführlichere Hinweise zu Anschauung des Prädikats insert finden sich in den Slides.

   1.                            ?-  insert(<t1>, <t2>, X).
      {X = tree(a, LT1, RT1)}    ?-  insert(tree(b, nil, nil), <t2>, LT1), 
                                     insert(tree(v, nil, nil), <t2>, RT1).   % 6
      {LT1 = tree(b, LT2, RT2)}  ?-  insert(nil , <t2>, LT2), 
                                     insert(nil, <t2>, RT2), 
                                     insert(tree(v, nil, nil), <t2>, RT1).   % 6
      {LT2 = nil, RT2 = nil}     ?-* insert(tree(v, nil, nil), <t2>, RT1).   % 4
      {RT1 = <t2>}               ?-  istree(<t2>).                           % 5
                                 ?-* istree(nil), istree(nil), istree(nil).  % 2
                                 ?-* .                                       % 4

   2.                            ?-  insert(<t1>, <t2>, X).
      {X = tree(a, LT1, RT1)}    ?-  insert(tree(b, nil, nil), <t2>, LT1), 
                                     insert(tree(v, nil, nil), <t2>, RT1).   % 6
      {LT1 = tree(b, LT2, RT2)}  ?-  insert(nil , <t2>, LT2), 
                                     insert(nil, <t2>, RT2), 
                                     insert(tree(v, nil, nil), <t2>, RT1).   % 6
      {LT2 = nil, RT2 = nil}     ?-* insert(tree(v, nil, nil), <t2>, RT1).   % 4
      {RT1 = tree(v, LT3, RT3)}  ?-  insert(nil, <t2>, LT3),
                                     insert(nil, <t2>, RT3).                 % 6
      {RT3 = nil, LT3 = nil}     ?-* .                                       % 4