Haskell.tex 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293
  1. %!TEX root = Programmierparadigmen.tex
  2. \chapter{Haskell}
  3. \index{Haskell|(}
  4. Haskell ist eine funktionale Programmiersprache, die 1990 in Version~1.0 veröffentlicht
  5. wurde. Namensgeber ist Haskell Brooks Curry, der die mathematischen Grundlagen der funktionalen Programmierung entwickelte.
  6. Wichtige Konzepte sind:
  7. \begin{enumerate}
  8. \item Funktionen höherer Ordnung
  9. \item anonyme Funktionen (sog. Lambda-Funktionen)
  10. \item Pattern Matching
  11. \item Unterversorgung
  12. \item Typinferenz
  13. \end{enumerate}
  14. Haskell kann mit \enquote{Glasgow Haskell Compiler} mittels
  15. \texttt{ghci} interpretiert und mittels
  16. \section{Erste Schritte}
  17. Haskell kann unter \href{http://www.haskell.org/platform/}{\path{www.haskell.org/platform/}}
  18. für alle Plattformen heruntergeladen werden. Unter Debian-Systemen
  19. ist das Paket \texttt{ghc} bzw. \texttt{haskell-platform} relevant.
  20. \subsection{Hello World}
  21. Speichere folgenden Quelltext als \texttt{hello-world.hs}:
  22. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=hello-world.hs]{haskell}{scripts/haskell/hello-world.hs}
  23. Kompiliere ihn mit \texttt{ghc -o hello hello-world.hs}. Es wird eine
  24. ausführbare Datei erzeugt.
  25. Alternativ kann es direkt mit \texttt{runghc hello-world.hs} ausgeführt werden.
  26. \section{Syntax}
  27. \subsection{Klammern und Funktionsdeklaration}
  28. Haskell verzichtet an vielen Stellen auf Klammern. So werden im
  29. Folgenden die Funktionen $f(x) := \frac{\sin x}{x}$ und $g(x) := x \cdot f(x^2)$
  30. definiert:
  31. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/einfaches-beispiel-klammern.hs}
  32. Die Funktionsdeklarationen mit den Typen sind nicht notwendig, da
  33. die Typen aus den benutzten Funktionen abgeleitet werden.
  34. Zu lesen ist die Deklaration wie folgt:
  35. \begin{center}
  36. \texttt{[Funktionsname] :: \texttt{[Typendefinitionen]} => \texttt{Signatur}}
  37. \end{center}
  38. \begin{itemize}
  39. \item[T. Def.] Die Funktion \texttt{f} benutzt als Parameter bzw. Rückgabewert
  40. einen Typen. Diesen Typen nennen wir \texttt{a} und er ist
  41. vom Typ \texttt{Floating}. Auch \texttt{b}, \texttt{wasweisich}
  42. oder etwas ähnliches wäre ok.
  43. \item[Signatur] Die Signatur liest man am einfachsten von hinten:
  44. \begin{itemize}
  45. \item \texttt{f} bildet auf einen Wert vom Typ \texttt{a} ab und
  46. \item \texttt{f} hat genau einen Parameter \texttt{a}
  47. \end{itemize}
  48. \end{itemize}
  49. \todo[inline]{Gibt es Funktionsdeklarationen, die bis auf Wechsel des Namens und der Reihenfolge äquivalent sind?}
  50. \subsection{if / else}
  51. Das folgende Beispiel definiert den Binomialkoeffizienten (vgl. \cref{bsp:binomialkoeffizient})
  52. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/binomialkoeffizient.hs}
  53. Das könnte man auch mit sog. Guards machen:\xindex{Guard}
  54. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/binomialkoeffizient-guard.hs}
  55. \subsection{Rekursion}
  56. Die Fakultätsfunktion wurde wie folgt implementiert:
  57. \[fak(n) := \begin{cases}
  58. 1 &\text{falls } n=0\\
  59. n \cdot fak(n) &\text{sonst}
  60. \end{cases}\]
  61. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/fakultaet.hs}
  62. Diese Implementierung benötigt $\mathcal{O}(n)$ rekursive Aufrufe und
  63. hat einen Speicherverbrauch von $\mathcal{O}(n)$. Durch einen
  64. \textbf{Akkumulator}\xindex{Akkumulator} kann dies verhindert werden:
  65. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/fakultaet-akkumulator.hs}
  66. \subsection{Listen}
  67. \begin{itemize}
  68. \item \texttt{[]} erzeugt die leere Liste,
  69. \item \texttt{[1,2,3]} erzeugt eine Liste mit den Elementen $1, 2, 3$
  70. \item \texttt{:} wird \textbf{cons}\xindex{cons} genannt und ist
  71. der Listenkonstruktor.
  72. \item \texttt{list !! i} gibt das $i$-te Element von \texttt{list} zurück.
  73. \item \texttt{head list} gibt den Kopf von \texttt{list} zurück,
  74. \texttt{tail list} den Rest:
  75. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/list-basic.sh}
  76. \item \texttt{last [1,9,1,3]} gibt 3 zurück.
  77. \item \texttt{length list} gibt die Anzahl der Elemente in \texttt{list} zurück.
  78. \item \texttt{maximum [1,9,1,3]} gibt 9 zurück (analog: \texttt{minimum}).
  79. \item \texttt{null list} prüft, ob \texttt{list} leer ist.
  80. \item \texttt{take 3 [1,2,3,4,5]} gibt \texttt{[1,2,3]} zurück.
  81. \item \texttt{drop 3 [1,2,3,4,5]} gibt \texttt{[4,5]} zurück.
  82. \item \texttt{reverse [1,9,1,3]} gibt \texttt{[3,1,9,1]} zurück.
  83. \item \texttt{elem item list} gibt zurück, ob sich \texttt{item} in \texttt{list} befindet.
  84. \end{itemize}
  85. \subsubsection{Beispiel in der interaktiven Konsole}
  86. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/listenoperationen.sh}
  87. \subsubsection{List-Comprehensions}\xindex{List-Comprehension}%
  88. List-Comprehensions sind kurzschreibweisen für Listen, die sich an
  89. der Mengenschreibweise in der Mathematik orientieren. So entspricht
  90. die Menge
  91. \begin{align*}
  92. myList &= \Set{1,2,3,4,5,6}\\
  93. test &= \Set{x \in myList | x > 2}
  94. \end{align*}
  95. in etwa folgendem Haskell-Code:
  96. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/list-comprehensions.sh}
  97. \begin{beispiel}[List-Comprehension]
  98. Das folgende Beispiel zeigt, wie man mit List-Comprehensions die unendliche
  99. Liste aller pythagoreischen Tripels erstellen kann:
  100. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/pythagorean-triples.hs}
  101. \end{beispiel}
  102. \subsection{Strings}
  103. \begin{itemize}
  104. \item Strings sind Listen von Zeichen:\\
  105. \texttt{tail "ABCDEF"} gibt \texttt{"BCDEF"} zurück.
  106. \end{itemize}
  107. \subsection{Let und where}\xindex{let}\xindex{where}%
  108. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/let-where-bindung.hs}
  109. \subsection{Funktionskomposition}\xindex{.}\xindex{Funktionskomposition}%
  110. In Haskell funktioniert Funktionskomposition mit einem Punkt:
  111. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/function-composition.hs}
  112. Dabei ergibt \texttt{h (-3)} in der mathematischen Notation
  113. \[(g \circ f) (-3) = f(g(-3)) = f(-4) = 16\]
  114. und \texttt{i (-3)} ergibt
  115. \[(f \circ g) (-3) = g(f(-3)) = g(9) = 8\]
  116. Es ist also anzumerken, dass die Reihenfolge \underline{nicht} der mathematischen
  117. konvention entspricht.
  118. \section{Typen}
  119. \subsection{Standard-Typen}
  120. Haskell kennt einige Basis-Typen:
  121. \begin{itemize}
  122. \item \textbf{Int}: Ganze Zahlen. Der Zahlenbereich kann je nach Implementierung variieren,
  123. aber der Haskell-Standart garantiert, dass das Intervall
  124. $[-2^{29}, 2^{29}-1]$ abgedeckt wird.
  125. \item \textbf{Integer}: beliebig große ganze Zahlen
  126. \item \textbf{Float}: Fließkommazahlen
  127. \item \textbf{Double}: Fließkommazahlen mit doppelter Präzision
  128. \item \textbf{Bool}: Wahrheitswerte
  129. \item \textbf{Char}: Unicode-Zeichen
  130. \end{itemize}
  131. Des weiteren gibt es einige strukturierte Typen:
  132. \begin{itemize}
  133. \item Listen: z.~B. $[1,2,3]$
  134. \item Tupel: z.~B. $(1,'a',2)$
  135. \item Brüche (Fractional, RealFrac)
  136. \item Summen-Typen: Typen mit mehreren möglichen Repräsentationen
  137. \end{itemize}
  138. \subsection{Typinferenz}
  139. In Haskell werden Typen aus den Operationen geschlossfolgert. Dieses
  140. Schlussfolgern der Typen, die nicht explizit angegeben werden müssen,
  141. nennt man \textbf{Typinferent}\xindex{Typinferenz}.
  142. Haskell kennt die Typen aus \cref{fig:haskell-type-hierarchy}.
  143. Ein paar Beispiele zur Typinferenz:
  144. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/typinferenz.sh}
  145. \begin{figure}[htp]
  146. \centering
  147. \resizebox{0.9\linewidth}{!}{\input{figures/haskell-type-classes.tex}}
  148. \caption{Hierarchie der Haskell Standardklassen}
  149. \label{fig:haskell-type-hierarchy}
  150. \end{figure}
  151. \subsection{type}\xindex{type}%
  152. Mit \texttt{type} können Typsynonyme erstellt werden:
  153. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/alt-types.hs}
  154. \subsection{data}\xindex{data}%
  155. Mit dem Schlüsselwort \texttt{data} können algebraische Datentypen\xindex{Datentyp!algebraischer}
  156. erzeugt werden:
  157. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/data-example.hs}
  158. \section{Lazy Evaluation}\xindex{Lazy Evaluation}%
  159. Haskell wertet Ausdrücke nur aus, wenn es nötig ist.
  160. \begin{beispiel}[Lazy Evaluation]
  161. Obwohl der folgende Ausdruck einen Teilausdruck hat, der einen Fehler zurückgeben
  162. würde, kann er aufgrund der Lazy Evaluation zu 2 evaluiert werden:
  163. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=lazy-evaluation.hs]{haskell}{scripts/haskell/lazy-evaluation.hs}
  164. \end{beispiel}
  165. \section{Beispiele}
  166. \subsection{Quicksort}
  167. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=qsort.hs]{haskell}{scripts/haskell/qsort.hs}
  168. \begin{itemize}
  169. \item Die leere Liste ergibt sortiert die leere Liste.
  170. \item Wähle das erste Element \texttt{p} als Pivotelement und
  171. teile die restliche Liste \texttt{ps} in kleinere und
  172. gleiche sowie in größere Elemente mit \texttt{filter} auf.
  173. Konkateniere diese beiden Listen mit \texttt{++}.
  174. \end{itemize}
  175. Durch das Ausnutzen von Unterversorgung\xindex{Unterversorgung} lässt
  176. sich das ganze sogar noch kürzer schreiben:
  177. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=qsort.hs]{haskell}{scripts/haskell/qsort-unterversorg.hs}
  178. \subsection{Fibonacci}\xindex{Fibonacci}
  179. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=fibonacci.hs]{haskell}{scripts/haskell/fibonacci.hs}
  180. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=fibonacci-akk.hs]{haskell}{scripts/haskell/fibonacci-akk.hs}
  181. \xindex{zipWith}
  182. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=fibonacci-zip.hs]{haskell}{scripts/haskell/fibonacci-zip.hs}
  183. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=fibonacci-pattern-matching.hs]{haskell}{scripts/haskell/fibonacci-pattern-matching.hs}
  184. Die unendliche Liste alle Fibonacci-Zahlen, also der Fibonacci-\textit{Stream}\xindex{Stream}
  185. wird wie folgt erzeugt:
  186. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=fibonacci-stream.hs]{haskell}{scripts/haskell/fibonacci-stream.hs}
  187. \subsection{Polynome}\xindex{Polynome}\xindex{zipWith}\xindex{foldr}\xindex{tail}%
  188. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=polynome.hs]{haskell}{scripts/haskell/polynome.hs}
  189. \subsection{Hirsch-Index}\xindex{Hirsch-Index}\xindex{Ord}\xindex{Num}%
  190. \textbf{Parameter}: Eine Liste $L$ von Zahlen aus $\mdn$\\
  191. \textbf{Rückgabe}: $\max \Set{n \in \mdn | n \leq \|\Set{i \in L | i \geq n}\|}$
  192. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=hirsch-index.hs]{haskell}{scripts/haskell/hirsch-index.hs}
  193. \subsection{Lauflängencodierung}\xindex{Lauflängencodierung}\xindex{splitWhen}\xindex{group}\xindex{concat}%
  194. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=lauflaengencodierung.hs]{haskell}{scripts/haskell/lauflaengencodierung.hs}
  195. \subsection{Intersections}\xindex{Intersections}\xindex{List-Comprehension}%
  196. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=intersect.hs]{haskell}{scripts/haskell/intersect.hs}
  197. \subsection{Funktionen höherer Ordnung}\xindex{Folds}\xindex{foldl}\xindex{foldr}\label{bsp:foldl-und-foldr}
  198. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=folds.hs]{haskell}{scripts/haskell/folds.hs}
  199. \subsection{Chruch-Zahlen}
  200. \inputminted[linenos, numbersep=5pt, tabsize=4, frame=lines, label=church.hs]{haskell}{scripts/haskell/church.hs}
  201. \subsection{Trees}\xindex{tree}\xindex{map!tree}%
  202. Einen Binärbaum kann man in Haskell so definieren:
  203. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/binary-tree.hs}
  204. Einen allgemeinen Baum so:
  205. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/general-tree.hs}
  206. Hier ist \texttt{t} der polymorphe Typ des Baumes. \texttt{t} gibt also an welche
  207. Elemente der Baum enthält.
  208. Man kann auf einem solchen Baum auch eine Variante von \texttt{map} und
  209. \texttt{reduce} definieren,
  210. also eine Funktion \texttt{mapT}, die eine weitere Funktion \texttt{f} auf jeden
  211. Knoten anwendet:
  212. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/mapt.hs}
  213. \subsection{Standard Prelude}
  214. Hier sind die Definitionen eininger wichtiger Funktionen:
  215. \xindex{zipWith}\xindex{zip}
  216. \inputminted[numbersep=5pt, tabsize=4]{haskell}{scripts/haskell/standard-definitions.hs}
  217. \section{Weitere Informationen}
  218. \begin{itemize}
  219. \item \href{http://hackage.haskell.org/package/base-4.6.0.1}{\path{hackage.haskell.org/package/base-4.6.0.1}}: Referenz
  220. \item \href{http://www.haskell.org/hoogle/}{\path{haskell.org/hoogle}}: Suchmaschine für das Haskell-Manual
  221. \item \href{http://wiki.ubuntuusers.de/Haskell}{\path{wiki.ubuntuusers.de/Haskell}}: Hinweise zur Installation von Haskell unter Ubuntu
  222. \end{itemize}
  223. \index{Haskell|)}