\input{../../../texPrelude}


\fancyhead[CO,CE]{Übungsaufgaben zum Haskell-Schnellkurs}
\fancyhead[LO,LE]{Jost Berthold / Björn Metzler}

\newcommand{\ignore}[1]{}

\ignore{
Diese Datei lässt sich in Hugs/GHC laden und Ausführen, oder Latex
erstellt den Aufgabenzettel (geeignete CODE-Umbegung nötig).

\begin{code}

module Uebungen
  where

import System
import Char

\end{code}
}

\section*{Übungsaufgaben}

Für die Übungsaufgaben sehr nützlich ist eine ausführliche 
Dokumentation der \cd{Prelude}-Funktionen, Sie finden eine 
unter \cd{http://www.cs.uu.nl/~afie/haskell/tourofprelude.html}.

\subsection{Fallende Faktorielle}
Die {\em fallende Faktorielle} aus der Kombinatorik verallgemeinert die 
Fakultätsfunktion. Sie ist wie folgt definiert:
$ \mbox{\tt factorial n k} = n^{\underline k} = 
   \prod_{j=0}^{k-1} (n-j) = n \cdot (n-1) \cdot \ldots (n-k+1)$.
Insbesondere ist $n^{\underline 0} = 1$.

\begin{enumerate}
 \item Definieren Sie diese Funktion {\em rekursiv} in Haskell.
 \item Geben Sie eine zweite Definition an, die mit einer {\em Faltungsfunktion} arbeitet.
 \item Geben Sie eine dritte Definition an, welche mit jeweils zwei rekursiven Aufrufen arbeitet.
\end{enumerate}

\subsection{Heap-Sort (Variante mit Braun-Bäumen)}
Mit Hilfe der sog. Braun-Bäume kann eine Variante von Heap-Sort
implementiert werden.  

{\bf Definitionen} Für einen Binärbaum H sei $\# H$ die Zahl seiner
inneren Knoten.  
\begin{itemize} 
  \item Ein leerer Binärbaum ist ein {\em Braun-Baum} 
  \item Ein nicht-leerer Binärbaum ist ein {\em Braun-Baum}, wenn 
    die beiden Kindbäume $h_l$ und $h_r$ seiner Wurzel Braun-Bäume sind 
    und gilt: $\# h_l - \# h_r \in \{0,1\}$.\\

Um eine Heap-Struktur {\em Braun-Heap} zu erhalten, fügen wir hinzu:
  \item[\bf Ordnung] Das enthaltene Element in einem Knoten eines Braun-Heaps
      ist stets {\em kleiner} (oder allenfalls gleich) als die Elemente in 
      beiden Sub-Heaps des Knotens.
\end{itemize}
{\bf Unterschiede zu Heap-Sort:}\\ Im originalen Heap-Sort ist der Heap ein 
{\em vollständiger} Binärbaum und die Elemente darin {\em absteigend} geordnet.

In der Datei \file{HeapSort-incomplete.hs} sind die Datenstruktur und 
das Sortierprinzip bereits aufgeschrieben. 
\begin{enumerate}
 \item Ergänzen Sie die fehlenden Funktionen, so dass die Funktion \cd{heapsort} 
       korrekt sortiert.
 \item Implementieren Sie zu Vergleichszwecken eine Quicksort-Funktion.\\
        {\bf Hinweis:} Am einfachsten geht das mit sog. {\em List-Comprehensions}:
\begin{xcode}
erzeugeListe alteListe = [ f x | x <- alteListe, praedikat x ] 
	   where f x         = ... -- Elemente konvertieren
		 praedikat x = ... -- filtern der Elemente von "alteListe"
\end{xcode}
Beachten Sie, dass die vorbereitete Datei mit der Typklasse \cd{Ord} arbeitet, 
anstatt den Typ der zu sortierenden Elemente vorzugeben.
 \item Definieren Sie einen eigenen Datentyp (z.B. Farben) und eine Ordnung 
   darauf, so dass Sie Listen von Elementen Ihres Typs mit Heapsort sortieren können.
\end{enumerate}

\subsection{Caesar-Code}
Der sog. Caesar-Code ist eine einfache Verschlüsselung (die nur mit zufälligen 
Schlüsseln sicher ist). Die Buchstaben im Klartext werden um so viele Zeichen des 
Alphabets verschoben, wie der zugehörige Buchstabe im Schlüssel angibt.\\
Beispiel: 
$\begin{array}{rcl}
\mbox{Klartext }  & :& \mbox{\tt Geheim}\\
\mbox{Schlüssel  ``key''} & :&\mbox{\tt keykey}\\
\mbox{Chiffre} & :& \mbox{2JaPNf}
\end{array}$ $G+k=2,e+e=J,\ldots$.

Implementieren Sie eine Caesar-Code-Verschlüsselung mit beliebigen Schlüssellängen.
Benutzen Sie Funktionen höherer Ordnung für die Listenverarbeitung.\\
Als Alphabet können Sie entweder die ersten 128 Ascii-Zeichen benutzen, oder Sie 
definieren ein eigenes Alphabet und konvertieren nur mit den Zeichen darin.

\end{document}

{-

ab hier kommen die Lösungen:
----------------------------
-}
\begin{code}

---------------------------------
-- fallende Faktorielle
factorial1 :: Int -> Int -> Int 
factorial1 n k  = if k == 0 then 1 
                            else n * factorial1 (n-1) (k-1)
-- oder:
factorial1' n k | k == 0 = 1
                | otherwise = (n-k+1) * factorial1' n (k-1)

factorial2 :: Int -> Int -> Int 
factorial2 n k = foldl (*) 1 (take k [n,(n-1)..]) 
-- Start mit n, nimm k Faktoren aus der Liste, Faltung

factorial3 :: Int -> Int -> Int
factorial3 n k
        | k == 0    =  1
        | k == 1    =  n
        | otherwise =  let mid  = (n+n-k) `div` 2
                           newk = k `div` 2
                       in  factorial3 n (k-newk) * factorial3 mid newk

-- Heapsort: siehe Extra-Datei Heapsort.*

--caesar-code, mit Hilfe des Typs Char und der Klasse Num:

instance Num Char where
    (+) c1 c2 = chr ((ord c1 + ord c2) `mod` 128) -- modulo-Addition bis 128
    (-) c1 c2 = chr ((ord c1 - ord c2) `mod` 128)

data Mode = ENCODE | DECODE

-- Codier- und Decodierfunktion
caesar :: Mode -> String -> String -> String
caesar mode s key = case (d mode) of 
			       Just f -> zipWith f s (concat (repeat key))
			       Nothing -> "Invalid Mode"
		  where  d ENCODE = Just (+)
			 d DECODE = Just (-)
			 d _      = Nothing

\end{code}