-
Notifications
You must be signed in to change notification settings - Fork 556
Expand file tree
/
Copy pathpart1.html
More file actions
6428 lines (6419 loc) · 633 KB
/
part1.html
File metadata and controls
6428 lines (6419 loc) · 633 KB
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>Haskell Mooc, part 1</title>
<style type="text/css">
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
span.underline{text-decoration: underline;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
</style>
<style type="text/css">
pre > code.sourceCode { white-space: pre; position: relative; }
pre > code.sourceCode > span { line-height: 1.25; }
pre > code.sourceCode > span:empty { height: 1.2em; }
.sourceCode { overflow: visible; }
code.sourceCode > span { color: inherit; text-decoration: inherit; }
div.sourceCode { margin: 1em 0; }
pre.sourceCode { margin: 0; }
@media screen {
div.sourceCode { overflow: auto; }
}
@media print {
pre > code.sourceCode { white-space: pre-wrap; }
pre > code.sourceCode > span { display: inline-block; text-indent: -5em; padding-left: 5em; }
}
pre.numberSource code
{ counter-reset: source-line 0; }
pre.numberSource code > span
{ position: relative; left: -4em; counter-increment: source-line; }
pre.numberSource code > span > a:first-child::before
{ content: counter(source-line);
position: relative; left: -1em; text-align: right; vertical-align: baseline;
border: none; display: inline-block;
-webkit-touch-callout: none; -webkit-user-select: none;
-khtml-user-select: none; -moz-user-select: none;
-ms-user-select: none; user-select: none;
padding: 0 4px; width: 4em;
color: #aaaaaa;
}
pre.numberSource { margin-left: 3em; border-left: 1px solid #aaaaaa; padding-left: 4px; }
div.sourceCode
{ }
@media screen {
pre > code.sourceCode > span > a:first-child::before { text-decoration: underline; }
}
code span.al { color: #ff0000; font-weight: bold; } /* Alert */
code span.an { color: #60a0b0; font-weight: bold; font-style: italic; } /* Annotation */
code span.at { color: #7d9029; } /* Attribute */
code span.bn { color: #40a070; } /* BaseN */
code span.bu { color: #008000; } /* BuiltIn */
code span.cf { color: #007020; font-weight: bold; } /* ControlFlow */
code span.ch { color: #4070a0; } /* Char */
code span.cn { color: #880000; } /* Constant */
code span.co { color: #60a0b0; font-style: italic; } /* Comment */
code span.cv { color: #60a0b0; font-weight: bold; font-style: italic; } /* CommentVar */
code span.do { color: #ba2121; font-style: italic; } /* Documentation */
code span.dt { color: #902000; } /* DataType */
code span.dv { color: #40a070; } /* DecVal */
code span.er { color: #ff0000; font-weight: bold; } /* Error */
code span.ex { } /* Extension */
code span.fl { color: #40a070; } /* Float */
code span.fu { color: #06287e; } /* Function */
code span.im { color: #008000; font-weight: bold; } /* Import */
code span.in { color: #60a0b0; font-weight: bold; font-style: italic; } /* Information */
code span.kw { color: #007020; font-weight: bold; } /* Keyword */
code span.op { color: #666666; } /* Operator */
code span.ot { color: #007020; } /* Other */
code span.pp { color: #bc7a00; } /* Preprocessor */
code span.sc { color: #4070a0; } /* SpecialChar */
code span.ss { color: #bb6688; } /* SpecialString */
code span.st { color: #4070a0; } /* String */
code span.va { color: #19177c; } /* Variable */
code span.vs { color: #4070a0; } /* VerbatimString */
code span.wa { color: #60a0b0; font-weight: bold; font-style: italic; } /* Warning */
</style>
<link rel="stylesheet" href="./style.css">
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<div id="everything">
<nav id="TOC">
<ul>
<li><a href="#lecture-1-and-so-it-begins"
id="toc-lecture-1-and-so-it-begins"><span
class="toc-section-number">1</span> Lecture 1: …And so It Begins</a>
<ul>
<li><a href="#about-the-course" id="toc-about-the-course"><span
class="toc-section-number">1.1</span> About the Course</a></li>
<li><a href="#read-these" id="toc-read-these"><span
class="toc-section-number">1.2</span> Read These</a></li>
<li><a href="#haskell" id="toc-haskell"><span
class="toc-section-number">1.3</span> Haskell</a></li>
<li><a href="#running-haskell" id="toc-running-haskell"><span
class="toc-section-number">1.4</span> Running Haskell</a></li>
<li><a href="#lets-start" id="toc-lets-start"><span
class="toc-section-number">1.5</span> Let’s Start!</a></li>
<li><a href="#expressions-and-types"
id="toc-expressions-and-types"><span
class="toc-section-number">1.6</span> Expressions and Types</a></li>
<li><a href="#the-structure-of-a-haskell-program"
id="toc-the-structure-of-a-haskell-program"><span
class="toc-section-number">1.7</span> The Structure of a Haskell
Program</a></li>
<li><a href="#working-with-examples"
id="toc-working-with-examples"><span
class="toc-section-number">1.8</span> Working with Examples</a></li>
<li><a href="#how-do-i-get-anything-done"
id="toc-how-do-i-get-anything-done"><span
class="toc-section-number">1.9</span> How Do I Get Anything
Done?</a></li>
<li><a href="#all-together-now" id="toc-all-together-now"><span
class="toc-section-number">1.10</span> All Together Now!</a></li>
<li><a href="#a-word-about-indentation"
id="toc-a-word-about-indentation"><span
class="toc-section-number">1.11</span> A Word About Indentation</a></li>
<li><a href="#quiz" id="toc-quiz"><span
class="toc-section-number">1.12</span> Quiz</a></li>
<li><a href="#working-on-the-exercises"
id="toc-working-on-the-exercises"><span
class="toc-section-number">1.13</span> Working on the Exercises</a></li>
<li><a href="#exercises" id="toc-exercises"><span
class="toc-section-number">1.14</span> Exercises</a></li>
</ul></li>
<li><a href="#lecture-2-either-you-die-a-hero"
id="toc-lecture-2-either-you-die-a-hero"><span
class="toc-section-number">2</span> Lecture 2: Either You Die a
Hero…</a>
<ul>
<li><a href="#recursion-and-helper-functions"
id="toc-recursion-and-helper-functions"><span
class="toc-section-number">2.1</span> Recursion and Helper
Functions</a></li>
<li><a href="#guards" id="toc-guards"><span
class="toc-section-number">2.2</span> Guards</a></li>
<li><a href="#lists" id="toc-lists"><span
class="toc-section-number">2.3</span> Lists</a></li>
<li><a href="#a-word-about-immutability-1"
id="toc-a-word-about-immutability-1"><span
class="toc-section-number">2.4</span> A Word About Immutability</a></li>
<li><a href="#a-word-about-type-inference-and-polymorphism"
id="toc-a-word-about-type-inference-and-polymorphism"><span
class="toc-section-number">2.5</span> A Word About Type Inference and
Polymorphism</a></li>
<li><a href="#the-maybe-type" id="toc-the-maybe-type"><span
class="toc-section-number">2.6</span> The <code>Maybe</code>
Type</a></li>
<li><a href="#sidenote-constructors"
id="toc-sidenote-constructors"><span
class="toc-section-number">2.7</span> Sidenote: Constructors</a></li>
<li><a href="#the-either-type" id="toc-the-either-type"><span
class="toc-section-number">2.8</span> The <code>Either</code>
type</a></li>
<li><a href="#the-case-of-expression"
id="toc-the-case-of-expression"><span
class="toc-section-number">2.9</span> The case-of Expression</a></li>
<li><a href="#recap-pattern-matching"
id="toc-recap-pattern-matching"><span
class="toc-section-number">2.10</span> Recap: Pattern Matching</a></li>
<li><a href="#quiz-1" id="toc-quiz-1"><span
class="toc-section-number">2.11</span> Quiz</a></li>
<li><a href="#exercises-1" id="toc-exercises-1"><span
class="toc-section-number">2.12</span> Exercises</a></li>
</ul></li>
<li><a href="#lecture-3-catamorphic"
id="toc-lecture-3-catamorphic"><span class="toc-section-number">3</span>
Lecture 3: Catamorphic</a>
<ul>
<li><a href="#functional-programming-at-last"
id="toc-functional-programming-at-last"><span
class="toc-section-number">3.1</span> Functional Programming, at
Last</a></li>
<li><a href="#partial-application" id="toc-partial-application"><span
class="toc-section-number">3.2</span> Partial Application</a></li>
<li><a href="#prefix-and-infix-notations"
id="toc-prefix-and-infix-notations"><span
class="toc-section-number">3.3</span> Prefix and Infix
Notations</a></li>
<li><a href="#lambdas" id="toc-lambdas"><span
class="toc-section-number">3.4</span> Lambdas</a></li>
<li><a href="#sidenote-the-.-and-operators"
id="toc-sidenote-the-.-and-operators"><span
class="toc-section-number">3.5</span> Sidenote: The <code>.</code> and
<code>$</code> Operators</a></li>
<li><a href="#example-rewriting-whatfollows"
id="toc-example-rewriting-whatfollows"><span
class="toc-section-number">3.6</span> Example: Rewriting
<code>whatFollows</code></a></li>
<li><a href="#more-functional-list-wrangling-examples"
id="toc-more-functional-list-wrangling-examples"><span
class="toc-section-number">3.7</span> More Functional List Wrangling
Examples</a></li>
<li><a href="#lists-and-recursion" id="toc-lists-and-recursion"><span
class="toc-section-number">3.8</span> Lists and Recursion</a></li>
<li><a href="#something-fun-list-comprehensions"
id="toc-something-fun-list-comprehensions"><span
class="toc-section-number">3.9</span> Something Fun: List
Comprehensions</a></li>
<li><a href="#something-fun-custom-operators"
id="toc-something-fun-custom-operators"><span
class="toc-section-number">3.10</span> Something Fun: Custom
Operators</a></li>
<li><a href="#something-useful-typed-holes"
id="toc-something-useful-typed-holes"><span
class="toc-section-number">3.11</span> Something Useful: Typed
Holes</a></li>
<li><a href="#quiz-2" id="toc-quiz-2"><span
class="toc-section-number">3.12</span> Quiz</a></li>
<li><a href="#exercises-2" id="toc-exercises-2"><span
class="toc-section-number">3.13</span> Exercises</a></li>
</ul></li>
<li><a href="#lecture-4-real-classy"
id="toc-lecture-4-real-classy"><span class="toc-section-number">4</span>
Lecture 4: Real Classy</a>
<ul>
<li><a href="#sidenote-tuples" id="toc-sidenote-tuples"><span
class="toc-section-number">4.1</span> Sidenote: Tuples</a></li>
<li><a href="#interlude-folding" id="toc-interlude-folding"><span
class="toc-section-number">4.2</span> Interlude: Folding</a></li>
<li><a href="#type-classes" id="toc-type-classes"><span
class="toc-section-number">4.3</span> Type Classes</a></li>
<li><a href="#type-constraints" id="toc-type-constraints"><span
class="toc-section-number">4.4</span> Type Constraints</a></li>
<li><a href="#standard-type-classes"
id="toc-standard-type-classes"><span
class="toc-section-number">4.5</span> Standard Type Classes</a></li>
<li><a href="#more-data-structures" id="toc-more-data-structures"><span
class="toc-section-number">4.6</span> More Data Structures</a></li>
<li><a href="#reading-docs" id="toc-reading-docs"><span
class="toc-section-number">4.7</span> Reading Docs</a></li>
<li><a href="#quiz-3" id="toc-quiz-3"><span
class="toc-section-number">4.8</span> Quiz</a></li>
<li><a href="#exercises-3" id="toc-exercises-3"><span
class="toc-section-number">4.9</span> Exercises</a></li>
</ul></li>
<li><a href="#lecture-5-you-need-string-for-a-knot"
id="toc-lecture-5-you-need-string-for-a-knot"><span
class="toc-section-number">5</span> Lecture 5: You Need String for a
Knot</a>
<ul>
<li><a href="#algebraic-datatypes" id="toc-algebraic-datatypes"><span
class="toc-section-number">5.1</span> Algebraic Datatypes</a></li>
<li><a href="#type-parameters" id="toc-type-parameters"><span
class="toc-section-number">5.2</span> Type Parameters</a></li>
<li><a href="#recursive-types" id="toc-recursive-types"><span
class="toc-section-number">5.3</span> Recursive Types</a></li>
<li><a href="#record-syntax" id="toc-record-syntax"><span
class="toc-section-number">5.4</span> Record Syntax</a></li>
<li><a href="#algebraic-datatypes-summary"
id="toc-algebraic-datatypes-summary"><span
class="toc-section-number">5.5</span> Algebraic Datatypes:
Summary</a></li>
<li><a href="#sidenote-other-ways-of-defining-types"
id="toc-sidenote-other-ways-of-defining-types"><span
class="toc-section-number">5.6</span> Sidenote: Other Ways of Defining
Types</a></li>
<li><a href="#how-do-algebraic-datatypes-work"
id="toc-how-do-algebraic-datatypes-work"><span
class="toc-section-number">5.7</span> How Do Algebraic Datatypes
Work?</a></li>
<li><a href="#quiz-4" id="toc-quiz-4"><span
class="toc-section-number">5.8</span> Quiz</a></li>
<li><a href="#exercises-4" id="toc-exercises-4"><span
class="toc-section-number">5.9</span> Exercises</a></li>
</ul></li>
<li><a href="#lecture-6-working-class-hero"
id="toc-lecture-6-working-class-hero"><span
class="toc-section-number">6</span> Lecture 6: Working Class Hero</a>
<ul>
<li><a href="#syntax-of-classes-and-instances"
id="toc-syntax-of-classes-and-instances"><span
class="toc-section-number">6.1</span> Syntax of Classes and
Instances</a></li>
<li><a href="#default-implementations"
id="toc-default-implementations"><span
class="toc-section-number">6.2</span> Default Implementations</a></li>
<li><a href="#useful-stuff" id="toc-useful-stuff"><span
class="toc-section-number">6.3</span> Useful Stuff</a></li>
<li><a href="#hierarchies" id="toc-hierarchies"><span
class="toc-section-number">6.4</span> Hierarchies</a></li>
<li><a href="#quiz-5" id="toc-quiz-5"><span
class="toc-section-number">6.5</span> Quiz</a></li>
<li><a href="#exercises-5" id="toc-exercises-5"><span
class="toc-section-number">6.6</span> Exercises</a></li>
</ul></li>
<li><a href="#lecture-7-new-constellations"
id="toc-lecture-7-new-constellations"><span
class="toc-section-number">7</span> Lecture 7: New Constellations</a>
<ul>
<li><a href="#modeling-with-boxes" id="toc-modeling-with-boxes"><span
class="toc-section-number">7.1</span> Modeling with Boxes</a></li>
<li><a href="#modeling-with-cases" id="toc-modeling-with-cases"><span
class="toc-section-number">7.2</span> Modeling with Cases</a></li>
<li><a href="#monoids" id="toc-monoids"><span
class="toc-section-number">7.3</span> Monoids</a></li>
<li><a href="#open-and-closed-abstractions"
id="toc-open-and-closed-abstractions"><span
class="toc-section-number">7.4</span> Open and Closed
Abstractions</a></li>
<li><a href="#modeling-with-languages"
id="toc-modeling-with-languages"><span
class="toc-section-number">7.5</span> Modeling with Languages</a></li>
<li><a href="#exercises-6" id="toc-exercises-6"><span
class="toc-section-number">7.6</span> Exercises</a></li>
</ul></li>
<li><a href="#lecture-8-the-aftertaste"
id="toc-lecture-8-the-aftertaste"><span
class="toc-section-number">8</span> Lecture 8: The Aftertaste</a>
<ul>
<li><a href="#a-taste-of-io" id="toc-a-taste-of-io"><span
class="toc-section-number">8.1</span> A Taste of IO</a></li>
<li><a href="#summary" id="toc-summary"><span
class="toc-section-number">8.2</span> Summary</a></li>
<li><a href="#what-next" id="toc-what-next"><span
class="toc-section-number">8.3</span> What Next?</a></li>
<li><a href="#final-project-graphics"
id="toc-final-project-graphics"><span
class="toc-section-number">8.4</span> Final Project: Graphics</a></li>
<li><a href="#acknowledgements" id="toc-acknowledgements"><span
class="toc-section-number">8.5</span> Acknowledgements</a></li>
</ul></li>
</ul>
</nav>
<div id="text-container">
<div id="text">
<!-- MENU -->
<header>
<h1 class="title">Haskell Mooc, part 1</h1>
</header>
<p>by Joel Kaasinen (<a href="https://nitor.com/en">Nitor</a>) and John
Lång (University of Helsinki)</p>
<h1 data-number="1" id="lecture-1-and-so-it-begins"><span
class="header-section-number">1</span> Lecture 1: …And so It Begins</h1>
<h2 data-number="1.1" id="about-the-course"><span
class="header-section-number">1.1</span> About the Course</h2>
<p>This is an online course on Functional Programming that uses the
Haskell programming language. You can study at your own pace. All the
material and exercises are openly available.</p>
<p>This course is aimed at beginners who wish to learn functional
programming, but also people who have experience with functional
programming and want to learn Haskell in particular. The course assumes
no previous knowledge, but knowing at least one programming language
beforehand will make the course easier.</p>
<p>Working on the exercises involves knowing how to use the command
line, and basic usage of the Git version control system.</p>
<p>This is part 1 of a two-part course. Part 1 covers the basics of
Haskell syntax and features. You will learn about recursion,
higher-order functions, algebraic data types and some of Haskell’s
advanced features. However, part 1 will stick to pure functional
programming, without side-effects. I/O and Monads will be introduced in
part 2.</p>
<p>The course is split into 8 lectures. They are roughly the same size,
but some lectures have more material than others. Each lecture set ends
with 10-30 small programming exercises on the topics of the lecture.</p>
<h2 data-number="1.2" id="read-these"><span
class="header-section-number">1.2</span> Read These</h2>
<p>In addition to this course material, the following sources might be
useful if you feel like you’re missing examples or explanations.</p>
<ul>
<li><a href="https://haskell.mooc.fi">The course pages</a></li>
<li>The course <a href="https://t.me/haskell_mooc_fi">channel on
Telegram</a></li>
<li>The course <a
href="https://github.com/moocfi/haskell-mooc">repository on Github</a>
contains the exercises and this material</li>
<li>Additional resources
<ul>
<li><a href="https://www.haskell.org/tutorial/">A Gentle Introduction to
Haskell</a> - an older and shorter tutorial, but still worth
reading</li>
<li><a href="http://learnyouahaskell.com/chapters">Learn You a Haskell
for Great Good!</a> – a nice free introduction to Haskell</li>
<li><a href="https://www.cs.yale.edu/homes/hudak/SOE/index.htm">The
Haskell School of Expression</a> - slightly older but still relevant
introduction to functional programming</li>
<li><a href="https://haskellbook.com/">Haskell Programming from First
Principles</a> - $59 e-book on Haskell, slow and long</li>
<li>The IRC channel <code>#haskell</code> on <a
href="https://libera.chat/">libera.chat</a> is a nice place for
beginners</li>
</ul></li>
</ul>
<h2 data-number="1.3" id="haskell"><span
class="header-section-number">1.3</span> Haskell</h2>
<p>Haskell is</p>
<p><strong>Functional</strong> – the basic building blocks of programs
are functions. Functions can return functions and take functions as
arguments. Also, the only looping construct in Haskell is recursion.</p>
<p><strong>Pure</strong> - Haskell functions are pure, that is, they
don’t have side effects. Side effects mean things like reading a file,
printing out text, or changing global variables. All inputs to a
function must be in its arguments, and all outputs from a function in
its return value. This sounds restricting, but makes reasoning about
programs easier, and allows for more optimizations by the compiler.</p>
<p><strong>Lazy</strong> - values are only evaluated when they are
needed. This makes it possible to work with infinite data structures,
and also makes pure programs more efficient.</p>
<p><strong>Strongly typed</strong> - every Haskell value and expression
has a type. The compiler checks the types at compile-time and guarantees
that no type errors can happen at runtime. This means no AttributeErrors
(a la Python), ClassCastExceptions (a la Java) or segmentation faults (a
la C). The Haskell type system is very powerful and can help you design
better programs.</p>
<p><strong>Type inferred</strong> - in addition to checking the types,
the compiler can deduce the types for most programs. This makes working
with a strongly typed language easier. Indeed, most Haskell functions
can be written completely without types. However programmers can still
give functions and values type annotations to make finding type errors
easier. Type annotations also make reading programs easier.</p>
<p><strong>Garbage-collected</strong> - like most high-level languages
these days, Haskell has automatic memory management via garbage
collection. This means that the programmer doesn’t need to worry about
allocating or freeing memory, the language runtime handles all of it
automatically.</p>
<p><strong>Compiled</strong> - even though we mostly use Haskell via the
interactive GHCi environment on this course, Haskell is a compiled
language. Haskell programs can be compiled to very efficient binaries,
and the GHC compiler is very good at optimising functional code into
performant machine code.</p>
<p>You’ll learn what these terms mean in practice during this course.
Don’t worry if some of them sound abstract right now.</p>
<p>See also: <a
href="https://wiki.haskell.org/Functional_programming">The Haskell Wiki
page on Functional programming</a>.</p>
<h3 data-number="1.3.1" id="features"><span
class="header-section-number">1.3.1</span> Features</h3>
<p>Here’s a showcase of some of the Haskell’s cool features:</p>
<p><strong>Higher-order functions</strong> – functions can take
functions as arguments:</p>
<div class="sourceCode" id="cb1"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb1-1"><a href="#cb1-1" aria-hidden="true" tabindex="-1"></a><span class="fu">map</span> <span class="fu">length</span> [<span class="st">"abc"</span>,<span class="st">"abcdef"</span>]</span></code></pre></div>
<p>This results in <code>[3,6]</code>.</p>
<p><strong>Anonymous functions aka lambdas</strong> – you can define
single-use helper functions without giving them a name</p>
<div class="sourceCode" id="cb2"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb2-1"><a href="#cb2-1" aria-hidden="true" tabindex="-1"></a><span class="fu">filter</span> (\x <span class="ot">-></span> <span class="fu">length</span> x <span class="op">></span> <span class="dv">1</span>) [<span class="st">"abc"</span>,<span class="st">"d"</span>,<span class="st">"ef"</span>]</span></code></pre></div>
<p>This results in <code>["abc","ef"]</code>.</p>
<p><strong>Partial application</strong> – you can define new functions
by giving another function only some of the arguments it needs. For
example this multiplies all elements in a list by 3:</p>
<div class="sourceCode" id="cb3"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb3-1"><a href="#cb3-1" aria-hidden="true" tabindex="-1"></a><span class="fu">map</span> (<span class="op">*</span><span class="dv">3</span>) [<span class="dv">1</span>,<span class="dv">2</span>,<span class="dv">3</span>]</span></code></pre></div>
<p><strong>Algebraic datatypes</strong> – a syntax for defining
datatypes that can contain a number of different cases:</p>
<div class="sourceCode" id="cb4"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb4-1"><a href="#cb4-1" aria-hidden="true" tabindex="-1"></a><span class="kw">data</span> <span class="dt">Shape</span> <span class="ot">=</span> <span class="dt">Point</span> <span class="op">|</span> <span class="dt">Rectangle</span> <span class="dt">Double</span> <span class="dt">Double</span> <span class="op">|</span> <span class="dt">Circle</span> <span class="dt">Double</span></span></code></pre></div>
<p>Now the type <code>Shape</code> can have values like
<code>Point</code>, <code>Rectangle 3 6</code> and
<code>Circle 5</code></p>
<p><strong>Pattern matching</strong> – defining functions based on cases
that correspond to your data definitions:</p>
<div class="sourceCode" id="cb5"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb5-1"><a href="#cb5-1" aria-hidden="true" tabindex="-1"></a>area <span class="dt">Point</span> <span class="ot">=</span> <span class="dv">0</span></span>
<span id="cb5-2"><a href="#cb5-2" aria-hidden="true" tabindex="-1"></a>area (<span class="dt">Rectangle</span> width height) <span class="ot">=</span> width <span class="op">*</span> height</span>
<span id="cb5-3"><a href="#cb5-3" aria-hidden="true" tabindex="-1"></a>area (<span class="dt">Circle</span> radius) <span class="ot">=</span> <span class="fu">pi</span> <span class="op">*</span> radius <span class="op">*</span> radius</span></code></pre></div>
<p><strong>Lists</strong> – Unlike many languages, Haskell has a concise
built-in syntax for lists. Lists can be built from other lists using
<em>list comprehensions</em>. Here’s a snippet that generates names of
even length from a set of options for first and last names:</p>
<div class="sourceCode" id="cb6"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb6-1"><a href="#cb6-1" aria-hidden="true" tabindex="-1"></a>[whole <span class="op">|</span> first <span class="ot"><-</span> [<span class="st">"Eva"</span>, <span class="st">"Mike"</span>],</span>
<span id="cb6-2"><a href="#cb6-2" aria-hidden="true" tabindex="-1"></a> <span class="fu">last</span> <span class="ot"><-</span> [<span class="st">"Smith"</span>, <span class="st">"Wood"</span>, <span class="st">"Odd"</span>],</span>
<span id="cb6-3"><a href="#cb6-3" aria-hidden="true" tabindex="-1"></a> <span class="kw">let</span> whole <span class="ot">=</span> first <span class="op">++</span> <span class="fu">last</span>,</span>
<span id="cb6-4"><a href="#cb6-4" aria-hidden="true" tabindex="-1"></a> <span class="fu">even</span> (<span class="fu">length</span> whole)]</span></code></pre></div>
<p>This results in <code>["EvaSmith","EvaOdd","MikeWood"]</code>. Thanks
to the laziness of Haskell, we can even create so-called <em>infinite
lists</em>:</p>
<div class="sourceCode" id="cb7"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb7-1"><a href="#cb7-1" aria-hidden="true" tabindex="-1"></a>primes <span class="ot">=</span> [ n <span class="op">|</span> n <span class="ot"><-</span> [<span class="dv">2</span><span class="op">..</span>] , <span class="fu">all</span> (\k <span class="ot">-></span> n <span class="ot">`mod`</span> k <span class="op">/=</span> <span class="dv">0</span>) [<span class="dv">2</span><span class="op">..</span>n <span class="ot">`div`</span> <span class="dv">2</span>] ]</span></code></pre></div>
<p>The first ten prime numbers can be then obtained by evaluating</p>
<div class="sourceCode" id="cb8"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb8-1"><a href="#cb8-1" aria-hidden="true" tabindex="-1"></a><span class="fu">take</span> <span class="dv">10</span> primes</span></code></pre></div>
<p>This evaluates to <code>[2,3,5,7,11,13,17,19,23,29]</code>.</p>
<p><strong>Parameterized types</strong> – you can define types that are
parameterized by other types. For example <code>[Int]</code> is a list
of <code>Int</code>s and <code>[Bool]</code> is a list of booleans. You
can define typed functions that work on all kinds of lists, for example
<code>reverse</code> has the type <code>[a] -> [a]</code> which means
it takes a list containing any type <code>a</code>, and returns a list
of the same type.</p>
<p><strong>Type classes</strong> – another form of polymorphism where
you can give a function a different implementation depending on the
arguments’ types. For example the <code>Show</code> type class defines
the function <code>show</code> that can convert values of various types
to strings. The <code>Num</code> type class defines arithmetic operators
like <code>+</code> that work on all number types (<code>Int</code>,
<code>Double</code>, <code>Complex</code>, …).</p>
<h3 data-number="1.3.2" id="some-history"><span
class="header-section-number">1.3.2</span> Some History</h3>
<p>A brief timeline of Haskell:</p>
<ul>
<li>1930s: Lambda Calculus</li>
<li>1950s-1970s: Lisp, Pattern Matching, Scheme, ML</li>
<li>1978 John Backus: <a
href="https://dl.acm.org/doi/pdf/10.1145/359576.359579">Can programming
be liberated from the von Neumann style?</a></li>
<li>1987 A decision was made to unify the field of pure functional
languages</li>
<li>1990 Haskell 1.0</li>
<li>1991 Haskell 1.1 (let-syntax, sections)</li>
<li>1992 Haskell 1.2, GHC</li>
<li>1996 Haskell 1.3 (Monads, do-syntax, type system improvements)</li>
<li>1999 Haskell 98</li>
<li>2000’s: GHC development, many extensions to the language</li>
<li>2009 <a href="https://www.haskell.org/onlinereport/haskell2010/">The
Haskell 2010 standard</a></li>
<li>2010’s: GHC development, Haskell Platform, Haskell Stack</li>
</ul>
<p>The word ‘haskel’ means wisdom in Hebrew, but the name of the Haskell
programming language comes from the logician Haskell Curry. The name
Haskell comes from the Old Norse words áss (god) and ketill
(helmet).</p>
<h3 data-number="1.3.3" id="uses-of-haskell"><span
class="header-section-number">1.3.3</span> Uses of Haskell</h3>
<p>Here are some examples of software projects that were written in
Haskell.</p>
<ul>
<li>The <a href="https://en.wikipedia.org/wiki/Darcs">Darcs</a>
distributed version control system</li>
<li>The <a
href="https://engineering.fb.com/security/fighting-spam-with-haskell/">Sigma
spam-prevention tool at Facebook</a></li>
<li>The implementations of the <a
href="https://www.purescript.org/">PureScript</a> and <a
href="https://elm-lang.org/">Elm</a> programming languages are written
in Haskell</li>
<li>The <a href="https://pandoc.org/">Pandoc</a> tool for converting
between different document formats – it’s also used to produce this
course material</li>
<li>The <a href="https://postgrest.org/">PostgREST</a> server that
exposes a HTTP REST API for a PostgreSQL database</li>
<li>Functional consulting companies like <a
href="https://galois.com/">Galois</a> and <a
href="https://well-typed.com/">Well-Typed</a> have a long history of
developing critical systems for clients in Haskell</li>
</ul>
<p>See <a href="https://wiki.haskell.org/Haskell_in_industry">The
Haskell Wiki</a> and <a
href="https://serokell.io/blog/top-software-written-in-haskell">this
blog post</a> for more!</p>
<h2 data-number="1.4" id="running-haskell"><span
class="header-section-number">1.4</span> Running Haskell</h2>
<p>The easiest way to get Haskell is to install the <code>stack</code>
tool, see <a href="https://haskellstack.org"
class="uri">https://haskellstack.org</a>. The exercises on this course
are intended to work with Stack, so you should use it for now.</p>
<p>By the way, if you’re interested in what Stack is, and how it relates
to other Haskell tools like Cabal and GHC, <a
href="https://www.quora.com/What-is-the-difference-between-Cabal-and-Stack-in-Haskell-projects-Which-one-do-you-recommend-and-why">read
more here</a> or <a
href="https://docs.haskellstack.org/en/stable/faq/">here</a>. We’ll get
back to Haskell packages and using them in detail in part 2 of the
course.</p>
<p>For now, after installing Stack, just run <code>stack ghci</code> to
get an interactive Haskell environment.</p>
<p><strong>Note!</strong> GHC 8.10.7 has a GHCi bug that makes editing
lines impossible on ARM-based systems. As a workaround, use
<code>TERM=dumb stack ghci</code>. More info <a
href="https://gitlab.haskell.org/ghc/ghc/-/issues/20022">here</a>.</p>
<h2 data-number="1.5" id="lets-start"><span
class="header-section-number">1.5</span> Let’s Start!</h2>
<p>GHCi is the interactive Haskell interpreter. Here’s an example
session:</p>
<pre><code>$ stack ghci
GHCi, version 9.2.8: https://www.haskell.org/ghc/ :? for help
Prelude> 1+1
2
Prelude> "asdf"
"asdf"
Prelude> reverse "asdf"
"fdsa"
Prelude> :type "asdf"
"asdf" :: [Char]
Prelude> tail "asdf"
"sdf"
Prelude> :type tail "asdf"
tail "asdf" :: [Char]
Prelude> :type tail
tail :: [a] -> [a]
Prelude> :quit
Leaving GHCi.</code></pre>
<p>By the way, the first time you run <code>stack ghci</code> it will
download GHC and some libraries, so don’t worry if you see some output
and have to wait for a while before getting the <code>Prelude></code>
prompt.</p>
<p>Let’s walk through this. Don’t worry if you don’t understand things
yet, this is just a first brush with expressions and types.</p>
<pre><code>Prelude> 1+1
2</code></pre>
<p>The <code>Prelude></code> is the GHCi prompt. It indicates we can
use the functions from the Haskell base library called Prelude. We
evaluate 1 plus 1, and the result is 2.</p>
<pre><code>Prelude> "asdf"
"asdf"</code></pre>
<p>Here we evaluate a string literal, and the result is the same
string.</p>
<pre><code>Prelude> reverse "asdf"
"fdsa"</code></pre>
<p>Here we compute the reverse of a string by applying the function
<code>reverse</code> to the value <code>"asdf"</code>.</p>
<pre><code>Prelude> :type "asdf"
"asdf" :: [Char]</code></pre>
<p>In addition to evaluating expressions we can also ask for their type
with the <code>:type</code> (abbreviated <code>:t</code>) GHCi command.
The type of <code>"asdf"</code> is a list of characters. Commands that
start with <code>:</code> are part of the user interface of GHCi, not
part of the Haskell language.</p>
<pre><code>Prelude> tail "asdf"
"sdf"
Prelude> :t tail "asdf"
tail "asdf" :: [Char]</code></pre>
<p>The <code>tail</code> function works on lists and returns all except
the first element of the list. Here we see <code>tail</code> applied to
<code>"asdf"</code>. We also check the type of the expression, and it is
a list of characters, as expected.</p>
<pre><code>Prelude> :t tail
tail :: [a] -> [a]</code></pre>
<p>Finally, here’s the type of the <code>tail</code> function. It takes
a list of any type as an argument, and returns a list of the same
type.</p>
<pre><code>Prelude> :quit
Leaving GHCi.</code></pre>
<p>That’s how you quit GHCi.</p>
<h2 data-number="1.6" id="expressions-and-types"><span
class="header-section-number">1.6</span> Expressions and Types</h2>
<p>Just like we saw in the GHCi example above, <em>expressions</em> and
<em>types</em> are the bread and butter of Haskell. In fact, almost
everything in a Haskell program is an expression. In particular, there
are no <em>statements</em> like in Python, Java or C.</p>
<p>An expression has a <em>value</em> and a <em>type</em>. We write an
expression and its type like this: <code>expression :: type</code>. Here
are some examples:</p>
<table>
<thead>
<tr class="header">
<th style="text-align: left;">Expression</th>
<th style="text-align: left;">Type</th>
<th style="text-align: left;">Value</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td style="text-align: left;"><code>True</code></td>
<td style="text-align: left;"><code>Bool</code></td>
<td style="text-align: left;"><code>True</code></td>
</tr>
<tr class="even">
<td style="text-align: left;"><code>not True</code></td>
<td style="text-align: left;"><code>Bool</code></td>
<td style="text-align: left;"><code>False</code></td>
</tr>
<tr class="odd">
<td style="text-align: left;"><code>"as" ++ "df"</code></td>
<td style="text-align: left;"><code>[Char]</code></td>
<td style="text-align: left;"><code>"asdf"</code></td>
</tr>
</tbody>
</table>
<h3 data-number="1.6.1" id="syntax-of-expressions"><span
class="header-section-number">1.6.1</span> Syntax of Expressions</h3>
<p>Expressions consist of functions <em>applied</em> to arguments.
Functions are <em>applied</em> (i.e. called) by placing the arguments
after the name of the function – there is no special syntax for a
function call.</p>
<table>
<thead>
<tr class="header">
<th style="text-align: left;">Haskell</th>
<th style="text-align: left;">Python, Java or C</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td style="text-align: left;"><code>f 1</code></td>
<td style="text-align: left;"><code>f(1)</code></td>
</tr>
<tr class="even">
<td style="text-align: left;"><code>f 1 2</code></td>
<td style="text-align: left;"><code>f(1,2)</code></td>
</tr>
</tbody>
</table>
<p>Parentheses can be used to <em>group</em> expressions (just like in
math and other languages).</p>
<table>
<thead>
<tr class="header">
<th style="text-align: left;">Haskell</th>
<th style="text-align: left;">Python, Java or C</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td style="text-align: left;"><code>g h f 1</code></td>
<td style="text-align: left;"><code>g(h,f,1)</code></td>
</tr>
<tr class="even">
<td style="text-align: left;"><code>g h (f 1)</code></td>
<td style="text-align: left;"><code>g(h,f(1))</code></td>
</tr>
<tr class="odd">
<td style="text-align: left;"><code>g (h f 1)</code></td>
<td style="text-align: left;"><code>g(h(f,1))</code></td>
</tr>
<tr class="even">
<td style="text-align: left;"><code>g (h (f 1))</code></td>
<td style="text-align: left;"><code>g(h(f(1)))</code></td>
</tr>
</tbody>
</table>
<p>Some function names are made special characters and they are used as
operators: between their arguments instead of before them. Function
calls <em>bind tighter</em> than operators, just like multiplication
binds tighter than addition.</p>
<table>
<thead>
<tr class="header">
<th style="text-align: left;">Haskell</th>
<th style="text-align: left;">Python, Java or C</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td style="text-align: left;"><code>a + b</code></td>
<td style="text-align: left;"><code>a + b</code></td>
</tr>
<tr class="even">
<td style="text-align: left;"><code>f a + g b</code></td>
<td style="text-align: left;"><code>f(a) + g(b)</code></td>
</tr>
<tr class="odd">
<td style="text-align: left;"><code>f (a + g b)</code></td>
<td style="text-align: left;"><code>f(a+g(b))</code></td>
</tr>
</tbody>
</table>
<p>PS. in Haskell, function application <em>associates left</em>, that
is, <code>f g x y</code> is actually the same as
<code>(((f g) x) y)</code>. We’ll get back to this topic later. For now
you can just think that <code>f g x y</code> is <code>f</code> applied
to the arguments <code>g</code>, <code>x</code> and <code>y</code>.</p>
<h3 data-number="1.6.2" id="syntax-of-types"><span
class="header-section-number">1.6.2</span> Syntax of Types</h3>
<p>Here are some basic types of Haskell to get you started.</p>
<table>
<thead>
<tr class="header">
<th style="text-align: left;">Type</th>
<th style="text-align: left;">Literals</th>
<th style="text-align: left;">Use</th>
<th style="text-align: left;">Operations</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td style="text-align: left;"><code>Int</code></td>
<td style="text-align: left;"><code>1</code>, <code>2</code>,
<code>-3</code></td>
<td style="text-align: left;">Number type (signed, 64bit)</td>
<td style="text-align: left;"><code>+</code>, <code>-</code>,
<code>*</code>, <code>div</code>, <code>mod</code></td>
</tr>
<tr class="even">
<td style="text-align: left;"><code>Integer</code></td>
<td style="text-align: left;"><code>1</code>, <code>-2</code>,
<code>900000000000000000</code></td>
<td style="text-align: left;">Unbounded number type</td>
<td style="text-align: left;"><code>+</code>, <code>-</code>,
<code>*</code>, <code>div</code>, <code>mod</code></td>
</tr>
<tr class="odd">
<td style="text-align: left;"><code>Double</code></td>
<td style="text-align: left;"><code>0.1</code>, <code>1.2e5</code></td>
<td style="text-align: left;">Floating point numbers</td>
<td style="text-align: left;"><code>+</code>, <code>-</code>,
<code>*</code>, <code>/</code>, <code>sqrt</code></td>
</tr>
<tr class="even">
<td style="text-align: left;"><code>Bool</code></td>
<td style="text-align: left;"><code>True</code>, <code>False</code></td>
<td style="text-align: left;">Truth values</td>
<td style="text-align: left;"><code>&&</code>, <code>||</code>,
<code>not</code></td>
</tr>
<tr class="odd">
<td style="text-align: left;"><code>String</code> aka
<code>[Char]</code></td>
<td style="text-align: left;"><code>"abcd"</code>, <code>""</code></td>
<td style="text-align: left;">Strings of characters</td>
<td style="text-align: left;"><code>reverse</code>, <code>++</code></td>
</tr>
</tbody>
</table>
<p>As you can see, the names of types in Haskell start with a capital
letter. Some values like <code>True</code> also start with a capital
letter, but variables and functions start with a lower case letter
(<code>reverse</code>, <code>not</code>, <code>x</code>). We’ll get back
to the meaning of capital letters in Lecture 2.</p>
<p>Function types are written using the <code>-></code> syntax:</p>
<ul>
<li>A function of one argument:
<code>argumentType -> returnType</code></li>
<li>… of two arguments:
<code>argument1Type -> argument2Type -> returnType</code></li>
<li>… of three arguments:
<code>argument1Type -> argument2Type -> argument3Type -> returnType</code></li>
</ul>
<p>Looks a bit weird, right? We’ll get back to this as well.</p>
<h3 data-number="1.6.3" id="note-about-misleading-types"><span
class="header-section-number">1.6.3</span> Note About Misleading
Types</h3>
<p>Sometimes, the types you see in GHCi are a bit different than what
you’d assume. Here are two common cases.</p>
<div class="sourceCode" id="cb17"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb17-1"><a href="#cb17-1" aria-hidden="true" tabindex="-1"></a><span class="dt">Prelude</span><span class="op">></span> <span class="op">:</span>t <span class="dv">1</span><span class="op">+</span><span class="dv">1</span></span>
<span id="cb17-2"><a href="#cb17-2" aria-hidden="true" tabindex="-1"></a><span class="dv">1</span><span class="op">+</span><span class="dv">1</span><span class="ot"> ::</span> <span class="dt">Num</span> a <span class="ot">=></span> a</span></code></pre></div>
<p>For now, you should read the type <code>Num a => a</code> as “any
number type”. In Haskell, number literals are <em>overloaded</em> which
means that they can be interpreted as any number type
(e.g. <code>Int</code> or <code>Double</code>). We’ll get back to what
<code>Num a</code> actually means when we talk about <em>type
classes</em> later.</p>
<div class="sourceCode" id="cb18"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb18-1"><a href="#cb18-1" aria-hidden="true" tabindex="-1"></a><span class="dt">Prelude</span><span class="op">></span> <span class="op">:</span>t <span class="st">"asdf"</span></span>
<span id="cb18-2"><a href="#cb18-2" aria-hidden="true" tabindex="-1"></a><span class="st">"asdf"</span><span class="ot"> ::</span> [<span class="dt">Char</span>]</span></code></pre></div>
<p>The type <code>String</code> is just an alias for the type
<code>[Char]</code> which means “list of characters”. We’ll get back to
lists on the next lecture! In any case, you can use <code>String</code>
and <code>[Char]</code> interchangeably, but GHCi will mostly use
<code>[Char]</code> when describing types to you.</p>
<h2 data-number="1.7" id="the-structure-of-a-haskell-program"><span
class="header-section-number">1.7</span> The Structure of a Haskell
Program</h2>
<p>Here’s a simple Haskell program that does some arithmetic and prints
some values.</p>
<div class="sourceCode" id="cb19"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb19-1"><a href="#cb19-1" aria-hidden="true" tabindex="-1"></a><span class="kw">module</span> <span class="dt">Gold</span> <span class="kw">where</span></span>
<span id="cb19-2"><a href="#cb19-2" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb19-3"><a href="#cb19-3" aria-hidden="true" tabindex="-1"></a><span class="co">-- The golden ratio</span></span>
<span id="cb19-4"><a href="#cb19-4" aria-hidden="true" tabindex="-1"></a><span class="ot">phi ::</span> <span class="dt">Double</span></span>
<span id="cb19-5"><a href="#cb19-5" aria-hidden="true" tabindex="-1"></a>phi <span class="ot">=</span> (<span class="fu">sqrt</span> <span class="dv">5</span> <span class="op">+</span> <span class="dv">1</span>) <span class="op">/</span> <span class="dv">2</span></span>
<span id="cb19-6"><a href="#cb19-6" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb19-7"><a href="#cb19-7" aria-hidden="true" tabindex="-1"></a><span class="ot">polynomial ::</span> <span class="dt">Double</span> <span class="ot">-></span> <span class="dt">Double</span></span>
<span id="cb19-8"><a href="#cb19-8" aria-hidden="true" tabindex="-1"></a>polynomial x <span class="ot">=</span> x<span class="op">^</span><span class="dv">2</span> <span class="op">-</span> x <span class="op">-</span> <span class="dv">1</span></span>
<span id="cb19-9"><a href="#cb19-9" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb19-10"><a href="#cb19-10" aria-hidden="true" tabindex="-1"></a>f x <span class="ot">=</span> polynomial (polynomial x)</span>
<span id="cb19-11"><a href="#cb19-11" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb19-12"><a href="#cb19-12" aria-hidden="true" tabindex="-1"></a>main <span class="ot">=</span> <span class="kw">do</span></span>
<span id="cb19-13"><a href="#cb19-13" aria-hidden="true" tabindex="-1"></a> <span class="fu">print</span> (polynomial phi)</span>
<span id="cb19-14"><a href="#cb19-14" aria-hidden="true" tabindex="-1"></a> <span class="fu">print</span> (f phi)</span></code></pre></div>
<p>If you put this in a file called <code>Gold.hs</code> and run it with
(for example) <code>stack runhaskell Gold.hs</code>, you should see this
output</p>
<pre><code>0.0
-1.0</code></pre>
<p>Let’s walk through the file.</p>
<div class="sourceCode" id="cb21"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb21-1"><a href="#cb21-1" aria-hidden="true" tabindex="-1"></a><span class="kw">module</span> <span class="dt">Gold</span> <span class="kw">where</span></span></code></pre></div>
<p>There is one Haskell <em>module</em> per source file. A module
consists of <em>definitions</em>.</p>
<div class="sourceCode" id="cb22"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb22-1"><a href="#cb22-1" aria-hidden="true" tabindex="-1"></a><span class="co">-- The golden ratio</span></span></code></pre></div>
<p>This is a comment. Comments are not part of the actual program, but
text for human readers of the program.</p>
<div class="sourceCode" id="cb23"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb23-1"><a href="#cb23-1" aria-hidden="true" tabindex="-1"></a><span class="ot">phi ::</span> <span class="dt">Double</span></span>
<span id="cb23-2"><a href="#cb23-2" aria-hidden="true" tabindex="-1"></a>phi <span class="ot">=</span> (<span class="fu">sqrt</span> <span class="dv">5</span> <span class="op">+</span> <span class="dv">1</span>) <span class="op">/</span> <span class="dv">2</span></span></code></pre></div>
<p>This is a definition of the constant <code>phi</code>, with an
accompanying <em>type annotation</em> (also known as a <em>type
signature</em>) <code>phi :: Double</code>. The type annotation means
that <code>phi</code> has type <code>Double</code>. The line with a
equals sign (<code>=</code>) is called an <em>equation</em>. The left
hand side of the <code>=</code> is the expression we are defining, and
the right hand side of the <code>=</code> is the definition.</p>
<p>In general a definition (of a function or constant) consists of an
optional <em>type annotation</em> and one or more <em>equations</em></p>
<div class="sourceCode" id="cb24"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb24-1"><a href="#cb24-1" aria-hidden="true" tabindex="-1"></a><span class="ot">polynomial ::</span> <span class="dt">Double</span> <span class="ot">-></span> <span class="dt">Double</span></span>
<span id="cb24-2"><a href="#cb24-2" aria-hidden="true" tabindex="-1"></a>polynomial x <span class="ot">=</span> x<span class="op">^</span><span class="dv">2</span> <span class="op">-</span> x <span class="op">-</span> <span class="dv">1</span></span></code></pre></div>
<p>This is the definition of a function called <code>polynomial</code>.
It has a type annotation and an equation. Note how an equation for a
function differs from the equation of a constant by the presence of a
parameter <code>x</code> left of the <code>=</code> sign. Note also that
<code>^</code> is the power operator in Haskell, not bitwise xor like in
many other languages.</p>
<div class="sourceCode" id="cb25"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb25-1"><a href="#cb25-1" aria-hidden="true" tabindex="-1"></a>f x <span class="ot">=</span> polynomial (polynomial x)</span></code></pre></div>
<p>This is the definition of a function called <code>f</code>. Note the
lack of type annotation. What is the type of <code>f</code>?</p>
<div class="sourceCode" id="cb26"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb26-1"><a href="#cb26-1" aria-hidden="true" tabindex="-1"></a>main <span class="ot">=</span> <span class="kw">do</span></span>
<span id="cb26-2"><a href="#cb26-2" aria-hidden="true" tabindex="-1"></a> <span class="fu">print</span> (polynomial phi)</span>
<span id="cb26-3"><a href="#cb26-3" aria-hidden="true" tabindex="-1"></a> <span class="fu">print</span> (f phi)</span></code></pre></div>
<p>This is a description of what happens when you run the program. It
uses do-syntax and the IO Monad. We’ll get back to those in part 2 of
the course.</p>
<h2 data-number="1.8" id="working-with-examples"><span
class="header-section-number">1.8</span> Working with Examples</h2>
<p>When you see an example definition like this</p>
<div class="sourceCode" id="cb27"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb27-1"><a href="#cb27-1" aria-hidden="true" tabindex="-1"></a><span class="ot">polynomial ::</span> <span class="dt">Double</span> <span class="ot">-></span> <span class="dt">Double</span></span>
<span id="cb27-2"><a href="#cb27-2" aria-hidden="true" tabindex="-1"></a>polynomial x <span class="ot">=</span> x<span class="op">^</span><span class="dv">2</span> <span class="op">-</span> x <span class="op">-</span> <span class="dv">1</span></span></code></pre></div>
<p>you should usually play around with it. Start by running it. There
are a couple of ways to do this.</p>
<p>If a definition fits on one line, you can just define it in GHCi:</p>
<pre><code>Prelude> polynomial x = x^2 - x - 1
Prelude> polynomial 3.0
5.0</code></pre>
<p>For a multi-line definition, you can either use <code>;</code> to
separate lines, or use the special <code>:{ :}</code> syntax to paste a
block of code into GHCi:</p>
<div class="sourceCode" id="cb29"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb29-1"><a href="#cb29-1" aria-hidden="true" tabindex="-1"></a><span class="dt">Prelude</span><span class="op">></span> <span class="op">:</span>{</span>
<span id="cb29-2"><a href="#cb29-2" aria-hidden="true" tabindex="-1"></a><span class="dt">Prelude</span><span class="op">|</span><span class="ot"> polynomial ::</span> <span class="dt">Double</span> <span class="ot">-></span> <span class="dt">Double</span></span>
<span id="cb29-3"><a href="#cb29-3" aria-hidden="true" tabindex="-1"></a><span class="dt">Prelude</span><span class="op">|</span> polynomial x <span class="ot">=</span> x<span class="op">^</span><span class="dv">2</span> <span class="op">-</span> x <span class="op">-</span> <span class="dv">1</span></span>
<span id="cb29-4"><a href="#cb29-4" aria-hidden="true" tabindex="-1"></a><span class="dt">Prelude</span><span class="op">|</span> <span class="op">:</span>}</span>
<span id="cb29-5"><a href="#cb29-5" aria-hidden="true" tabindex="-1"></a><span class="dt">Prelude</span><span class="op">></span> polynomial <span class="fl">3.0</span></span>
<span id="cb29-6"><a href="#cb29-6" aria-hidden="true" tabindex="-1"></a><span class="fl">5.0</span></span></code></pre></div>
<p>Finally, you can paste the code into a new or existing
<code>.hs</code> file, and then <code>:load</code> it into GHCi. If the
file has already been loaded, you can also use <code>:reload</code>.</p>
<div class="sourceCode" id="cb30"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb30-1"><a href="#cb30-1" aria-hidden="true" tabindex="-1"></a><span class="co">-- first copy and paste the definition into Example.hs, then run GHCi</span></span>
<span id="cb30-2"><a href="#cb30-2" aria-hidden="true" tabindex="-1"></a><span class="dt">Prelude</span><span class="op">></span> <span class="op">:</span>load Example.hs</span>
<span id="cb30-3"><a href="#cb30-3" aria-hidden="true" tabindex="-1"></a>[<span class="dv">1</span> <span class="kw">of</span> <span class="dv">1</span>] <span class="dt">Compiling</span> <span class="dt">Main</span> ( Example.hs, interpreted )</span>
<span id="cb30-4"><a href="#cb30-4" aria-hidden="true" tabindex="-1"></a><span class="dt">Ok</span>, one <span class="kw">module</span> loaded<span class="op">.</span></span>
<span id="cb30-5"><a href="#cb30-5" aria-hidden="true" tabindex="-1"></a><span class="op">*</span><span class="dt">Main</span><span class="op">></span> polynomial <span class="fl">3.0</span></span>
<span id="cb30-6"><a href="#cb30-6" aria-hidden="true" tabindex="-1"></a><span class="fl">5.0</span></span>
<span id="cb30-7"><a href="#cb30-7" aria-hidden="true" tabindex="-1"></a><span class="co">-- now you can edit the definition</span></span>
<span id="cb30-8"><a href="#cb30-8" aria-hidden="true" tabindex="-1"></a><span class="op">*</span><span class="dt">Main</span><span class="op">></span> <span class="op">:</span>reload</span>
<span id="cb30-9"><a href="#cb30-9" aria-hidden="true" tabindex="-1"></a>[<span class="dv">1</span> <span class="kw">of</span> <span class="dv">1</span>] <span class="dt">Compiling</span> <span class="dt">Main</span> ( Example.hs, interpreted )</span>
<span id="cb30-10"><a href="#cb30-10" aria-hidden="true" tabindex="-1"></a><span class="dt">Ok</span>, one <span class="kw">module</span> loaded<span class="op">.</span></span>
<span id="cb30-11"><a href="#cb30-11" aria-hidden="true" tabindex="-1"></a><span class="op">*</span><span class="dt">Main</span><span class="op">></span> polynomial <span class="dv">3</span></span>
<span id="cb30-12"><a href="#cb30-12" aria-hidden="true" tabindex="-1"></a><span class="fl">3.0</span></span></code></pre></div>
<p>After you’ve run the example, try modifying it, or making another
function that is similar but different. You learn programming by
programming, not by reading!</p>
<h3 data-number="1.8.1" id="dealing-with-errors"><span
class="header-section-number">1.8.1</span> Dealing with Errors</h3>
<p>Since Haskell is a typed language, you’ll pretty quickly bump into
type errors. Here’s an example of an error during a GHCi session:</p>
<div class="sourceCode" id="cb31"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb31-1"><a href="#cb31-1" aria-hidden="true" tabindex="-1"></a><span class="dt">Prelude</span><span class="op">></span> <span class="st">"string"</span> <span class="op">++</span> <span class="dt">True</span></span>
<span id="cb31-2"><a href="#cb31-2" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb31-3"><a href="#cb31-3" aria-hidden="true" tabindex="-1"></a><span class="op"><</span>interactive<span class="op">>:</span><span class="dv">1</span><span class="op">:</span><span class="dv">13</span><span class="op">:</span> <span class="fu">error</span><span class="op">:</span></span>
<span id="cb31-4"><a href="#cb31-4" aria-hidden="true" tabindex="-1"></a> • <span class="dt">Couldn't</span> match expected <span class="kw">type</span> ‘[<span class="dt">Char</span>]’ with actual <span class="kw">type</span> ‘<span class="dt">Bool</span>’</span>
<span id="cb31-5"><a href="#cb31-5" aria-hidden="true" tabindex="-1"></a> • <span class="dt">In</span> the second argument <span class="kw">of</span> ‘(<span class="op">++</span>)’, namely ‘<span class="dt">True</span>’</span>
<span id="cb31-6"><a href="#cb31-6" aria-hidden="true" tabindex="-1"></a> <span class="dt">In</span> the expression<span class="op">:</span> <span class="st">"string"</span> <span class="op">++</span> <span class="dt">True</span></span>
<span id="cb31-7"><a href="#cb31-7" aria-hidden="true" tabindex="-1"></a> <span class="dt">In</span> an equation for ‘it’<span class="op">:</span> it <span class="ot">=</span> <span class="st">"string"</span> <span class="op">++</span> <span class="dt">True</span></span></code></pre></div>
<p>This is the most common type error, “Couldn’t match expected type”.
Even though the error looks long and scary, it’s pretty simple if you
just read through it.</p>
<ul>
<li><p>The first line of the error message,
<code><interactive>:1:13: error:</code> tells us that the error
occurred in GHCi. If we had loaded a file, we might instead get
something like <code>Sandbox.hs:3:17: error:</code>, where
<code>Sandbox.hs</code> is the name of the file, <code>3</code> is the
line number and <code>17</code> is the number of a character in the
line.</p></li>
<li><p>The line
<code>• Couldn't match expected type ‘[Char]’ with actual type ‘Bool’</code>
tells us that the immediate cause for the error is that there was an
expression of type <code>Bool</code>, when GHCi was expecting to find an
expression of type <code>[Char]</code>“. The location of this error was
indicated in the first line of the error message. Note that the expected
type is not always right. Giving type annotations by hand can help
debugging typing errors.</p></li>
<li><p>The line
<code>• In the second argument of ‘(++)’, namely ‘True’</code> tells
that the expression that had the wrong type was the second argument of
the operator <code>(++)</code>. We’ll learn later why it’s surrounded by
parentheses.</p></li>
<li><p>The full expression with the error was
<code>"string" ++ True</code>. As mentioned above, <code>String</code>
is a type alias for <code>[Char]</code>, the type of character lists.
The first argument to <code>++</code> was a list of characters, and
since <code>++</code> can only combine two lists of the same type, the
second argument should’ve been of type <code>[Char]</code> too.</p></li>
<li><p>The line
<code>In an equation for ‘it’: it = "string" ++ True</code> says that
the expression occurred in the definition of the variable
<code>it</code>, which is a default variable name that GHCi uses for
standalone expressions. If we had a line
<code>x = "string" ++ True</code> in a file, or a declaration
<code>let x = "string" ++ True</code> in GHCi, GHCi would print
<code>In an equation for ‘x’: x = "string" ++ True</code>
instead.</p></li>
</ul>
<p>There are also others types of errors.</p>
<div class="sourceCode" id="cb32"><pre
class="sourceCode haskell"><code class="sourceCode haskell"><span id="cb32-1"><a href="#cb32-1" aria-hidden="true" tabindex="-1"></a><span class="dt">Prelude</span><span class="op">></span> <span class="dt">True</span> <span class="op">+</span> <span class="dv">1</span></span>
<span id="cb32-2"><a href="#cb32-2" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb32-3"><a href="#cb32-3" aria-hidden="true" tabindex="-1"></a><span class="op"><</span>interactive<span class="op">>:</span><span class="dv">6</span><span class="op">:</span><span class="dv">1</span><span class="op">:</span> <span class="fu">error</span><span class="op">:</span></span>
<span id="cb32-4"><a href="#cb32-4" aria-hidden="true" tabindex="-1"></a> • <span class="dt">No</span> <span class="kw">instance</span> for (<span class="dt">Num</span> <span class="dt">Bool</span>) arising from a use <span class="kw">of</span> ‘<span class="op">+</span>’</span>
<span id="cb32-5"><a href="#cb32-5" aria-hidden="true" tabindex="-1"></a> • <span class="dt">In</span> the expression<span class="op">:</span> <span class="dt">True</span> <span class="op">+</span> <span class="dv">1</span></span>