Die Funktionale Programmiersprache Haskell

Transcript

Die Funktionale Programmiersprache Haskell Simon Winterhalter 49013 Wladimir Bulanow 49034 Hochschule Aalen Hochschule Aalen Wintersemester 16/17 1 Inhaltsverzeichnis 1 Einführung 1.1 Compiler und Interpreter . . . . . . . . . . . . . . . . . . . . . 1.2 Der GHCI-Interpreter . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 2 Philosophie und Paradigmen der Funktionalen Programmierung 6 3 Syntax 3.1 Atomare Datentypen . . . . . 3.2 Signaturen . . . . . . . . . . . 3.3 Typvariablen und Polymorphe 3.4 Typklassen . . . . . . . . . . . . . . . . . . . . . . . . . Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Funktionen 7 7 7 8 9 10 5 Vordefinierte Datenstrukturen: Listen, Strings und Tupel 12 5.1 Listen und Strings . . . . . . . . . . . . . . . . . . . . . . . . 12 5.2 Tupel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6 Unendliche Listen, Lazy Evaluation und List-Comprehensions 15 6.1 Ranges und Lazy Evaluation . . . . . . . . . . . . . . . . . . . 15 6.2 List-Comprehensions . . . . . . . . . . . . . . . . . . . . . . . 16 7 Fallunterscheidungen 7.1 If Then Else . . . . 7.2 Patternmatching . 7.3 Guards . . . . . . . 7.4 Case Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 18 18 19 20 8 Lokale Definitionen 20 8.1 Lokale Definitionen mit Where . . . . . . . . . . . . . . . . . . 20 8.2 Lokale Definitionen mit Let-in . . . . . . . . . . . . . . . . . . 21 9 Rekursionen 22 9.1 Die Funktion take . . . . . . . . . . . . . . . . . . . . . . . . . 22 9.2 Endrekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 10 Funktionen Höherer Ordnung 25 11 Mapping 25 2 12 Filtering 26 13 Fazit 26 14 Literaturverzeichnis und Verweise 28 3 Listings 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Signatur Beispiel . . . . . . . . . . . . . . Signatur Beispiel 2 . . . . . . . . . . . . . Funktion Beispiel . . . . . . . . . . . . . . Infix/Prefix Beispiel . . . . . . . . . . . . . Funktionelle Problemlösungsansatz . . . . ++-Operator Beispiel . . . . . . . . . . . . !!-Operator Beispiel . . . . . . . . . . . . . Listen Zerlegung Beispiel . . . . . . . . . . Beispiel Head-Funktion . . . . . . . . . . . Listen Zerlegung Beispiel . . . . . . . . . . Ranges Beispiel . . . . . . . . . . . . . . . List-Comprehensions Beispiel . . . . . . . If-then-else Konstrukt Beispiel . . . . . . . Patternmatching Beispiel . . . . . . . . . . Beispiel Guards [Lip11] . . . . . . . . . . . Case-of Konstrukt Beispiel . . . . . . . . . Where Konstrukt Beispiel . . . . . . . . . Let-in Konstrukt Beispiel . . . . . . . . . . Implementierung first second Beispiel . . . Implementierung take Beispiel . . . . . . . Implementierung . . . . . . . . . . . . . . Darstellung im Speicher . . . . . . . . . . Implementierung mit Endrekursion . . . . Darstellung der Endrekursion im Speicher Funktion als Parameter Beispiel . . . . . . Mapping Rekursiv Beispiel . . . . . . . . . Mapping List-Comprehension Beispiel . . . 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 8 10 11 11 12 12 13 14 15 16 17 18 19 20 20 21 21 22 23 24 24 24 24 25 25 26 1 Einführung In dieser Arbeit möchten wir uns mit der funktionalen Programmiersprache Haskell auseinandersetzten. Wir möchten hier Vor- und Nachteile, sowie anhand einiger Beispiele die Eigenheiten und Anwendungsgebiete von Haskell erläutern. Für die effiziente Umsetzung von Softwareaufgaben ist schon die Wahl der Sprache entscheidend. Viele Aufgaben sind in herkömmlichen, imperativen Sprachen wie C, C++ oder Java zwar umsetzbar, doch scheitern sie gegebenenfalls an strikten Vorgaben für Speicherplatz oder Performance. Außerdem kann der Arbeitsaufwand durch syntaktische Hindernisse erhöht werden, während eine optimierte Sprache eine kürzere, weniger fehleranfällige und effizientere Codierung des gefragten Algorithmus ermöglichen kann. Haskell ermöglicht insbesondere optimierte Implementierungen von Funktionen. Durch Lazy Evaluation und Rekursionsoptimierung ist es möglich unnötige Funktionsaufrufe und damit Laufzeit und Speicherplatz einzusparen. 1.1 Compiler und Interpreter Es gibt eine Vielzahl verschiedener Haskell Compiler. Für diese Arbeit ist die Wahl auf den Glasgow Haskell Compiler gefallen, da er die Haskell Standards am besten umsetzt und die größte Verbreitung findet [Wik]. Außerdem bringt er einen interaktiven Interpreter mit, der sich gut für die ersten praktischen Experimente und Übungen eignet. Für Linux ist der Compiler in den Paketquellen enthalten. Des weiteren ist dort auch die Haskell-Plattform zu finden, die weitere Werkzeuge rund um Haskell enthält auf die jedoch im folgenden nicht näher eingegangen wird. Mit den folgenden Zeilen können die Pakete installiert werden. sudo apt-get install ghc sudo apt-get install haskell-platform 1.2 Der GHCI-Interpreter Der Interpreter lässt sich über das Terminal mit dem Aufruf ’ghci’ starten. Nach einem kurzen Grußtext erscheint der Prompt ’Prelude>’. Es ist empfehlenswert den Prompt direkt zu beginn manuell zu ändern, da er ansonsten jedes geladene Modul aufführt und sich somit verlängert, was der Übersicht schaden kann. Dies geht mit der Zeile :set prompt “prompt“ . Zur Konfiguration des Interpreters können Kommandos mit einem vorangestellten Doppelpunkt eingegeben werden, als Beispiel sein hier genannt :? , was 5 die Ausgabe der verfügbaren Kommandos zur Folge hat. Die in dieser Arbeit verwendeten Kommandos können samt kurzer Beschreibung in der folgenden Tabelle eingesehen werden. Kommando Beschreibung :set prompt "ghci> " Statischen Prompt einrichten :t Den Typ eines Ausdrucks ausgeben [Lip11] :l Laden eines Moduls :r Geladene Module neu Einlesen 2 Philosophie und Paradigmen der Funktionalen Programmierung In der Funktionalen Programmierung ist der typische Problemlösungsansatz, einfache, nachweislich korrekte Funktionen zu schreiben und diese dann zu komplexeren Funktionen zusammenzusetzen. In der Funktionalen Programmierung werden keine Variablen verwendet, Funktionsaufrufe können daher keine Nebeneffekte erzeugen. Das führt dazu, dass alle Haskell Programme zustandsfrei sind. Diese Herangehensweise trägt einerseits dazu bei, die Fehleranfälligkeit eines Programms zu minimieren. Andererseits, und das ist eine besondere Stärke von Funktionalen Programmiersprachen, trägt sie vor allem bei zunehmend tiefen Rekursionen oder langen Iterationen zu einer erheblichen Verbesserung der Laufzeit bei. Das rührt daher, dass für die meisten, wenn nicht gar alle, Funktionen bereits zum Zeitpunkt der Kompilierung feststeht, welchen Rückgabewert sie liefern werden. Durch die Eingrenzung von Definitionsmengen und Wertebereichen können selbst einige semantische Fehler, die in imperativen Sprachen nur schwer zu finden sind, ebenfalls bereits vom Compiler erkannt und gemeldet werden. Die Syntax für Funktionen in Haskell ist sehr übersichtlich und prägnant. Das vereinfacht eine eventuelle Fehlersuche, da das Funktionale Paradigma von Haskell den Programmierer dazu zwingt, den Code in kleine, übersichtliche Teile zu zerlegen. So kann ein Defekt schnell eingegrenzt und behoben werden. Außerdem können durch die feine Granularität der so entstandenen Module auch komplexe Funktionen ganz nach Bedarf angepasst und wiederverwendet werden. 6 3 3.1 Syntax Atomare Datentypen Die atomaren Datentypen in Haskell sind ähnlich zu denen aus imperativen Programmiersprachen. Eine Besonderheit stellt hierbei der Datentyp Integer dar, der beliebig große ganzzahlige Werte darstellen kann. In der folgenden Tabelle findet man einen Überblick der atomaren Datentypen aus Haskell.[Lip11] [BN11] Datentyp Beschreibung Bool True, False Int 32 Bit Ganzzahl, -2147483648 bis 2147483647 Integer Beliebig Große Ganzzahl Float 32 Bit Gleitkommazahl Double 64 Bit Gleitkommazahl Char Beliebige ASCII Code Zeichen in Hochkommata, ’a’ 3.2 Signaturen Die Signatur einer Funktion kann man am besten mit einem Prototyp einer Funktion aus imperativen Sprachen Vergleichen. Sie wird definiert durch den Funktionsnamen gefolgt von zwei Doppelpunkten. Anschließend werden die Typen der Eingabeparameter aufgelistet getrennt durch den Pfeiloperator, der Letzte Datentyp in der Auflistung stellt dabei den Datentyp des Rückgabewertes dar. 7 Zur Verdeutlichung ein Beispiel: addzwei : : Int −> Int addzwei x = x + 2 Listing 1: Signatur Beispiel In der ersten Zeile ist die Signatur einer Funktion addzwei, diese bekommt einen einzigen Parameter vom Typ Int und hat einen Rückgabewert der ebenfalls vom Typ Int ist. In der zweiten Zeile ist das Verhalten der Funktion definiert. In diesem Fall addiert sie den Wert 2 zur eingegebenen Zahl hinzu. Haskell ist eine Typinferente Sprache. Das bedeutet, dass der Haskell Compiler den Datentyp einer Funktion selbst schlussfolgern kann und somit eine Funktionen nicht mit Datentypen deklariert werden muss. Obwohl man bei der Erstellung seiner eigenen Funktionen die Signatur nicht angeben muss, ist es dennoch ratsam es bei größeren Funktionen zu tun, um die Lesbarkeit des Codes nicht zu beeinträchtigen. Möchte man sich die Signatur einer Funktion im Interpreter ansehen kann man diese mittels :t ausgeben lassen.[Lip11][BN11] 3.3 Typvariablen und Polymorphe Funktionen Lässt man bei der obigen Funktion die Signatur weg und lässt sich den Typ der Funktion im Interpreter ausgeben, wird man folgende Ausgabe erhalten. g h c i > : t addzwei addzwei : : Num a => a −> a Listing 2: Signatur Beispiel 2 Anhand dieser Ausgabe möchten wir kurz das Prinzip der Typvariablen in Haskell anschneiden und den Num a => Part in das folgende Kapitel verschieben. Anstelle eines Datentypen steht nun eine Datentypvariable, was soviel bedeutet, dass die Funktion verschiedene Datentypen als Parameter entgegennehmen kann. Beispielsweise würde die Funktion sowohl mit einem Int als auch mit einem Double Eingabeparameter Funktionieren. Da der Datentyp des Eingabeparameters, sowie des Rückgabewertes beide die gleiche Typvariable haben, bedeutet dies, dass der Rückgabewert vom gleichen Datentyp wie der Eingabe Parameter sein muss. Hat man hingegen die Signatur func:: a->b->b , bedeutet dies nicht dass der Rückgabetyp einen Anderen Datentyp als der erste Eingabeparameter hat sondern lediglich, dass der Rückgabetyp und der Typ des zweiten Parameters vom gleichen Typ sind. [Lip11] [BN11] 8 3.4 Typklassen Wie im vorherigen Kapitel angesprochen wollen wir hier die Bedeutung von Num a => kurz erklären. Num a steht hierbei für die Typklasse Num , die der Parameter implementieren muss um als Eingabeparameter für diese Funktion geeignet zu sein. Eine Typklasse kann man sich am besten wie ein Interface aus imperativen Sprachen vorstellen, welches bestimmte Eigenschaften definiert. Da das Prinzip der Typklassen in dieser Arbeit keine besondere Rolle spielt wollen wir nicht näher darauf eingehen und dem Leser lediglich eine kleine Übersicht der vordefinierten Typklassen und deren Eigenschaften geben. Klasse Bedeutung Bounded Member haben ein ober und Untergrenze Enum Member können Aufgezählt werden Eq Member können auf Gleichheit überprüft werden Floating Member sind Gleitpunktzahlen Integral Member sind Ganzzahlig Num Member sind Zahlen Ord Member können der Größe nach Geordnet werden Read Member können aus Strings in Datentyp Umgewandelt werden Show Member können als String dargestellt werden [Lip11][BN11] 9 4 Funktionen Das wichtigste und namensgebende Konstrukt einer Funktionalen Programmiersprache ist die Funktion. Dabei Unterscheidet sich die Syntax von konventionellen Programmiersprachen wie C, C++ und Java. Funktionen in Beispielsweise C werden durch einen Rückgabetyp einem Funktionsbezeichner und einer Parameterliste durch Kommata getrennt eingeschlossen durch runde Klammern definiert. Es folgt ein Funktionsblock, der das Verhalten der Funktion beschreibt und definiert. Bei Haskell hingegen steht zuerst der Funktionsbezeichner gefolgt von einer Parameterliste getrennt durch Leerzeichen. Der Funktionsblock steht nach einem Gleichheitszeichen und wird durch Einrückung zusammengefasst oder kann durch Patternmatching eine andere Form haben; siehe hierzu 7.2. Ein Beispiel zur Veranschaulichung: −− Funktion i n C Int B e z e i c h n e r ( , , . . . ) { Anweisungsblock ; } −− Funktion i n H a s k e l l funktionsName Arg1 Arg2 = Anweisung Anweisung Anweisung −− Konkretes B e i s p i e l addiere x y = x + y Listing 3: Funktion Beispiel Auch das Aufrufen einer Funktion unterscheidet sich von imperativen Sprachen. Funktionen können entweder durch prefix Schreibweise aufgerufen werden oder durch infix Schreibweise. Üblicherweise wird die prefix Schreibweise bevorzugt. Die infix Variante eignet sich vor allem bei Funktionen, die Operationen auf zwei Parametern darstellen, wie zum Beispiel die Grundrechenarten. Die Grundrechenarten sind in Haskell auch Funktionen, werden aber aufgrund der besseren Lesbarkeit des Codes bevorzugt als infix Schreibweise verwendet. 10 Auch hierzu ein kleines Beispiel. −− Grundrechenarten a l s I n f i x S c f h r e i b w e i s e 3 + 4 5 − 3 2 ∗ 4 4 / 2 −− G a n z z a h l d i v i s i o n a l s p r e f i x S c h r e i b w e i s e div 14 6 mod 14 6 −− G a n z z a h l d i v i s i o n a l s i n f i x S c h r e i b w e i s e 14 ‘ div ‘ 6 14 ‘mod‘ 6 Listing 4: Infix/Prefix Beispiel Wer direkt eigene Funktionen schreiben und im Interpreter ausprobieren möchte hat die Möglichkeit diese in Form von Modulen in den Interpreter zu laden und zu testen. Eigene Module können definiert werden indem man seine Funktionen in eine Textdatei mit der Endung .hs schreibt. In den Interpreter können die Module dann mittels :l .hs eingebunden und direkt verwendet werden. Funktionen können auch in anderen Funktionen verwendet werden. Hierzu ein Beispiel. −− F u n k t i o n e l l e r P r o b l e m l o e s u n g s a n s a t z hochzwei x = x ∗ x h o c h v i e r x = hochzwei x ∗ hochzwei x h o c h v i e r 2 x = hochzwei ( hochzwei x ) Listing 5: Funktionelle Problemlösungsansatz Der Ausdruck hochzwei (hochzwei x) entspricht dabei dem Ausdruck hochzwei(hochzwei(x)) einer Imperativen Sprache. [Lip11][BN11] 11 5 5.1 Vordefinierte Datenstrukturen: Listen, Strings und Tupel Listen und Strings Eine der meist verwendeten Datenstrukturen in Haskell sind Listen. Sie lassen sich am besten mit Arrays aus imperativen Sprachen vergleichen. Listen werden mit eckigen Klammern notiert. Eine leere Liste sieht wie folgt aus: [] . Eine Liste mit Int Werten wird folgendermaßen notiert: [1, 2, 3] . Die Liste ist eine homogene Datenstruktur, was soviel bedeutet, dass eine Liste nur mit Elementen mit dem gleichen Datentyp befüllt werden kann. Versucht man eine Liste wie [1, ä"] zu erzeugen, wird der Compiler eine Fehlermeldung ausgeben. Listen können beliebig tief geschachtelt werden, allerdings ist dabei zu beachten, dass alle Listen die in der Äußersten Liste enthalten sind vom gleichen Typ sind. Strings sind in Haskell auch Listen und werden in doppelten Anführungszeichen notiert. “Beispiel“ ist dabei mit [’B’, ’e’, ’i’, ’s’, ’p’, ’i’, ’e’, ’l’] äquivalent. In Haskell gibt es drei vordefinierte Operatoren für das Arbeiten mit Listen. Für das verketten von Listen und Strings gibt es den ++ -Operator. g h c i > [ 1 , 2 , 3 ] ++ [ 3 , 4 , 5 ] [1 ,2 ,3 ,3 ,4 ,5] g h c i > " H a l l o " ++ " , ␣" ++ "Welt ! " " Hallo , ␣Welt ! " Listing 6: ++-Operator Beispiel Möchte man das n-te Element aus einer Liste, benutzt man den !! Operator, dabei beginnt die Indizierung bei 0 und das Element bleibt in der Liste enthalten. Wird ein Wert angegeben der größer ist als die Liste, gibt es eine Fehlermeldung. ghci> " Hallo " ! ! 0 ’H’ ghci> " Hallo " ! ! 6 ∗∗∗ Ex cep ti on : Prelude . ! ! : index t oo l a r g e Listing 7: !!-Operator Beispiel Ein weiterer wichtiger Operator, der mit Listen arbeitet, ist der : -Operator. Er hat zwei Bedeutungen. Zum einen wird er dafür verwendet um ein Element vorne in eine Liste einzufügen. Möchte man ein Element vorne in eine 12 Liste einfügen schreibt man dafür 1:[2,3] . Als Ergebnis erhält man die Liste [1,2,3] . Da der : -Operator Rechtsassoziativ ist, kann man auch 1:2:3:[] schreiben um die selbige Liste zu erhalten. Die zweite und noch wichtigere Funktion des : -Operators ist die Möglichkeit damit eine Liste in head und tail zu zerlegen. So gibt es in Haskell ca. ein dutzend vordefinierter Funktionen die auf Listen operieren welche mit dem : -Operator Implementiert sind. Vier dieser Funktionen möchten wir hier näher beleuchten, denn sie beschreiben wie Listen in Haskell zerlegt werden und sind wichtig für das Verständnis. head Gibt das erste Element einer Liste zurück tail Gibt alle Elemente einer Liste zurück, ausgenommen dem ersten init Gibt alle Elemente einer Liste zurück, ausgenommen dem letzten last Gibt das letzte Element einer Liste zurück im folgenden Beispiel werden diese Funktionen im Interpreter demonstriert dabei kommt das Schlüsselwort let zum Einsatz. Damit kann man sich auf die schnelle kurze Funktionen im Interpreter definieren. ghci> let l i s t = [ 1 , 2 , 3 , 4 , 5 ] g h c i > head l i s t 1 ghci> t a i l l i s t [2 ,3 ,4 ,5] ghci> i n i t l i s t [1 ,2 ,3 ,4] ghci> last l i s t 5 Listing 8: Listen Zerlegung Beispiel 13 Zur visuellen Veranschaulichung hierzu ein Bild. Abbildung 1: [Lip11] Beispielsweise sieht die Implementierung von Head mit dem : -Operator folgendermaßen aus. head ( x :_) = x Listing 9: Beispiel Head-Funktion Hierbei wird die als Parameter übergebene Liste innerhalb der Klammer in head und tail zerlegt. Es wird das erste Element durch den Doppelpunkt Operator in der Variablen x zwischengespeichert und kann dann rechts vom Gleichheitszeichen für weitere Berechnungen verwendet werden. Der Rest von der Liste wird in der _ -Variable verwahrt. Der _ wird als Wildcard bezeichnet und wird in Haskell als Variable für Daten verwendet, die in diesem Teil der Funktion keine besondere Rolle spielen. [Lip11] [BN11] 5.2 Tupel Tupel sind eine weitere Grundlegende Datenstruktur von Haskell. Tupel werden mit runden Klammern notiert. Die Elemente in einem Tupel müssen nicht homogen sein. Um Tupel in einer Liste zu verwahren, müssen diese vom gleichen Typ sein, denn wie wir bereits wissen ist die Liste eine homogene Datenstruktur. 14 Der Typ eines Tupels wird wie folgt definiert: 1. Anzahl der enthaltenen Elemente 2. Die Datentypen der Elemente 3. Die Position der Elemente Somit ist die Anzahl der möglichen Typen von Tupeln unendlich. Am Besten lässt sich das Anhand von mit Tupeln befüllten Listen verdeutlichen, da diese ja wie oben erwähnt nur Elemente vom gleichen Datentyp aufnehmen können. −− K o r r e k t e L i s t e mit Tupel [ ( "Hans" , 2 6 ) , ( " F r i t z " , 3 0 ) ] −− N i c h t K o r r e k t : Tupel n i c h t vom g l e i c h e n Typ [ ( "Hans" , 2 6 ) , ( 2 5 , 3 0 ) ] −− N i c h t K o r r e k t : R e i h e n f o l g e Stimmt n i c h t u e b e r e i n [ ( "Hans" , 2 6 ) , ( 3 0 , " F r i t z " ) ] Listing 10: Listen Zerlegung Beispiel [Lip11] [BN11] 6 Unendliche Listen, Lazy Evaluation und ListComprehensions Da Listen ein wichtiger Bestandteil von Haskell sind, sind diverse Möglichkeiten vorgesehen, solche zu erzeugen, zu durchsuchen und zu filtern. In diesem Kapitel möchten wir einige dieser Möglichkeiten näher betrachten. 6.1 Ranges und Lazy Evaluation Möchte man eine Liste der ganzen Zahlen von 1 bis 100 erzeugen, muss man nicht mühsam alle Zahlen einzeln eintippen sondern hat die Möglichkeit diese durch sogenannte Ranges zu definieren. Ranges werden wie Listen in eckigen Klammern notiert. Die erste Zahl bestimmt den Startwert, die zweite Zahl ist optional und wird durch ein Komma von der ersten getrennt und bestimmt die Schrittweite, danach kommen zwei Punkte und der Wert des größten Elements welches in der Liste enthalten sein soll. Der Ausdruck: [2, 4..100] definiert beispielsweise eine Liste mit geraden Zahlen von 2 bis 100. In Haskell kann man mittels Ranges auch unendliche Listen definieren, wenn 15 man diese jedoch ausgeben lässt wird das Programm erst terminieren, wenn der Speicher erschöpft ist. Aus diesem Grund bietet Haskell ein Prinzip welches als Lazy Evaluation bezeichnet wird. Erst dieses ermöglicht uns unendliche Listen zu erzeugen. Haskell geht dabei so vor, dass es die Liste immer nur soweit auswertet wie es muss. So kann man eine unendliche Liste definieren und beispielsweise die ersten 20 Zahlen mittels der take Funktion anfordern. Haskell wertet dabei nur die ersten 20 Elemente aus und ignoriert den Rest, denn Haskell ist ’faul’ und die restlichen Elemente werden gerade nicht benötigt. Hierzu ein Beispiel: −− Eine e i n f a c h e L i s t e n mit den Zahlen von −− 1 b i s 100 liste1 = [1..100] −− A l l e s geraden Zahlen von 2 b i s 100 liste2 = [2 ,4..100] −− U n e n d l i c h e L i s t e mit a l l e n N a t u e r l i c h e n Zahlen liste3 = [1..] −− Die e r s t e n 20 N a t u e r l i c h e n Zahlen l i s t e 4 = take 20 [ 1 . . ] Listing 11: Ranges Beispiel 6.2 List-Comprehensions Eine weitere Möglichkeit endliche und unendliche Listen zu erzeugen ist an die mathematische Mengen Notation angelehnt. So definiert {2n|n ≤ 20} in der Mathematik beispielsweise die Menge der geraden Zahlen von 2 bis 20. In Haskell lässt sich eine Liste der selben Menge verblüffend ähnlich durch [2*n| n <-[1..10]] erzeugen. Dabei wird der Ausdruck vor dem Pipe Operator als Ausgabefunktion bezeichnet. Nach dem Pipe Operator wird die Eingabemenge für n definiert, dabei sind sowohl endliche als auch unendliche Listen als Eingabe möglich. Durch den Pfeil-Operator und der Liste wird Intuitiv symbolisiert aus welcher Menge n seine Elemente bezieht. Nach der Eingabemenge lassen sich noch verschiedene Einschränkungen der Menge definieren, die als Prädikate bezeichnet werden und durch Kommata getrennt werden. Mit [2*n| n <-[1..10], 2*n >= 10] lässt sich die Menge auf Zahlen größer als 10 beschränken. Erfüllt ein von der Ausgabefunktion zurückgegebener Wert alle aufgelisteten Prädikate, so wird er in die Ausgabeliste 16 mit aufgenommen. Als Prädikat ist jede denkbare Funktion erlaubt die einen Wahrheitswert zurückgibt. Auch mehrere Eingabemengen sind erlaubt, dabei werden die Mengen im Kreuzprodukt mit einander kombiniert und nachdem sie durch die Ausgabefunktion gelaufen sind auf die angegebenen Prädikate getestet. Beispiel: −− E i n f a c h e L i s t Comprehension lC1 = [ x | x < − [ 1 . . 1 0 ] ] −− Demo g h c i > lC1 [1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10] −− L i s t Comprehension mit P r a e d i k a t lC2 = [ x | x < − [ 1 . . 1 0 ] , x ‘mod‘ 2 == 0 ] −− Demo g h c i > lC2 [2 ,4 ,6 ,8 ,10] −− L i s t Comprehension mit mehreren Eingabemengen −− D e m o n s t r i e r t Kreuzprodukt . lC3 = [ ( x , y , z ) | x <− [ ’ a ’ , ’ b ’ , ’ c ’ ] , y <− [ 1 , 2 , 3 ] , z <− [ ’ A’ , ’B’ , ’C ’ ] ] −− Demo g h c i > lC3 [ ( ’ a ’ , 1 , ’ A’ ) , ( ’ a ’ , 1 , ’ B’ ) , ( ’ a ’ , 1 , ’ C’ ) , ( ’ a ’ , 2 , ’ A’ ) , ( ’ a ’ , 2 , ’ B’ ) , ( ’ a ’ , 2 , ’ C’ ) , ( ’ a ’ , 3 , ’ A’ ) , ( ’ a ’ , 3 , ’ B’ ) , ( ’ a ’ , 3 , ’ C’ ) , ( ’ b ’ , 1 , ’ A’ ) , ( ’ b ’ , 1 , ’ B’ ) , ( ’ b ’ , 1 , ’ C’ ) , ( ’ b ’ , 2 , ’ A’ ) , ( ’ b ’ , 2 , ’ B’ ) , ( ’ b ’ , 2 , ’ C’ ) , ( ’ b ’ , 3 , ’ A’ ) , ( ’ b ’ , 3 , ’ B’ ) , ( ’ b ’ , 3 , ’ C’ ) , ( ’ c ’ , 1 , ’ A’ ) , ( ’ c ’ , 1 , ’ B’ ) , ( ’ c ’ , 1 , ’ C’ ) , ( ’ c ’ , 2 , ’ A’ ) , ( ’ c ’ , 2 , ’ B’ ) , ( ’ c ’ , 2 , ’ C’ ) , ( ’ c ’ , 3 , ’ A’ ) , ( ’ c ’ , 3 , ’ B’ ) , ( ’ c ’ , 3 , ’ C ’ ) ] Listing 12: List-Comprehensions Beispiel [Lip11][BN11] 17 7 7.1 Fallunterscheidungen If Then Else Wer schon einmal in einer imperativen Programmiersprache Programmiert hat kennt mit Sicherheit das If-Statement, anders als in C, C++ oder Java ist in Haskell das If Then Else-Statement jedoch ein Ausdruck. Das bedeutet es muss ein Wert zurückgegeben werden, weshalb der Else-Teil zwingend notwendig ist. Da es ein Ausdruck ist, lässt es sich auch inline notieren. Zur Verdeutlichung ein kleines Beispiel: g r o e s s e r Z e h n x = i f x > 10 then True e l s e False Listing 13: If-then-else Konstrukt Beispiel 7.2 Patternmatching Patternmatching in Haskell erinnert auf den ersten Blick an das Überladen von Funktionen aus anderen Programmiersprachen da der Funktionsname immer wieder untereinander mit verschieden aussehenden Parametern aufgerufen wird. Dem ist aber nicht so. Es ist vielmehr eine Art Fallunterscheidung, bei der die Funktionsparameter auf verschiedene Muster untersucht werden um dann den passenden Code auszuführen. Dabei ist zu beachten, dass die Übergabeparameter von oben nach unten mit den formulierten Muster verglichen werden. Das erste passende Muster wird genommen und der dazugehörige Code wird ausgeführt. Deshalb ist es wichtig die spezielleren Muster oben zu notieren und die generelleren unten. Wird kein passendes Muster gefunden wird eine Fehlermeldung ausgegeben. Deshalb ist es ratsam ein Muster zu formulieren welches die restlichen Fälle auffängt. Dabei kommen oft Variablen, Wildcards oder das Schlüsselwort otherwise zum Einsatz, welches per Definition zu jedem Muster passt und somit immer zu True ausgewertet wird. [Lip11] [BN11] 18 −− P a t t e r n m a t c h i n g E i n f u e h r e n d e s B e i s p i e l bewertung : : ( Integral a ) => a −> String bewertung 1 = " s e h r ␣ gut " bewertung 2 = " gut " bewertung 3 = " b e f r i e d i g e n d " bewertung 4 = " a u s r e i c h e n d " −−b e w e r t u n g x = " d u r c h g e f a l l e n " −−b e w e r t u n g o t h e r w i s e = " d u r c h g e f a l l e n " −−b e w e r t u n g _ = " d u r c h g e f a l l e n " −− D e m o n s t r i e r t A b a r b e i t u n g der F a e l l e bewertungF : : ( Integral a ) => a −> String bewertungF x = " d u r c h g e f a l l e n " bewertungF 1 = " s e h r ␣ gut " bewertungF 2 = " gut " bewertungF 3 = " b e f r i e d i g e n d " bewertungF 4 = " a u s r e i c h e n d " Listing 14: Patternmatching Beispiel 7.3 Guards Guards lassen sich am besten mit einem verzweigten if elif else Konstrukt aus anderen Sprachen vergleichen, nur sind Guards deutlich einfacher zu lesen. Was vor allem der gleichmäßigen Einrückung für alle Fallunterscheidungen, sowie der Einsparung von Zeilen durch das wegfallen der vielen Schlüsselwörter zu verdanken ist. Guards bzw. eine Fallunterscheidung werden durch den Pipe-Operator eingeleitet, danach folgt ein Ausdruck der zu einem Wahrheitswert ausgewertet wird. Nach einem Gleichheitszeichen folgt der Auszuführende Code. Wie beim Patternmatching kommt es auch hier auf die Reihenfolge der Bedingungsüberprüfung an. Die speziellen Guards müssen nach oben und die generellen nach unten, da die Bedingungen von oben nach unten sequenziell überprüft werden. Auch hier sollte ein Guard die übrigen Fälle abfangen da ansonsten eine Fehlermeldung ausgegeben wird. Vorzugsweise ist auch hier das Schlüsselwort otherwise zu verwenden. 19 Am besten lassen sich Guards jedoch anhand eines Beispiels erklären: bm iTell bmi | bmi <= 1 8 . 5 | bmi <= 2 5 . 0 | bmi <= 3 0 . 0 | otherwise = = " U n te r g e w ic h t " = "Normal" = " Uebergewicht " " Fettleibig " Listing 15: Beispiel Guards [Lip11] In diesem Beispiel kann ein Benutzer seinen BMI(Body-Mass-Index) eingeben und bekommt als Antwort seine körperliche Verfassung angezeigt. [Lip11][Lip11] 7.4 Case Expressions Case-Expressions lassen sich am Besten mit dem Case-Konstrukt aus imperativen Sprachen vergleichen. Mit Case-Expressions kann auf das Ergebnis eines Ausdrucks gezielt reagiert werden. Das Konstrukt wird mit dem Schlüsselwort Case eingeleitet, danach kommt der Ausdruck der die Verzweigung bestimmt, es folgt das Schlüsselwort of, danach eine gleichmäßig Eingerückte Folge von möglichen Werten die den Auszuführenden Code, für diesen Fall, nach einem Pfeil-Operator bereithält. ampel f a r b e = case f a r b e of " rot " −> " s t e h e n " " g e l b " −> " b e r e i t ␣ h a l t e n " " gruen " −> " gehen " Listing 16: Case-of Konstrukt Beispiel [Lip11][BN11] 8 Lokale Definitionen Mit den folgenden Programmier-Konstrukten lassen sich Hilfsfunktionen definieren, die der Übersichtlichkeit und Lesbarkeit des Programms dienen. 8.1 Lokale Definitionen mit Where Mit dem Schlüsselwort where lassen sich in einer Funktion Hilfsfunktionen definieren, welche nur in der Funktion sichtbar und von außen nicht zugänglich sind. Versucht man eine solche Funktion außerhalb der Funktion, in der 20 sie definiert ist, aufzurufen wird man eine Fehlermeldung vom Compiler erhalten. Auch hierzu ein Beispiel: bm iTell g e w i c h t g r o e s s e | bmi <= 1 8 . 5 = " U n te r g e w ic h t " | bmi <= 2 5 . 0 = "Normal" | bmi <= 3 0 . 0 = " Uebergewicht " | otherwise = " F e t t l e i b i g " where bmi = g e w i c h t / g r o e s s e ^ 2 Listing 17: Where Konstrukt Beispiel Im Beispiel wir nicht der BMI direkt angegeben, sondern Größe und Gewicht, aus denen das Programm dann selbst mittels der Hilfsfunktion den Index berechnet. [Lip11][BN11] 8.2 Lokale Definitionen mit Let-in Let-in Definitionen sind vergleichbar mit den oben behandelten where Definitionen. Der Unterschied liegt jedoch darin, dass Let-in bindings sich noch eine Stufe lokaler verhalten. Das Let-in Konstrukt ist an sich ein Ausdruck. Nach dem Schlüsselwort Let lassen sich ein oder mehrere Ausrücke definieren die dann nach dem Schlüsselwort in verwendet werden können. Da das let in Konstrukt ein Ausdruck ist kann es überall dort stehen wo ein Ausdruckt erwartet wird. Die in Let definierten Funktionen sind jedoch so lokal, dass wenn es in einem Guard definiert wird es in den anderen benachbarten Guards nicht sichtbar ist. Die Syntax lautet Let in Möchte man mehr als eine Definition inline schreiben, müssen diese durch Semikolons getrennt werden. Beispiel: c y l i n d e r : : ( RealFloat a ) => a −> a −> a cylinder r h = l e t s i d e A r e a = 2 ∗ pi ∗ r ∗ h topArea = pi ∗ r ^ 2 in s i d e A r e a + 2 ∗ topArea Listing 18: Let-in Konstrukt Beispiel Diese Funktion cylinder berechnet aus der Höhe und dem Radius eines Zylinders, unter Zuhilfenahme der vordefinierten Konstante π, dessen Gesamtoberfläche. Die Hilfsfunktionen sideArea und topArea sind dabei nur innerhalb des in-Statements sichtbar. [Lip11][BN11] 21 9 Rekursionen Ein Konzept aus den herkömmlichen Programmiersprachen, das in Haskell nicht verwendet wird sind Schleifen. Durch das Fehlen von Programmzuständen und Zählvariablen sind Schleifen auch gar nicht umsetzbar. Alle Schleifendurchläufe hätten dasselbe Ergebnis und es gäbe keine Abbruchbedingung. Stattdessen werden in Haskell Probleme die das mehrfache Durchlaufen von Codeabschnitten benötigen, mithilfe von Rekursionen gelöst. Um die Bedeutung von Rekursionen für Haskell zu unterstreichen wollen wir im folgenden einige mögliche Implementationen von Standardfunktionen durchgehen und somit das Verständnis für Haskell fördern. Dabei kommen, zur Verdeutlichung, viele in den vorangehenden Kapiteln erklärte Konstrukte und Operatoren zum Einsatz. 9.1 Die Funktion take Ein gutes Eingangsbeispiel ist die Funktion take , die als ersten Parameter die Anzahl der zurückzugebenden Elemente einer Liste und als zweiten Parameter die Liste, aus der die Elemente entnommen werden sollen erhält. Möchte man nur das erste oder das zweite Element zurückgeben lässt es sich einfach durch den : -Operator formulieren: e i n s : : [ a ] −> [ a ] e i n s ( x : xs ) = x : [ ] z w e i : : [ a ] −> [ a ] z w e i ( x : y : xys ) = x : y : [ ] Listing 19: Implementierung first second Beispiel Möchte man aber eine Liste mit beliebig vielen Elementen zurückgeben ist dieser Ansatz nicht zielführend, denn man müsste auf diese Weise unendlich viele Funktionen definieren. Den Ansatz eine for-Schleife mit n Iterationen über die Liste laufen zu lassen gibt es in Haskell nicht. In Haskell werden Probleme dieser Art Rekursiv gelöst. 22 Bei der folgenden Implementierung wird das Konzept des Patternmatching verwendet um das Problem zu Lösen. nehme nehme nehme nehme nehme :: n 0 1 n Int −> [ a ] −> [ a ] [ ] = error " Fehlermeldung " ( x : xs ) = [ ] ( x :_) = [ x ] ( x : xs ) = x : nehme ( n−1) xs −−g h c i > nehme 1 [ 1 , 2 , 3 ] −−[ 1 ] −−g h c i > nehme 2 [ 1 , 2 , 3 ] −−[ 1 , 2 ] −−g h c i > nehme 3 [ 1 , 2 , 3 ] −−[ 1 , 2 , 3 ] Listing 20: Implementierung take Beispiel Jedoch hat die obige Funktion noch eine Schwachstelle. Ruft man die Funktion mit einer leeren Liste auf bekommt man eine Fehlermeldung, denn eine leere Liste lässt sich nicht durch x:xs zerlegen. Deshalb fügen wir die folgende Zeile nach der Signatur ein nehme n [] = error Fehlermeldung . Eine ähnliche Funktion ist die last -Funktion, die das letzte Element einer Liste zurückliefert. Auf den ersten Blick ist diese Problemstellung schwieriger als die vorherige, jedoch ist es nur eine Frage des richtigen Rekursionsankers. Das letzte Element einer Einelementigen Liste ist immer das eine Element. Ansonsten wir immer das erste Element entfernt bis eine Einelementige Liste übrig bleibt und das Problem ist gelöst. Selbstverständlich sollte hierbei auf unendliche Listen geachtet werden, die per Definition kein ’letztes’ Element besitzen. 9.2 Endrekursion Eine Besonderheit des GHC ist die Rekursionsoptimierung, im Speziellen die Endrekursion. Diese Art der Optimierung ermöglicht es beliebig tiefe Rekursionen mit minimalem und konstantem Speicherverbrauch auszuwerten. Im Folgenden sehen wir die Implementierung der Gaußschen Summenformel und Darstellung des Speichers bei der Ausführung der Funktion: 23 gaus_r : : Integer −> Integer gaus_r 0 = 0 gaus_r n = n + gaus_r ( n−1) Listing 21: Implementierung gaus 3 = 3 gaus 2 = gaus 1 gaus gaus 1 gaus 2 = gaus 3 = 3 + 2 = 0 = 2 + gaus 2 + gaus 1 1 + gaus 0 = 0 −−R e k u r s i o n s a b b r u c h 1 + 0 + 1 2 Listing 22: Darstellung im Speicher Es ist leicht zu erkennen, dass der Speicherverbrauch mit zunehmender Eingabegröße schnell in problematische Höhe steigt. Schon bei Eingaben n > 1000 kann es bei Umgebungen mit begrenztem Speicherplatz, wie zum Beispiel eingebetteten Systemen, zu Ausfällen kommen. Hier kommt das Konzept der Endrekursion zur Anwendung. Durch eine Hilfsfunktion mit einem zusätzlichen Parameter ist es möglich die Zwischenergebnisse der Rekursionsaufrufe zwischenzuspeichern und so den Speicheraufwand zu minimieren. gaus Integer −> Integer gaus n = gaus_tr 0 n gaus_tr Integer Integer −> Integer gaus_tr m n = i f n=0 then m e l s e gaus_tr m+n n−1 Listing 23: Implementierung mit Endrekursion gaus 3 = = = = = gaus_tr gaus_tr gaus_tr gaus_tr 6 0 3 5 6 3 2 1 0 Listing 24: Darstellung der Endrekursion im Speicher Zu beachten ist hier: die Laufzeit der beiden Implementierungen sind beinahe identisch, da bei der Endrekursion immer zwei Rechenoperationen pro Zeile ausgeführt werden. 24 10 Funktionen Höherer Ordnung Eine Funktion, die als Parameter eine Funktion entgegennimmt oder als Rückgabewert zurückgibt, wird als eine Funktion Höherer Ordnung bezeichnet. Am besten lässt sich solch eine Funktion mit einer Funktion aus C vergleichen, welche als Argument einen Funktionspointer entgegennimmt oder zurückgibt. In Haskell kann man solche Funktionen schon an der Signatur erkennen. Als Beispiel möchten wir function:: (Int -> Int) -> Int -> Int heranziehen. Diese Signatur zeigt eine Funktion: function , die als ersten Parameter eine Funktion entgegennimmt, welche einen Parameter vom Typ Int entgegennimmt und ein Int zurückliefert. Als zweiten Parameter bekommt function einen Int und liefert zuletzt ebenfalls einen Int Wert zurück. Die Implementierung könnte folgendermaßen aussehen. f u n c t i o n : : ( Int −> Int ) −> Int −> Int function f i = ( f i ) + 1 g h c i > f u n c t i o n (+1) 1 3 ghci> ghci> Listing 25: Funktion als Parameter Beispiel 11 Mapping Das Abbilden von einzelnen Elementen aus einer Liste, durch eine beliebige Funktion, in eine neue Liste wird als mapping bezeichnet. Da mapping eine häufig auftretende Problemstellung ist gibt es in Haskell die vordefinierte Funktion map . Diese Funktion bekommt als ersten Parameter eine Abbildungsfunktion für die einzelnen Elemente und als zweiten Parameter eine Liste. Hierzu ein Beispiel: f u n c t i o n : : ( Int −> Int ) −> Int −> Int function f i = ( f i ) + 1 g h c i > f u n c t i o n (+1) 1 3 ghci> ghci> Listing 26: Mapping Rekursiv Beispiel 25 Die selbe Funktion lässt sich anstatt Rekursiv auch mit Hilfe der bereits kennengelernten List-Comprehensions Formulieren: mapListC : : ( a −> b ) −> [ a ] −> [ b ] mapListC f xs = [ f x | x <− xs ] Listing 27: Mapping List-Comprehension Beispiel 12 Filtering Was als Filtering in Haskell bezeichnet wird ist, recht ähnlich mit Mapping aus dem vorherigen Abschnitt. Der Unterschied liegt darin, dass als Funktion ein Prädikat übergeben wird, welches durch das Überprüfen einer oder mehrerer Eigenschaften bestimmt ob das Element in die neue Liste mit aufgenommen wird. 13 Fazit Aus unseren Untersuchungen und Experimenten mit der Funktionalen Sprache Haskell haben wir erkannt, dass durch die Vereinfachung von Definition und Anwendung von Funktionen sowohl der Programmieraufwand als auch die Laufzeit des daraus entstehenden Programms erheblich verbessert werden. Durch den Wegfall von Programmzuständen, die gute Unterstützung von Rekursion und die Lazy-Evaluation können selbst resourcenintensive Berechnungen wie 100000! in Rekordzeit und mit minimalem Speicheraufwand durchgeführt werden. Die mit Listen und entsprechenden Filtern erzeugten Mengen ermöglichen die unkomplizierte Anwendung von Operationen der Mengenlehre, und lassen sich mit Funktionen Höherer Ordnung sogar zu Mathematischen Gruppen und Körpern übertragen. Allerdings eignet sich Haskell nicht für komplexe, eigenständige Programme, da diese meist auf einem zustandsbehafteten Automaten beruhen und Haskell dieses Konzept der Informatik nicht unterstützt. Am besten eignet sich Haskell unseren Ergebnissen nach als Sprache für ein Unterprogramm, das Berechnungen für ein umfassenderes Oberprogramm übernimmt, beispielsweise eine Taschenrechner-Anwendung. Durch seine hohe Performance und die Fähigkeit, mit beliebig großen Zahlen umgehen zu können, würde Haskell selbst bei komplexen Berechnungen schnelle Ergebnisse liefern und so das Oberprogramm beschleunigen. Außerdem können mit 26 dem Datentyp Integer, ähnlich wie in Python, beliebig große Zahlen verarbeitet werden. Das legt die Anwendung in Bereichen der Astronomie und Chemie nahe, die zum Beispiel mit großen Distanzen oder großen Teilchenmengen rechnen. 27 14 Literaturverzeichnis und Verweise Literatur [BN11] Marco Block and Adrian Neumann. Haskell Intensivkurs. Springer Verlag Berlin Heidelber, 1st edition, 2011. [Lip11] Miran Lipovača. Learn You a Haskell for Great Good! no starch press, 1st edition, 2011. [Wik] Wikipedia. Glasgow haskell compiler. Wikipedia. 28