i1rekzahlen.tex

% Diese Datei ist Teil des Buchs "Schreibe Dein Programm!"
% Das Buch ist lizenziert unter der Creative-Commons-Lizenz
% "Namensnennung - Weitergabe unter gleichen Bedingungen 4.0 International (CC BY-SA 4.0)"
% https://creativecommons.org/licenses/by-sa/4.0/deed.de

\chapter{Natürliche Zahlen}
\label{cha:recursion-numbers}

In diesem Kapitel geht es um Funktionen, die etwas zählen und sich
dementsprechend mit Zahlen beschäftigen.  Wir haben schon eine Reihe
von Programmen gesehen, die mit Zahlen rechnen, aber Zählen ist etwas
besonderes und verdient deshalb ein eigenes Kapitel mit eigener
Konstruktionsanleitung.

\section{Zahlen, die zählen}

\mentioncode{natuerliche-zahlen/natural.rkt}
%
Du kennst bestimmt aus dem Mathematikunterricht die
\textit{Potenz}\index{Potenz} einer Zahl (der
\textit{Basis}\index{Basis}) $b$ zu einem
\textit{Exponenten}\index{Exponent} $e$:
%
\begin{displaymath}
  b^e
\end{displaymath}
%
Uns interessieren hier Exponenten, die ganze Zahlen ab 0 sind.  Für
solche Exponenten ist die Potenz folgendermaßen definiert:
%
\begin{displaymath}
  b^e \deq \underbrace{b \times \ldots \times b}_{e\textrm{-mal}}
\end{displaymath}
%
Der Exponent $e$ muss also eine natürliche Zahl\index{natürliche Zahl}
sein.\footnote{Spitzfindige Leser können anmerken, dass in manchen
  Lehrbüchern die natürlichen Zahlen mit 1 beginnen, aber wir halten
  uns an DIN~5473, und da ist die 0 mit dabei.}
  
  Umgangssprachlich sind natürliche Zahlen gerade die Zahlen, die
Gegenstände zählen.  In unserer Intuition sind die natürlichen Zahlen
einfach auf einem Zahlenstrahl angeordnet und bilden eine Reihe.  Für
das Programmieren ist das aber wenig hilfreich.  Viel mehr können wir
mit der folgenden Datendefinition anfangen:\label{page:datendefinition-N}
%
\begin{lstlisting}
; Eine natürliche Zahl ist eine der folgenden:
; - 0
; - der Nachfolger einer natürlichen Zahl
\end{lstlisting}
%
In dieser Definition findet man alte Bekannte wieder: Es handelt sich
um eine Fallunterscheidung, und der zweite Fall enthält einen
Selbstbezug.

Dir mag der Begriff "<Nachfolger"> etwas befremdlich erscheinen: Der
Nachfolger einer Zahl ist einfach nur die Zahl "<plus 1">.  Weil der
Nachfolger im Zusammenhang mit natürlichen Zahlen eine besondere
Bedeutung hat, spendieren wir ihm zunächst eine eigene Hilfsfunktion:
%
\indexvariable{successor}
\begin{lstlisting}
; Nachfolger einer Zahl
(: successor (natural -> natural))

(define successor
  (lambda (n)
    (+ n 1)))
\end{lstlisting}
%
Wo ein Nachfolger ist, muss es auch einen Vorgänger geben, und der
zieht Eins ab:
%
\indexvariable{predecessor}
\begin{lstlisting}
; Vorgänger einer Zahl
(: predecessor (natural -> natural))

(define predecessor
  (lambda (n)
    (- n 1)))
\end{lstlisting}
%
Allerdings haben wir bei dieser Definition etwas geschummelt, weil der
Vorgänger nur für die natürlichen Zahlen funktioniert, welche die
Nachfolger anderer natürlicher Zahlen sind~-- also für sogenannte
\textit{positive} natürliche Zahlen\index{positive natürliche Zahlen}.
Die Signatur kann das nicht zum Ausdruck bringen, da es keine
eingebaute Signatur dafür gibt.  Aber wir können eine Verzweigung
entsprechend der Datendefinition einbauen, um die Funktion vor
Missbrauch zu schützen:
%
\begin{lstlisting}
(define predecessor
  (lambda (n)
    (cond
      ((zero? n)
       (violation "0 does not have a predecessor"))
      ((positive? n)
       (- n 1)))))
\end{lstlisting}
%
Du siehst in der Funktionsdefinition die beiden eingebauten Funktionen
\lstinline{zero?}\indexvariable{zero?} und
\lstinline{positive?}\indexvariable{positive?}, welche die
beiden Fälle der Datendefinition der natürlichen Zahlen unterscheiden.

Zurück zur eigentlichen Aufgabe, der Potenz.  So könnten
Kurzbeschreibung, Signatur und zwei Tests aussehen:\label{function:power}
%
\begin{lstlisting}
; Potenz einer Zahl berechnen
(: power (number natural -> number))

(check-expect (power 5 0) 1)
(check-expect (power 5 3) 125)
\end{lstlisting}
%
Als Nächstes ist das Gerüst dran:
%
\indexvariable{power}
\begin{lstlisting}
(define power
  (lambda (base exponent)
    ...))
\end{lstlisting}
%
Für den Rumpf können wir eine Schablone aus der Datendefinition
für \lstinline{exponent} ableiten, das ist ja die natürliche
Zahl.  Die Datendefinition für natürliche Zahlen ist eine
Fallunterscheidung mit zwei Fällen, dementsprechend brauchen wir eine
Verzweigung mit zwei Zweigen:
%
\begin{lstlisting}
(define power
  (lambda (base exponent)
    (cond
      ((zero? exponent) ...)
      ((positive? exponent) ...))))
\end{lstlisting}
%
Im zweiten Fall der Datendefinition steckt außerdem eine
Selbstreferenz, wir schreiben also noch einen rekursiven Aufruf in die
Schablone:
%
\begin{lstlisting}
(define power
  (lambda (base exponent)
    (cond
      ((zero? exponent) ...)
      ((positive? exponent)
       ... (power base (predecessor exponent)) ...))))
\end{lstlisting}
%
Beim ersten Fall~--Exponent $0$~-- muss als Potenz $1$ herauskommen, das
neutrale Element bezüglich der Multiplikation: Das ist ja nichts
anderes, als die Zahlen der leeren Liste zu multiplizieren.  (Siehe
dazu auch Seite~\pageref{page:neutrales-element} in
Abschnitt~\ref{page:neutrales-element}.)
Für den anderen Fall ist das Ergebnis des rekursiven Aufruf die Potenz
von \lstinline{base} mit dem Vorgänger von \lstinline{exponent} als
Exponent.  Damit wir als Ergebnis \lstinline{base} mit sich selbst
\lstinline{exponent}-mal multipliziert bekommen, fehlt noch eine
Multiplikation mit \lstinline{base}:
%
\begin{lstlisting}
(define power
  (lambda (base exponent)
    (cond
      ((zero? exponent) 1)
      ((positive? base)
       (* base (power base (predecessor exponent)))))))
\end{lstlisting}
%
Fertig!

Der Begriff des Vorgängers ist hier eher im Weg: Er passt zwar gut zur
Verwendung des Worts "<Nachfolger"> in der
Datendefinition. \lstinline{(predecessor exponent)} ist aber hier das
gleiche ist wie \lstinline{(- exponent 1)}, und entsprechend werden
wir auch in der Schablone direkt \lstinline{(- ... 1)} statt
\lstinline{predecessor} verwenden.
\begin{aufgabe}
  Die Funktion \lstinline{predecessor} hat zwei Zweige: Warum ist der
  Aufruf in \lstinline{power} immer gleichbedeutend zu
  \lstinline{(- exponent 1)}~-- was ist mit dem anderen Zweig?
\end{aufgabe}


\begin{konstruktionsanleitung}{Natürliche Zahlen als Eingabe: Schablone}
  \label{ka:nats-eingabe-schablone}
  Eine Schablone für eine Funktion, die eine natürliche Zahl akzeptiert, sieht
folgendermaßen aus:
%
\begin{lstlisting}
(define |\(f\)|
  (lambda (|\ldots| |\(\mathit{n}\)| |\ldots|)
    (cond
      ((zero? |\(\mathit{n}\)|) |\ldots|)
      ((positive? |\(\mathit{n}\)|)
       |\ldots|
       (|\(f\)| ... (- |\(\mathit{n}\)| 1) ...)
       |\ldots|
       ))))
\end{lstlisting}
  
\end{konstruktionsanleitung}

\section{Natürliche Zahlen und Listen}
\label{func:copies}

\mentioncode{natuerliche-zahlen/list.rkt}
%
Zwischen natürlichen Zahlen und Listen besteht eine enge Beziehung:
Die Datendefinition für natürliche Zahlen entspricht in ihrer Struktur
der von Listen.  Die Funktion~\lstinline{list-length} in
Abschnitt~\ref{page:list-length} auf Seite~\pageref{page:list-length}
macht aus einer Liste eine natürliche Zahl.  Das geht auch umgekehrt:
%
\begin{lstlisting}
; Liste aus Kopien eines Werts erzeugen
(: copies (natural %element -> (list-of %element)))

(check-expect (copies 4 23) (list 23 23 23 23))
(check-expect (copies 5 "Mike")
              (list "Mike" "Mike" "Mike" "Mike" "Mike"))
\end{lstlisting}
%
Die Signatur der Funktion enthält die Signaturvariable \lstinline{%element}, ist also
polymorph und macht klar, dass die Elemente der Liste nur zur Signatur
\lstinline{%element} gehören können.
%
\indexvariable{copies}
\begin{lstlisting}
(define copies
  (lambda (count element)
    ...))
\end{lstlisting}
%
Die Konstruktionsanleitung schlägt folgende Schablone vor:
%
\begin{lstlisting}
(define copies
  (lambda (count element)
    (cond
      ((zero? count) ...)
      ((positive? count)
       ... (copies (- count 1) element) ...)))))
\end{lstlisting}
%
Für den ersten Fall brauchen wir eine Liste mit 0 Elemente.  Im
zweiten Fall liefert der rekursive Aufruf eine Liste mit einem Element
weniger, als wir brauchen. Das ergänzen wir zur fertigen Definition
so:
%
\begin{lstlisting}
(define copies
  (lambda (count element)
    (cond
      ((zero? count)
       empty)
      ((positive? count)
       (cons element
             (copies (- count 1) element))))))
\end{lstlisting}
%
Eine weitere nützliche Funktion akzeptiert die Nummer eines
Listenelementes~-- einen sogenannten \textit{Index}\index{Index}~--
und liefert das Element:
%
\begin{lstlisting}
; Nummeriertes Element aus einer Liste holen
(: nth ((list-of %element) natural -> %element))

(check-expect (nth (list 1 2 3 4 5) 0) 1)
(check-expect (nth (list 1 2 3 4 5) 2) 3)
\end{lstlisting}
%
Wir sollten uns noch überlegen, was passieren soll, wenn es den Index in der Liste gar
nicht gibt.  Die Funktion kann kein sinnvolles Ergebnis liefern, das
zur Signatur passt~-- es muss ja ein Element der Liste herauskommen.
Wir können also nur einen Fehler anzeigen.
Daraus wird folgender Testfall:
%
\begin{lstlisting}
(check-error (nth (list 1 2 3 4 5) 5))
\end{lstlisting}
%
Das Gerüst der Funktion sieht folgendermaßen aus:
%
\begin{lstlisting}
(define nth
  (lambda (list index)
    ...))
\end{lstlisting}
%
Wir können die
Schablone für Listen als Eingabe benutzen oder die für natürliche
Zahlen.  Hier ist der Index federführend~-- beim
zweitem Element einer tausendelementigen Liste 
ist die Länge irrelevant.  Wir halten uns also an die
Konstruktionsanleitung für natürliche Zahlen:
%
\begin{lstlisting}
(define nth
  (lambda (list index)
    (cond
      ((zero? index) ...)
      ((positive? index)
       ... (nth (rest list) (- index 1)) ...))))
\end{lstlisting}
%
Im ersten Fall ist der Index $0$, also das erste Element 
gefragt.  Im zweiten Fall liefert der rekursive Aufruf im Rest der
Liste das Element an Stelle \lstinline{(- index 1)}, also
das \lstinline{index}-te Element in \lstinline{list}.  Die
Funktion sieht so aus:
%
\indexvariable{nth}
\begin{lstlisting}
(define nth
  (lambda (list index)
    (cond
      ((zero? index) (first list))
      ((positive? index)
       (nth (rest list) (- index 1))))))
\end{lstlisting}
%
Alle Testfälle laufen bereits durch~-- obwohl wir
für den Fehlerfall gar nichts programmiert haben.
\begin{aufgabeinline}
  Werte mit dieser Definition folgenden Ausdruck aus:
\begin{lstlisting}
(nth (list 1 2 3 4 5) 5)
\end{lstlisting}
\end{aufgabeinline}
%
Die Fehlermeldung ist zwar technisch richtig, gibt aber keinen
Aufschluss auf die Ursache des Fehlers.  Das können wir korrigieren,
indem wir doch noch die Schablone für Listen als Eingabe ergänzen und
\lstinline{violation} benutzen.  (Siehe Abschnitt~\ref{sec:violation} auf
Seite~\pageref{sec:violation}.)
%
\begin{lstlisting}
(define nth
  (lambda (list index)
    (cond
      ((empty? list)
       (violation "nth: Die Liste ist nicht lang genug"))
      ((cons? list)
       (cond
         ((zero? index) (first list))
         ((positive? index)
          (nth (rest list) (- index 1))))))))
\end{lstlisting}
%
Fertig!

\section{Andersrum zählen}
\label{sec:andersrum-zaehlen}

\mentioncode{natuerliche-zahlen/count-from.rkt}
%
Wir programmieren noch ein weiteres Beispiel: Zwei Zahlen bestimmen
Unter- und Obergrenze eines Bereichs ganzer Zahlen und wir wollen die
Liste dieser Zahlen generieren.  Die Zahlen zwischen 3 und 7 sind zum
Beispiel 3, 4, 5, 6, 7.

Hier sind Kurzbeschreibung, Signatur und ein Test:
%
\begin{lstlisting}
; Liste aufeinanderfolgender ganzer Zahlen berechnen
(: between (integer integer -> (list-of integer)))

(check-expect (between 3 7) (list 3 4 5 6 7))
\end{lstlisting}
%
Hier ist das Gerüst für die Funktion:
%
\indexvariable{between}
\begin{lstlisting}
(define between
  (lambda (from to)
    ...))
\end{lstlisting}
%
Es ist gar nicht so klar, was für eine Schablone wir anwenden sollten,
um die Funktion zu vervollständigen: In der Signatur steht
\lstinline{integer}, die Eingaben können also auch negative Zahlen sein,
mithin keine natürlichen Zahlen.  Die Konstruktionsanleitung für
natürliche Zahlen ist also nicht direkt anwendbar.  Allerdings geht es
bei der Funktion doch augenscheinlich ums Zählen, irgendwie sind also
doch natürliche Zahlen im Spiel.

Wir können uns der Lösung nähern, indem wir zählen, wieviele Elemente
die Ausgabe-Liste hat.  Am Testfall sind es fünf Elemente, allgemein
ist das eins mehr als die Differenz der beiden Eingabezahlen~-- und
das ist immer eine natürliche Zahl.

Wir können die Aufgabe also leicht umformulieren: Nicht "<die Zahlen
zwischen 3 und 7"> generieren, sondern "<die 5 Zahlen ab 3">.  Dafür
können wir eine eigene Funktion schreiben:
%
\begin{lstlisting}
; Aufeinanderfolgende Zahlen ab einer Zahl generieren
(: count-from (integer natural -> (list-of integer)))

(check-expect (count-from 3 5) (list 3 4 5 6 7))
\end{lstlisting}
%
Das Gerüst ist wie folgt:
%
\indexvariable{count-from}
\begin{lstlisting}
(define count-from
  (lambda (from count)
    ...))
\end{lstlisting}
%
Da \lstinline{count} eine natürliche Zahl ist, können wir die
entsprechende Schablone anwenden:
%
\begin{lstlisting}
(define count-from
  (lambda (from count)
    (cond
      ((zero? count) ...)
      ((positive? count)
       ... (count-from ... (- count 1)) ...))))
\end{lstlisting}
%
Im ersten Fall sind null Elemente gefragt, da muss das Ergebnis
\lstinline{empty} sein.  Da eine Liste herauskommt, werden wir
im zweiten Fall \lstinline{cons} benutzen, um diese zu
konstruieren.  Außerdem ist das gewünschte erste Element gerade
\lstinline{from}.  Wir können die Schablone also wie folgt
weiterentwickeln:
%
\begin{lstlisting}
(define count-from
  (lambda (from count)
    (cond
      ((zero? count) empty)
      ((positive? count)
       (cons from
             ... (count-from ... (- count 1)) ...)))))
\end{lstlisting}
%
Für den Rest der Ausgabe-Liste brauchen wir eine Liste, die mit der
nächsten Zahl anfängt, also mit \lstinline{(+ from 1)}.  Wenn wir das
als erstes Argument des rekursiven Aufrufs benutzen, ist dieser schon
genau die benötigte Rest-Liste:
%
\begin{lstlisting}
(define count-from
  (lambda (from count)
    (cond
      ((zero? count) empty)
      ((positive? count)
       (cons from
             (count-from (+ from 1) (- count 1)))))))
\end{lstlisting}
%
Nun ist \lstinline{count-from} fertig, aber unsere eigentliche Funktion
\lstinline{between} noch nicht.  Wir können aber \lstinline{count-from}
benutzen, um \lstinline{between} zu realisieren:
%
\indexvariable{between}
\begin{lstlisting}
(define between
  (lambda (from to)
    (count-from from (+ (- to from) 1))))
\end{lstlisting}
%
Fertig!

Vielleicht erscheint Dir umständlich, die Aufgabe erst einmal
umzumodeln auf eine Aufgabe über natürliche Zahlen und dann die zu
bearbeiten.  Geht das nicht "<direkt">? Es geht.

Der Schlüssel zur direkten Lösung ist die Einsicht, dass die
natürliche Zahl in der Aufgabe gerade die Differenz zwischen
\lstinline{from} und \lstinline{to} ist.  Wir können eine
entsprechende Verzweigung so formulieren:
%
\begin{lstlisting}
(define between
  (lambda (from to)
    (cond
      ((= from to) ...)
      ((< from to)
       ... (between ... ...) ...))))
\end{lstlisting}
%
Beim ersten Zweig brauchen wir eine einelementige Liste.  Im zweiten
ist es wieder sinnvoll, zunächst das \lstinline{cons} hinzuschreiben,
weil wir wissen, dass das erste Element \lstinline{from} ist:
%
\begin{lstlisting}
(define between
  (lambda (from to)
    (cond
      ((= from to) ...)
      ((< from to)
       (cons from (between ... ...))))))
\end{lstlisting}
%
Nun können wir die Argumente des rekursiven Aufrufs ergänzen.  Wir
benötigen eine Liste, die mit der nächsten Zahl anfängt und genau wie
gehabt aufhört:
%
\begin{lstlisting}
(define between
  (lambda (from to)
    (cond
      ((= from to) (list from))
      ((< from to)
       (cons from (between (+ from 1) to))))))
\end{lstlisting}
%
Fertig!
Vielleicht fällt Dir bei dieser Aufgabe auf, dass es leicht passieren
kann, dass die ganzen Zahlen "<um eins verrutschen">.  Man könnte zum
Beispiel leicht auf die Idee kommen, im ersten Zweig statt
\lstinline{(list from)} einfach \lstinline{empty} hinzuschreiben.  Es
ist deswegen sinnvoll, beim Programmieren von Funktionen über
natürliche und ganze Zahlen genau hinzuschauen, ob sie korrekt sind.

\section{Exkurs: Potenz optimieren}

\mentioncode{natuerliche-zahlen/power.rkt}
%
Wir kehren in diesem Abschnitt noch einmal zur Potenz zurück.  Mit
einem Trick können wir nämlich den Rechenaufwand reduzieren: Zum
Beispiel können wir $3^{10}$ folgendermaßen berechnen:
%
\begin{displaymath}
  3^{10}   = 3^5 \times 3^5
\end{displaymath}
%
Wir müssen also nicht mühsam die 3 zehnmal mit sich selbst
multiplizieren, es reicht, $3^5$ zu berechnen und mit sich selbst zu
multiplizieren.  Bei ungeraden Exponenten geht der Trick auch, wir müssen aber einmal extra
mit der Basis multiplizieren:
%
\begin{displaymath}
  3^9   = 3^4 \times 3^4 \times 3
\end{displaymath}
%
Diesen Trick können wir auch zu einem Programm machen.  Wir nennen die
Funktion der Einfachheit halber \lstinline{power2}, die aber ansonsten
genau wie \lstinline{power} funktionieren soll.  Hier ist das Gerüst:\label{function:power2}
%
\begin{lstlisting}
(define power2
  (lambda (base exponent)
    ...))
\end{lstlisting}
%
In \lstinline{power2} wird nicht mehr direkt gezählt, obwohl der
Exponent immer noch eine natürliche Zahl ist.  Weil nicht gezählt
wird, können wir die Schablone für natürliche Zahlen (wieder) nicht
direkt verwenden.  Allerdings können wir eine alternative
Datendefinition für natürliche Zahlen unterstellen, die Zahlen
halbiert, statt sich (wie die erste Definition) auf den Vorgänger zu beziehen.
%
\begin{lstlisting}
; Eine natürliche Zahl ist:
; - 0
; - das Doppelte einer natürlichen Zahl
; - der Nachfolger des Doppelten einer natürlichen Zahl
\end{lstlisting}
%
Da die Datendefinition drei Fälle hat, muss der Rumpf aus
einer Verzweigung mit drei Zweigen bestehen:
%
\begin{lstlisting}
(define power2
  (lambda (base exponent)
    (cond
      ((zero? exponent) ...)
      ((even? exponent) ...)
      ((odd? exponent) ...))))
\end{lstlisting}
%
Der erste Fall entspricht der ursprünglichen
\lstinline{power}-Funktion~-- da muss eine $1$ hin.  Der zweite und der
dritte Fall enthalten jeweils einen Selbstbezug, weswegen dort
rekursive Aufrufe stehen müssen.  Im zweiten Fall steht "<das
Doppelte">, wir müssen also halbieren.  Im dritten Fall müssen wir vor dem Halbieren
noch eins abziehen.  Wir benutzen jeweils \lstinline{quotient}, weil
wir ganzzahlig halbieren:
%
\begin{lstlisting}
(define power2
  (lambda (base exponent)
    (cond
      ((zero? exponent) 1)
      ((even? exponent)
       ... (power2 base (quotient exponent 2)) ...)
      ((odd? exponent)
       ... (power2 base (quotient (- exponent 1) 2)) ...))))
\end{lstlisting}
%
Wir kümmern uns nun um den zweiten Fall: Wenn dort $b$ die Basis und
$e$ der Exponent sind, dann kommt beim rekursiven Aufruf heraus:
%
\begin{displaymath}
  b^{\frac{e}{2}}
\end{displaymath}
%
Gesucht ist \[b^e = b^{\frac{e}{2}} \times b^{\frac{e}{2}}.\]
Dafür müssen wir $b^{\frac{e}{2}}$ mit sich selbst
multiplizieren. Damit diese Zahl
nicht zweimal berechnet wird, legen wir dafür eine lokale Definition an:
%
\begin{lstlisting}
(define power2
  (lambda (base exponent)
    (cond
      ((zero? exponent) 1)
      ((even? exponent)
       (define half (power2 base (quotient exponent 2)))
       (* half half))
      ((odd? exponent)
       ... (power2 base (quotient (- exponent 1) 2)) ...))))
\end{lstlisting}
%
Im dritten Fall gilt:
\begin{displaymath}
  b^e = b^{\frac{e-1}{2}} \times b^{\frac{e-1}{2}} \times b.
\end{displaymath}
%
Entsprechend können wir den letzten Zweig ausfüllen:
%
\indexvariable{power2}
\begin{lstlisting}
(define power2
  (lambda (base exponent)
    (cond
      ((zero? exponent) 1)
      ((even? exponent)
       (define half (power2 base (quotient exponent 2)))
       (* half half))
      ((odd? exponent)
       (define half (power2 base (quotient (- exponent 1) 2)))
       (* half half base)))))
\end{lstlisting}
%
\begin{aufgabeinline}
  Überzeuge Dich mit dem Stepper, dass \lstinline{power2} weniger
  Multiplikationen benötigt als \lstinline{power}!
\end{aufgabeinline}

\section*{Aufgaben}

\begin{aufgabe}
  Schreibe eine Funktion, welche die \textit{Fakultät}\index{Fakultät}
  einer Zahl $n$ berechnet!  Die ist definiert als:
  %
  \begin{displaymath}
    n! \deq 1 \times 2 \times \cdots \times n
  \end{displaymath}
  %
\end{aufgabe}

\begin{aufgabe}\label{ex:drop}
  Programmieren Sie folgende Funktionen auf Listen:
  \begin{enumerate}
  \item Programmiere eine Funktion \texttt{take}, die als
    Argumente eine Liste \texttt{l} und eine Zahl \texttt{n}
    akzeptiert, und die ersten \texttt{n} Elemente der Liste
    \texttt{l} zurückgibt. Beispiel:
    \begin{alltt}
      (take (list 1 2 3 4 5 6 7 8) 5)
      \evalsto{} #<list 1 2 3 4 5>
    \end{alltt}
    %
    Gehe davon aus, dass \texttt{l} mindestens \texttt{n}
    Elemente lang ist.

  \item Programmiere eine Funktion \texttt{drop}, die als
    Argumente eine Liste \texttt{l} und eine Zahl \texttt{n}
    akzeptiert, und die Liste \texttt{l} ohne die ersten \texttt{n}
    Elemente zurückgibt.  Beispiel:
    \begin{alltt}
      (drop (list 1 2 3 4 5 6 7 8) 3)
      \evalsto{} #<list 4 5 6 7 8>
    \end{alltt}
    %
    Gehe davon aus, dass \texttt{l} mindestens \texttt{n}
    Elemente lang ist.
    \end{enumerate}
\end{aufgabe}


\begin{aufgabe}\label{ex:evensodds}
  \begin{itemize}
  \item
    Die eingebaute Funktion \texttt{even?}\indexvariable{even?}
    akzeptiert eine ganze Zahl und liefert \verb|#t|, falls diese
    gerade ist und \verb|#f| wenn nicht.
    Schreibe mit Hilfe von \texttt{even?}
    eine Funktion namens \texttt{evens}, welche für zwei
    Zahlen $a$ und $b$ eine Liste der geraden Zahlen zwischen $a$ und
    $b$ zurückgibt:
\begin{alltt}
(evens 1 10)
\evalsto{} #<list 2 4 6 8 10>
\end{alltt}
  \item
    Die eingebaute Funktion \texttt{odd?}\indexvariable{odd?}
    akzeptiert eine ganze Zahl und liefert \verb|#t|, falls diese
    ungerade ist und \verb|#f| wenn nicht.
    Schreibe mit Hilfe von \texttt{odd?} eine Funktion \texttt{odds}, welche für zwei
    Zahlen $a$ und $b$ eine Liste der ungeraden Zahlen zwischen $a$ und $b$
    zurückgibt:
\begin{alltt}
(odds 1 10)
\evalsto{} #<list 1 3 5 7 9>
\end{alltt}
  \end{itemize}
\end{aufgabe}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "i1"
%%% End: