\documentclass[a4paper,11pt]{article}
\usepackage[german]{babel}
\usepackage{epsfig}
\usepackage{verbatim}
\newcommand{\tilda}{\def\~{}}
\newcommand{\grad}{\ensuremath{^\circ}}
%\usepackage{german}
%\selectlanguage{\austrian}
\usepackage[breaklinks=true]{hyperref}
\hypersetup{
  pdfauthor = {Alexander \"Olzant},
            pdftitle = {Praktikum zur Fachdidaktik: Funktionale Programmierung mit Haskell},
            pdfsubject = {Haskell},
            pdfkeywords = {Martin Piskernig},
            pdfcreator = {LaTeX with hyperref package},
            pdfproducer = {dvips + ps2pdf}}



\begin{document}
\titlepage
\title{Funktionale Programmierung mit Haskell\\
050071 Praktikum zur Fachdidaktik SoSe 2006\\
bei Martin Piskernig
}
\author{Alexander \"Olzant\\
9301547\\
E 190 884 423}
\maketitle

\thispagestyle{empty}
\newpage
\tableofcontents
\newpage


\section{Einleitung}

Gerade zur schulischen Instruktion erscheint es wichtig, nicht nur die
\"ublichen imperativen und objektorientierten
Programmiersprachen zu unterrichten, sondern
m\"oglichst fr\"uh einen Einblick in funktionale Strukturen zu gew\"ahren.

Im Gegensatz etwa zu Logo, das als funktionale Programmiersprache im
Unterricht gerade mit j\"ungeren Kindern gerne eingesetzt wird, ist Haskell
einerseits eine sauberere/reinere funktionale Sprache und wird von vielen
auch als sch\"oner gesehen, andererseits bringt es nicht den Ballast der
graphischen Ausgabe inklusive Schildkr\"ote mit, sodass es wohl als weniger
\glqq verspielt\grqq{} angesehen werden wird. 
\subsection{Funktionale Programmierung}

Als Alternative zur objektorientierten Programmierung bietet sich die
funktionale Programmierung an: bereits vor deren Erfindung wurden
in funktionalen Sprachen Polymorphismus, Vererbung, Encapsulation
implementiert, sodass das objektorientierte Modell aus dieser Sicht
keinerlei Vorteile brachte. 

Der Begriff \glqq funktional\grqq ist im Bereich der Programmiersprachen
in unterschiedlichen Bedeutungen in Verwendung:
\begin{itemize} 
\item funktional = reich an Funktionalit\"at
\item funktional = beinhaltet die Abarbeitung von Ausdr\"ucken, die
keinerlei Nebeneffekte (side effects) aufweisen im Gegensatz zur
Abarbeitung von Befehlen.
\end{itemize} 

Die FAQ der Newsgroup comp.lang.functional definiert dementsprechend 
funktionale Programmierung folgendermassen:

\begin{quote}
Functional
programming is a style of programming that emphasizes the evaluation of
expressions, rather than execution of commands. The expressions in
these language are formed by using functions to combine basic
values. A
functional language is a language that supports and encourages
programming in a functional style. 
\end{quote}

(http://cbbrowne.com/info/functional.html)

W\"ahrend also in imperativen Programmiersprachen Variablen verwendet
werden, um Zwischenergebnisse zu speichern, z\"ahlt hier vor allem der
R\"uckgabewert.

Ein weiterer positiver Aspekt der funktionalen Sprachen liegt in der
Formulierung von Programmen, die der mathematischen Formelsprache
\"ahnlicher ist als entsprechend aufbereitete Algorithmen in prozeduralen
Sprachen. In diesem Zusammenhang wird besonders Haskell gerne als {\em
mind-expanding} bezeichnet, da sich besonders kompakter, subjektiv
huebscher, lesbarer Code mit sauberen Definitionen formulieren laesst.

Auch bez\"uglich der Abarbeitungsreihenfolge (lazy Evaluation) bietet die
funktionale Programmierung den Vorteil, dass nicht ben\"otigte Ergebnisse
gar nicht erst berechnet werden.

Die Auswertungsreihenfolge ist einerlei, und wenn es eine terminierende
Auswertungsreihenfolge gibt, so terminiert auch die normal order evaluation
(Theorem von Church/Rosser,
Konfluenz-, Diamanteigenschaft). 
Zirkul\"are Definitionen sind m\"oglich, wenn auch nicht immer leicht zu
formulieren. 
% TODO

Durch {\em Tail Recursion} kann Rekursion erst effizient implementiert werden: 
indem der Stack Frame der aufrufenden Funktion weiter verwendet wird,
anstatt einen neuen anzulegen, koennen beliebige Rekursionstiefen ohne
zus\"atzlichen Speicherverbrauch realisiert werden.
\cite{schani2001}


\subsection{Die Programmiersprache Haskell}
 
Benannt ist die Sprache nach dem Mathematiker Haskell Curry (1900 -
1982), dessen Name von Christopher Strachey auch f\"ur die
Benennung des Prinzip des {\em Currying} verwendet wurde. Dieses
wurde eigentlich von Moses Schönfinkel und Gottlob Frege erfunden
(die Begriffe sch\"onen f\"ur currying und finkeln fuer uncurrying haben
sich jedoch im Sprachgebrauch nicht wirklich durchgesetzt) bedeutet die
Umsetzung einer Funktion mehrerer Variablen auf eine mit nur einer -
intuitiv werden dabei die anderen festgesetzt.

Currying:

$$f : (X \times{} Y) \rightarrow{} Z$$

Uncurrying:

$$g : X \rightarrow{} (Y \rightarrow{}  Z)$$

Die Sprache selbst entstand im Jahre 1987, als ein Kommitee gegr\"undet und
die Sprache standardisiert wurde, um eine saubere Implementierung einer
funktionalen Sprache von Grund auf zu
erm\"oglichen. Der aktuelle Standard {\em Haskell 98} stammt, wie
der Name schon sagt, aus dem Jahr 1998.

Zum interaktiven Kennenlernen eignet sich am besten der Interpreter
{\em hugs} (Haskell User's Gofer System), es gibt jedoch auch einen
Compiler ({\em GHC}, Glasgow Haskell Compiler), der wie etwa bei Java oder
inform Bytecode f\"ur die zugeh\"orige Virtuelle Maschine produziert.

Beide sind Open Source und f\"ur die g\"angigsten Betriebssysteme (Unices,
Mac OS, Windows, VMS, ...) verf\"ugbar, wenngleich nicht unter der GPL.

Wie bereits bei der Einf\"uhrung der funktionalen Programmiersprachen
erw\"ahnt sind dank der lazy evaluation 
zirkul\"are Definitionen in Haskell formulierbar, es gibt jedoch auch
mindestens einen Dialekt mit einem anderen Paradigma:
Eager Haskell implementiert speculative evaluation.

\subsection{Andere Implementationen von Haskell}

% TODO: GPL

Seit seiner Entstehung wurde neben den oben genannten verbreiteten
Versionen GHS und HUGS noch andere programmiert:

\begin{itemize} 
\item Objektorientierte Versionen: Haskell++, O\'{}Haskell und Mondrian
\item Distributed Haskell 
\item Eager Haskell (speculative evaluation)
\item Concurrent Clean: GUI-Integration, keine Monaden, sondern unique types\\
http://www.cs.ru.nl/\~{}clean/
\end{itemize} 


\section{Erste Schritte}

Die Einf\"uhrung in eine funktionale Sprache bietet nat\"urlich einige
interessante M\"oglichkeiten. Einfache Berechnungen und
String-/Listenbeispiele koennen schon bald die list comprehension von
Haskell demonstrieren


\begin{verbatim}
Prelude> 2*2
4
Prelude> ['h','e','l','l','o'] ++ " world" 
"hello world"
Prelude> [n | n <- [0..10],  mod n 2 == 0 ]
[0,2,4,6,8,10]
Prelude> fac 5 where fac = product . enumFromTo 1
120
\end{verbatim}

Ganz leicht kann auch die lazy evaluation gezeigt werden: aus der unendlich
langen Liste ...

\begin{verbatim}
Prelude> enumFrom 1
[1,2,3,4,5,6,7,...
\end{verbatim}

... wird bei Bedarf nur der tats\"achlich ben\"otigte Teil berechnet:

\begin{verbatim}
Prelude> take 10 (enumFrom 1)
[1,2,3,4,5,6,7,8,9,10]
\end{verbatim}

Neben der Erl\"auterung der einfachen Datentypen und der wichtigsten Operatoren
sollte wohl auf die Fehlermeldungen eingegangen werden.

\begin{verbatim}
Prelude> sum == 2)
ERROR - Syntax error in input (unexpected `)')
\end{verbatim}

Abgesehen davon darf auch die Einf\"uhrung in den Interpreter hugs 
nicht zu kurz kommen

\begin{verbatim}
Prelude> :?
LIST OF COMMANDS:  Any command may be abbreviated to :c where
c is the first character in the full name.

:load <filenames>   load modules from specified files
:load               clear all files except prelude
:also <filenames>   read additional modules
:reload             repeat last load command
:edit <filename>    edit file
:edit               edit last module
:module <module>    set module for evaluating expressions
<expr>              evaluate expression
:type <expr>        print type of expression
:?                  display this list of commands
:set <options>      set command line options
:set                help on command line options
:names [pat]        list names currently in scope
:info <names>       describe named objects
:browse <modules>   browse names exported by <modules>
:find <name>        edit module containing definition of name
:!command           shell escape
:cd dir             change directory
:gc                 force garbage collection
:version            print Hugs version
:quit               exit Hugs interpreter
\end{verbatim}

\section{Rekursion}

Das beliebteste Beispiel zur Erl\"auterung
der Rekursion ist vielleicht die
Implementation der Funktion zur Berechnung der {\em Faktoriellen}

\begin{verbatim}
fac :: Integer -> Integer
fac 0 = 1
fac n | n > 0 = n * fac (n-1)
\end{verbatim}

Dies erfordert jedoch, dass das Ergebnis jedes Funktionsaufrufes mit n
multipliziert wird und verhindert damit die Wiederbenutzung des Stack Frame
(tail recursion). Durch eine Modifikation kann dieser Sch\"onheitsfehler
behoben werden.  In dieser Variante ist nur ein Stack Frame f\"ur die
Rekursion notwendig, daher ist sie nicht weniger effizient und viel
eleganter als eine iterative Variante:

\begin{verbatim}
fac :: [Integer] -> [Integer] -> Integer
fac c m  | m == 1 = c 
         | otherwise = fac (c*m) (m-1)

fac> fac 1 99
933262154439441526816992388562667004907159682643816214685929638952175999932
299156089414639761565182862536979208272237582511852109168640000000000000000
000000
\end{verbatim}

\section{Lambda-Operator}

Ebenfalls unumg\"anglich ist die Verwendung des Lambda-Operators zur
Definition anonymer Funktionen.

\begin{verbatim}
Prelude> do_something 99 (\x -> x * x) where 
                    do_something x fn = fn x
9801
\end{verbatim}
%TODO: type
\begin{verbatim}
msort = foldl (\s -> \t -> (\(u, v) -> u++[t]++v) 
                           (break (>t) s)  ) []
Prelude> msort "ZyXVAbCdE1230"
"0123ACEVXZbdy"
\end{verbatim}



\section{Datentypen}

Zus\"atzlich zu den anfangs besprochenen einfachen Datentypen wie
Integer, Bool, String (eigtl. liste von Char) sind dann Tupel und der
Zugriff auf die Elemente zu behandenln:

\begin{verbatim}
type Tier = (String, String, Int)

name   :: Tier -> String
linne  :: Tier -> String
nummer :: Tier -> Int

name (n,l,u) = n
linne (n,l,u) = l
nummer (n,l,u) = u
\end{verbatim}

\section{Unterrichtsplan}

\begin{enumerate}	
\item {\bf Einf\"uhrung 1}\\
Erl\"auterung iterative, funktionale, objektorientierte
Programmiersprachen\\
diverse Beispiele\\
Hinweis auf funktionale Eigenschaften (list comprehension, Rekursion,
anonyme Funktionen ...)
\item {\bf Einf\"uhrung 2}\\
Erkl\"arung der Arbeitsumgebung\\
hugs - Interpreter, Fehlermeldungen\\
literale und traditionelle Scripte\\
einfache funktionale Konstrukte\\
\item {\bf Einf\"uhrung 3}\\
Elementare Datentypen\\
Operatoren\\
Konstanten\\
Relatoren
\item {\bf Rekursion}\\
Vergleich iterativer und rekursiver Algorithmen\\
mathematische Schreibweise\\
Beispiele: Faktorielle, Fibonacci-Zahlen\\
\item {\bf Rekursion Wiederholung}\\
Tail recursion\\
repetitive (schlichte), lineare, geschachtelte, baumartige Rekursion\\
Effizienz (z. B. von Fibonacci-Implementierungen)
\item{\bf Lambda-Operator}\\
freie und gebundene Variablen\\
Lambda-Ausdr\"ucke, anonyme Funktionen\\
Sortierfunktionen
\item{\bf Layout-Konventionen, Notation, Muster}
Abseitsregel\\
\item{\bf Lambda-Operator Wiederholung}
\item{\bf Tupel}\\
festgelegte Zahl von Werten zur Modellierung von Strukturen\\
\item{\bf Listen}\\
beliebige Zahl von Werten gleichen Typs\\
Kurznotation [5 .. 10] \\
Listenkomprehension wieder einmal\\
\begin{verbatim}
[ n*n | n <- list, n < 10 ]
\end{verbatim}
\item{\bf Polymorphie, Muster}\\
Polymorphie == \glqq Vielgestaltigkeit\grqq\\
\"Uberladen == ad-hoc Polymorphie\\
Muster: Werte, Variablen, Wild cards
\item{\bf Typen}\\
Produkttyp vs Tupel: beim Tupel kein Kunstruktor\\
Summentyp\\
Rekursive Typen (B\"aume, ...)\\
polymorphe Typen
\item{\bf Polymorphie, Vererbung}\\
Wiederverwendung!\\
Typen, Funktionen\\
\item{\bf Funktionale}\\
Funktionen h\"oherer Ordnung (involvieren Funktionen in Argumenten oder
Resultaten)\\
\item{\bf Currying, Funktionskomposition}\\
mehrstellige Funktionen - Funktionspfeil statt Tupel
\item{\bf Monaden}\\
Ein-/Ausgabe - Schnittstelle zur imperativen Programmierung\\
Festlegung der Reihenfolge von Operationen
\item{\bf Module} (optional)\\
Export/Import, Kollisionen\\
\end{enumerate} 


\section{\"Ubungsbeispiele}

\subsection{Rekursion: Fibonacci-Zahlen}

Schreibe eine rekursive Funktion, welche die Fibonacci-Zahlen berechnet.
Diese Zahlen $f_0, f_1, ...$ sind folgendermassen definiert: $f_0 = f_1 =
1$ und $f_{n+2} = f_n + f_{n+1}$. 

Abzugeben ist eine rekursive Funktion {\tt fibonacci}, welche eine
nat\"urliche Zahl $n$ als Parameter nimmt und $f_n$ als Ergebnis ausgibt.

\subsection{Listen und Strings: Palindrome}

Schreibe eine Funktion {\tt isPal}, die fuer eine Eingabeliste
oder einen String feststellt, ob sie ein Palindrom darstellt, also von
vorne nach hinten die gleiche Folge von Elementen aufweist wie von hinten
nach vorne.

\subsection{Tupeln und Listen: Primfaktorenzerlegung}

Schreibe eine Haskell-Funktion zur Primfaktorenzerlegung, die eine Liste
der Primfaktoren fuer den Eingabeparameter ausgibt. Empfehlung:
implementiere dazu eine Funktion, die \"uberpr\"uft, ob eine Zahl eine
Primzahl ist.

\subsection{Typklassen und ihre Instanzen}

\begin{verbatim}
data Baum a = Empty |
              Node a (Baum a) (Baum a)
\end{verbatim}

Schreibe Haskell-Funktionen, die die Hoehe des Baumes (also den l\"angsten
Weg von der Wurzel bis zum letzten Ast) und die Anzahl der \"Aste
berechnen!

\subsection{Currying}

Schreibe eine curryfizierte, polymorphe Funktion {\tt zauberwort a 
-$>$ [b] -$>$ [b]}, die eine
Eingabeliste folgendermassen modifiziert:

\begin{itemize} 
\item wenn {\tt a == 1}, dann drehe die Reihenfolge der Elemente in der
Ausgabeliste um
\item wenn {\tt a == 2}, dann erhoehe den Wert jedes Elements in der Ausgabeliste
um 1
\item wenn {\tt a == 3}, dann ersetze A..Za..z durch Z..Az..a, drehe also das
Alphabet um
\item ansonsten gebe \glqq Hokuspokus\grqq{} aus
\end{itemize} 

Implementiere die Varianten 1 bis 3 dazu als einstellige Funktionen.

\section{Fallstricke/Caveats}

Eine Eigenschaft, die in vielen anderen Programmiersprachen so nicht
vorkommt, ist die Bedeutung von Einr\"uckungen. W\"ahrend es
grunds\"atzlich in fasst jeder Sprache zur Lesbarkeit beitr\"agt,
zusammengeh\"orige Codebl\"ocke entsprechend einzur\"ucken, markieren
Einr\"uckungen in Haskell die Bindungsbereiche und m\"ussen daher unbedingt
eingehalten werden, was daf\"ur die Typographie vereinfacht (keine
Strichpunkte notwendig).

Die beiden Varianten von script ({\em
traditional}, {\bf .hs}
und {\em literal}, {\bf .lhs}) k\"onnen ebenfalls zur Verwirrung beitragen.

Syntax und Semantik kann f\"ur Anf\"angerInnen funktionaler Programmierung
verwirrend sein.

http://www.haskell.org/tutorial/pitfalls.html f\"uhrt noch folgende
Probleme an:

\begin{itemize} 
\item Typisierung: keine implizite Umwandlung
\item explizite Rekursion wegen der high order functions meist nicht notwendig\\
\begin{verbatim}
raise :: Num a => a -> [a] -> [a]
raise _ [] = []
raise x (y:ys) = x+y : raise x ys
\end{verbatim}
eleganter:\\
\begin{verbatim}
raise x ys = map (x+) ys
\end{verbatim}
\end{itemize} 


\section{Iterative Programmeirung}
{\bf nicht} zur Nachahmung, von 
http://www.willamette.edu/~fruehr/haskell/evolution.html
\begin{verbatim}
fac n = result (for init next done)
        where init = (0,1)
              next   (i,m) = (i+1, m * (i+1))
              done   (i,_) = i==n
              result (_,m) = m

for i n d = until d n i
\end{verbatim}



%    * Welche "Fallstricke" gibt es in der Sprache (C: "if(c = 3) do_something();")?
%    * Wie einfach ist die Syntax zu erlernen (Java: "public static void main(String[] args)")?
%    * Welche Konzepte vermittelt die Sprache vorwiegend (Rekursion, Vererbung, ...)?
%    * In welcher Reihenfolge werden diese Konzepte erklärt?
%    * Wie könnten erste Übungsbeispiele aussehen?
%    * Gibt es geeignete Entwicklungsumgebungen (IDEs)?
%    * Wie schwierig zu verwenden ist die Sprache (interpretiert, kompiliert, ...)?
%    * Welcher Familie gehört die Sprache an (prozedural, funktional, ...)?
%    * usw. usf. 
%

\section{Fazit}

Im Besonderen f\"ur eine funktionale Programmiersprache hat Haskell also
einiges zu bieten, in einem Semester sind zumindest die Grundz\"uge
unterzubringen, ohne die Sch\"ulerInnen zu \"uberbeanspruchen.

Auch ohne
vorhergehende Erfahrungen etwa in der Unterstufe sollte es durchaus
m\"oglich sein, Rekursion, Currying und dar\"uber hinausgehende Konstrukte
nahezubringen, zumal wenn in einem weiterf\"uhrenden Kurs die Konzepte
erweitert und vertieft werden k\"onnen, eine erstmalige Verwendung in einer
h\"oheren Schulstufe wird vermutlich zu interessanten Relativierungen der
zu diesem Zeitpunkt m\"oglicherweise bereits einge\"ubten imperativen
Konstrukte aus anderen Programmiersprachen f\"uhren. 

Durch die mathematische Formulierung der Programme ist eine direkte
Kooperation mit dem Fach Mathematik m\"oglich, keinesfalls aber zwingend
notwendig. Eine funktionale Grundeigenschaft ist {\em list comprehension},
mit Listen (und sogar dem \"Aquivalent des mathematischen Allquantors) kann
elegant nicht nur ein Iteratives Konstrukt, sondern auch direkte Rekursion
vermieden werden.

Der \glqq freundliche\grqq{} Interpreter hugs, der meist aussagekr\"aftige
Fehlermeldungen ausgibt, scheint f\"ur den Unterricht ebenfalls sehr
geeignet, da f\"ur Prototyping nicht erst Compile-Zyklen eingeschoben 
werden m\"ussen.

Zuvorderst (und als Mindestmass f\"ur die Bewertung) sind wohl die
Beherrschung funktionaler Konstrukte zu sehen, aus denen Programme mit
einfachen Algorithmen zu konstruieren sind; weitergehende Projekte werden
wohl einen gr\"osseren Antel des umfangreichen Vokabulars nutzen.

\section{Links, weitere Informationen}

\begin{itemize} 
\item Eleven Reasons to use Haskell as a Mathematician \\
http://sigfpe.blogspot.com/2006/01/eleven-reasons-to-use-haskell-as.html
\item Haskellwiki \\
http://www.haskell.org/
\item Haskell Reference (zvon.org) \\
http://zvon.org/other/haskell/Outputglobal/index.html
\item Functional Programming in the Real World\\
http://homepages.inf.ed.ac.uk/wadler/realworld/index.html
\item Funktionale Programmierung - Lehrveranstaltung des Instituts f\"ur
Computersprachen an der TU Wien\\
http://www.complang.tuwien.ac.at/knoop/fp185161\_{}ws0506.html
\end{itemize} 

\nocite{*}
\section{Bibliographie}
\bibliographystyle{plainnat}       % (uses file "plain.bst")
\bibliography{fachdidaktikpraktikum_haskell}


\end{document}
% vim: textwidth=75

