Fp Colleges
Center
FP
1 Functioneel Programmeren 3
1.1 Functionele talen 3
1.1.1 Functies 3
1.1.2 Talen 4
1.2 De Haskell-interpreter 4
1.2.1 Expressies uitrekenen 4
1.2.2 Functies defini ̈eren 6
1.2.3 Opdrachten aan de interpreter 8
1.3 Standaardfuncties 8
1.3.1 Ingebouwd/voorgedefinieerd 8
1.3.2 Namen van functies en operatoren 8
1.3.3 Functies op getallen 10
1.3.4 Boolese functies 11
1.3.5 Functies op lijsten 12
1.3.6 Functies op functies 12
1.4 Functie-definities 13
1.4.1 Definitie door combinatie 13
1.4.2 Definitie door gevalsonderscheid 14
1.4.3 Definitie door patroonherkenning 14
1.4.4 Definitie door recursie of inductie 16
1.4.5 Layout en commentaar 17
1.5 Typering 18
1.5.1 Soorten fouten 18
1.5.2 Typering van expressies 19
1.5.3 Polymorfie 21
1.5.4 Functies met meer parameters 22
1.5.5 Overloading 22
2 Getallen en functies 27
2.1 Operatoren 27
2.1.1 Operatoren als functies en andersom 27
2.1.2 Prioriteiten 27
2.1.3 Associatie 28
2.1.4 Definitie van operatoren 29
2.2 Currying 29
2.2.1 Partieel parametriseren 29
2.2.2 Haakjes 30
2.2.3 Operator-secties 31
2.3 Functies als parameter 31
2.3.1 Functies op lijsten 31
2.3.2 Iteratie 33
2.3.3 Samenstelling 34
2.3.4 De lambda-notatie 35
2.4 Numerieke functies 35
2.4.1 Rekenen met gehele getallen 35
2.4.2 Numeriek differenti ̈eren 38
2.4.3 Zelfgemaakte wortel 39
2.4.4 Nulpunt van een functie 39
2.4.5 Inverse van een functie 40
3 IO in Haskell 43
3.1 Inleiding 43
3.2 Acties 44
3.2.1 Lezen en schrijven van een enkel karakter 44
3.2.2 Combineren van acties 44
3.3 Recursieve acties 45
3.4 Acties met resultaten 45
3.5 Het hoofdprogramma 46
3.6 Een groter voorbeeld: getal raden 46
3.7 Imperatief programmeren voorbij 47
3.8 Andere acties 47
4 Lijsten 49
4.1 Lijsten 49
4.1.1 Opbouw van een lijst 49
4.1.2 Functies op lijsten 50
4.1.3 Hogere-orde functies op lijsten 53
4.1.4 Lijsten vergelijken en ordenen 55
4.1.5 Lijsten sorteren 57
4.2 Speciale lijsten 59
4.2.1 Strings 59
4.2.2 Characters 60
4.2.3 Functies op characters en strings 61
4.2.4 Oneindige lijsten 63
4.2.5 Lazy evaluatie 63
4.2.6 Functies op oneindige lijsten 64
4.2.7 Lijst-comprehensies 67
4.3 Tupels 68
4.3.1 Gebruik van tupels 68
4.3.2 Type-definities 69
4.3.3 Rationale getallen 70
4.3.4 Tupels en lijsten 71
4.3.5 Tupels en Currying 72
Opgaven 72
5 Datastructuren 75
5.1 Datatypes 75
5.1.1 Enumeratietypes 75
5.1.2 Constructoren met parameters 76
5.1.3 Beschermde types 76
5.1.4 Polymorfe datatypes 77
5.1.5 Recursieve datatypes 78
5.1.6 Lijsten: een speciaal soort bomen 79
5.1.7 Zoekbomen 80
6 Algoritmen op lijsten 87
6.1 Combinatorische functies 87
6.1.1 Segmenten en deelrijen 87
6.1.2 Permutaties en combinaties 89
6.1.3 De @-notatie 91
6.2 Matrixrekening 91
6.2.1 Vectoren en matrices 91
6.2.2 Elementaire operaties 94
6.2.3 Determinant en inverse 98
6.3 Polynomen 100
6.3.1 Representatie 100
6.3.2 Vereenvoudiging 101
6.3.3 Rekenkundige operaties 103
Opgaven 104
7 Algoritmen op bomen 107
7.1 Rekenkundige expressies 107
7.2 Symbolisch differenti ̈eren 108
7.3 Andere expressiebomen 109
7.4 Stringrepresentatie van een boom 109
8 Combinator Talen 113
8.1 Inleiding 113
8.2 Parser Combinators 113
8.2.1 Parser-combinators 114
8.3 Ontleden van expressies 116
8.4 Meer parser-combinators 117
9 Klassen en hun instanties 119
9.1 Numerieke types 119
9.1.1 Overloading 119
9.1.2 Classes en instances 119
9.1.3 Nieuwe numerieke types 120
9.1.4 Numerieke constanten 121
9.2 Ordening en gelijkheid 122
9.2.1 Default-definities 122
9.2.2 Klassen met voorwaarden 123
9.2.3 Instances met voorwaarden 124
9.2.4 Standaard-klassen 125
9.2.5 Problemen met klassen 126
9.3 Klassen en wetten 128
9.3.1 Wetten voor standaardklassen 128
9.3.2 Een klasse-hi ̈erarchie 129
9.3.3 Afgeleide operatoren 131
9.3.4 Instances van de klassen 132
9.3.5 Polynoomringen 134
9.3.6 Quoti ̈entenlichamen 136
9.3.7 Matrixringen 137
10 Graphical User Interfaces 139
11 Programmatransformatie 153
11.1 Effici ̈entie 153
11.1.1 Tijdgebruik 153
11.1.2 Complexiteitsanalyse 154
11.1.3 Verbeteren van effici ̈entie 155
11.1.4 Geheugengebruik 158
11.2 Wetten 161
11.2.1 Wiskundige wetten 161
11.2.2 Haskell-wetten 162
11.2.3 Bewijzen van wetten 163
11.2.4 Inductieve bewijzen 165
11.2.5 Verbetering van effici ̈entie 167
11.2.6 Eigenschappen van functies 170
11.2.7 Polymorfie 174
11.2.8 Bewijzen van rekenkundige wetten 176
12 Case Study: Finger Trees 181
A Kennismakingspracticum 183
B Practicumopgaven 195
B.0 Oefenopgaven 195
B.1 Complexe getallen 196
B.2 Teksten 198
B.3 Formulemanipulatie 200
B.4 Predicatenlogica 202
B.5 De klasse ‘Verzameling’ 206
B.6 Parsen van predicaten 207
B.7 Chipknip kaarten 207
C ISO/ASCII tabel 211
D Haskell syntaxdiagrammen 213
E Haskell syntax 223
F The overloaded Standard Prelude for the Helium Compiler 227
F.1 Operator priorities 227
F.2 Num 227
F.3 Eq 227
F.4 Ord 228
F.5 Enum 228
F.6 Int 228
F.7 Float 229
F.8 Bool 230
F.9 Maybe 230
F.10 Either 230
F.11 Ordering 230
F.12 Tuples 230
F.13 Char 231
F.14 List 231
F.15 Conversion 234
F.16 Some standard functions 234
F.17 IO 235
F.18 Read 236
G Lisp voor Haskell-kenners 237
G.1 Expressies 237
G.1.1 Functie-aanroep 237
G.1.2 Operatoren 237
G.1.3 Lijsten 237
G.2 Functies op lijsten 238
G.3 Functiedefinitie 238
G.3.1 Simpele definitie 238
G.3.2 Definitie met gevalsonderscheid 238
G.3.3 Definitie met patronen 239
G.3.4 Evaluatie 239
G.4 Typering 239
G.4.1 Statisch versus dynamisch 239
G.4.2 Types van lijsten 240
G.4.3 Overloading 240
G.4.4 Polymorfie 240
G.5 Hogere-ordefuncties 240
G.5.1 Map / Mapcar 240
G.5.2 Foldr / Reduce 241
G.5.3 Currying / Lambda-notatie 241
G.6 Filosofie 241
G.6.1 Haskell: referentieel transparant 241
G.6.2 Lisp: meta-circulair 241
G.7 Haskell en Prolog 243
G.7.1 Lijsten 243
G.7.2 Functies en relaties 243
G.7.3 Patronen 243
G.7.4 Richtingloze definities 243
G.7.5 Constructorfuncties 244
H Literatuur 245
I Woordenlijst 247
J Oude Tentamenvragen 253
K Antwoorden 267
