\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{verbatim}

\newcommand{\ZETTELNUMMER}{9}
% TODO
\newcommand{\ABGABEDATUM}{am 5. Januar 2016 bis 12 Uhr in die
Tutorenf\"acher}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\B}{\mathbb{B}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Informatik A}\hfill WiSe 2015/16 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

Alle Aufgaben auf diesem Zettel sind Zusatzaufgaben.
Frohe Weihnachten!

\vskip 0.5cm

\begin{description}

\AUFGABE{Falten}{10 Zusatzpunkte}

Implementieren Sie die folgenden Funktionen mit Hilfe 
von Lambda-Ausdr\"ucken und der Funktion
\texttt{falte}/\texttt{foldr} (VL 15). 

\emph{Hinweis}: Man kann \texttt{if$\dots$then$\dots$else$\dots$} in 
Lambda-Ausdr\"ucken verwenden.
\begin{enumerate}
  \item Gegeben eine Liste, berechne ihre L\"ange.
    \begin{center}
      \texttt{laenge:: [a] -> Int}
    \end{center}
  \item \texttt{wendeAn}/\texttt{map} aus der Vorlesung.
    \begin{center}
      \texttt{wendeAn:: (a -> b) -> [a] -> [b]}
    \end{center}
  \item \texttt{siebe}/\texttt{filter} aus der Vorlesung.
    \begin{center}
      \texttt{siebe:: (a -> Bool) -> [a] -> [a]}
    \end{center}
  \item Sei \texttt{f} eine Funktion mit Signatur 
  \texttt{f:: a -> Bool} und \texttt{xs} eine Liste  vom Typ 
  \texttt{a}, liefere genau dann \texttt{True}, 
  falls \texttt{f} f\"ur \emph{alle} Elemente in \texttt{xs} 
   den Wert \texttt{True}
    ergibt.
    \begin{center}
      \texttt{fuerAlleWahr:: (a -> Bool) -> [a] -> Bool} 
    \end{center}
\end{enumerate}


\AUFGABE{Algebraische Datentypen: Mengen}{10 Zusatzpunkte}

In der Vorlesung hatten wir den Datentyp \texttt{Liste} definiert. 
Definieren Sie jetzt einen Datentyp, der eine 
\emph{Menge} darstellt.
\begin{center}
  \texttt{data Menge a = Menge [a]}
\end{center}

\begin{enumerate}
\item Deklarieren Sie den Typ \texttt{Menge} als Instanz der Typklasse
  \texttt{Show} und implementieren Sie die Funktion
  \begin{center}
    \texttt{show :: Show a => Menge a -> String}
  \end{center}
Zum Beispiel soll die Ausgabe einer Menge 
\texttt{Menge [1,5,6]} folgendes Format haben:
\texttt{\{1,5,6\}}.
\item Implementieren Sie die Funktion
  \begin{center}
    \texttt{vonListe :: Eq a => [a] -> Menge a}
  \end{center}
  die aus einer Liste vom Typ \texttt{a} eine Menge erstellt. Dabei 
  sollen Duplikate aus der Liste entfernt werden. Beispielsweise 
  soll \texttt{vonListe [1,2,2,3,1]} das Ergebnis \texttt{Menge [1,2,3]} 
  zur\"uckgeben. Im Folgenden
  k\"onnen Sie davon ausgehen, dass alle Werte des Typs \texttt{Menge}  
  durch die
  Funktion \texttt{vonListe} erzeugt wurden.

\item Deklarieren Sie den Typ \texttt{Menge} als Instanz der Typklasse
  \texttt{Eq} und implementieren Sie die Funktion 
  \begin{center}
   \texttt{(==) :: Eq a => Menge a -> Menge a -> Bool}
  \end{center}
  Dabei soll
  \texttt{Menge xs == Menge ys} genau dann wahr sein, wenn \texttt{xs} und
  \texttt{ys} dieselben Elemente enthalten (die Reihenfolge spielt dabei 
  keine
  Rolle!). Beispielsweise soll \texttt{Menge [1,5,2] == Menge [2,1,5]} 
  wahr sein,
  w\"ahrend \texttt{Menge [1,5,2] == Menge [1,5]} falsch ist.

\item Deklarieren Sie den Typ \texttt{Menge} als Instanz der Typklasse
  \texttt{Ord} und implementieren Sie die Funktion
  \begin{center}
    \texttt{(<=) :: Eq a => Menge a -> Menge a -> Bool}
  \end{center}

  Dabei soll \texttt{Menge xs <= Menge ys} genau dann wahr sein, wenn
  \texttt{xs} eine Teilmenge von \texttt{ys} ist (die Reihenfolge spielt 
  wieder keine Rolle).
\end{enumerate}


\AUFGABE{Produkte der anderen Elemente}{10 Zusatzpunkte}

Sei $[a_1,\dots,a_n]\texttt{::[Int]}$. Wir wollen 
eine Liste $[b_1,\dots,b_n]\texttt{::[Int]}$ finden mit
\begin{align*}
  b_1 & = a_2 \cdot \dots \cdot  a_n \\
  \vdots &  \\
  b_i & = a_1 \cdot \dots \cdot a_{i-1} \cdot a_{i+1} \cdot \dots 
  \cdot  a_n \\
  \vdots &  \\
  b_n & = a_1 \cdot \dots \cdot  a_{n-1}.
\end{align*}
In der Vorlesung hatte wir angefangen, dazu einen Algorithmus zu
implementieren, der \texttt{scanl} und \texttt{scanr} benutzt.
Vervollst\"andigen Sie die fehlenden Schritte. Den Code aus der Vorlesung
k\"onnen Sie auf der Veranstaltungswebsite finden.

\begin{enumerate}
\item Implementieren Sie die Funktion
  \begin{center}
    \texttt{produkteRechts:: [Tripel] -> [Tripel]}
  \end{center}
  analog zur Funktion \texttt{produkteLinks} aus der Vorlesung. Verwenden 
  Sie jedoch \texttt{scanr} anstatt \texttt{scanl}.
  Diese ist wie folgt definiert.

  \begin{tabular}{ll}
    \multicolumn{2}{l}{\texttt{scanr:: (a->b->b) -> b -> [a] -> [b]}}  \\
    \texttt{scanr \_ x0 []} & \texttt{= [x0]} \\
    \texttt{scanr f x0 (x:xs)} & \texttt{= (f x y) : (y:ys)} \\
                               & \texttt{where (y:ys) = scanr f x0 xs} 
  \end{tabular}

  Um eine Intuition f\"ur \texttt{scanr} zu bekommen, bietet es sich 
  an, die Ausgabe von \texttt{scanr (*) 4 [1,2,3]} zu betrachten.

  \emph{Hinweis:} Bei
  \texttt{produkteLinks} hatten wir bei \texttt{scanl} f\"ur \texttt{x0} das
  erste Element $a_1$ der Liste gew\"ahlt, und f\"ur \texttt{(x:xs)} den 
  Rest der
  Liste, also $[a_2,\dots,a_n]$. Bei \texttt{scanr} verh\"alt es sich
  spiegelverkehrt.
\item
  Implementieren Sie die Funktion
  \begin{center}
    \texttt{multLR:: [Tripel] -> [Int]},
  \end{center}
  die jeden Tripel \texttt{(a,b,c)} in einer Liste auf das Produkt 
  \texttt{a*c}
  abbildet.
\item Implementieren Sie die Funktion
  \begin{center}
    \texttt{produkte :: [Int] -> [Int]}, 
  \end{center}
  mit Hilfe von \texttt{tripel}, \texttt{produkteLinks},
  \texttt{produkteRechts} und \texttt{multLR}.
\end{enumerate}
\end{description}

\noindent
Geben Sie immer alle Signaturen an und machen Sie geeignete Testl\"aufe.
Versehen Sie Ihr Skript mit geeigneten Kommentaren.
\end{document}
