forked from moocfi/haskell-mooc
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpart1.html
3977 lines (3968 loc) · 553 KB
/
part1.html
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">
a.sourceLine { display: inline-block; line-height: 1.25; }
a.sourceLine { pointer-events: none; color: inherit; text-decoration: inherit; }
a.sourceLine:empty { height: 1.2em; position: absolute; }
.sourceCode { overflow: visible; }
code.sourceCode { white-space: pre; position: relative; }
div.sourceCode { margin: 1em 0; }
pre.sourceCode { margin: 0; }
@media screen {
div.sourceCode { overflow: auto; }
}
@media print {
code.sourceCode { white-space: pre-wrap; }
a.sourceLine { text-indent: -1em; padding-left: 1em; }
}
pre.numberSource a.sourceLine
{ position: relative; }
pre.numberSource a.sourceLine:empty
{ position: absolute; }
pre.numberSource a.sourceLine::before
{ content: attr(data-line-number);
position: absolute; left: -5em; text-align: right; vertical-align: baseline;
border: none; pointer-events: all;
-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 {
a.sourceLine::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 { } /* 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 { } /* 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"><span class="toc-section-number">1</span> Lecture 1: …And so It Begins</a><ul>
<li><a href="#about-the-course"><span class="toc-section-number">1.1</span> About the Course</a></li>
<li><a href="#read-these"><span class="toc-section-number">1.2</span> Read These</a></li>
<li><a href="#haskell"><span class="toc-section-number">1.3</span> Haskell</a></li>
<li><a href="#running-haskell"><span class="toc-section-number">1.4</span> Running Haskell</a></li>
<li><a href="#lets-start"><span class="toc-section-number">1.5</span> Let’s Start!</a></li>
<li><a href="#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"><span class="toc-section-number">1.7</span> The Structure of a Haskell Program</a></li>
<li><a href="#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"><span class="toc-section-number">1.9</span> How Do I Get Anything Done?</a></li>
<li><a href="#all-together-now"><span class="toc-section-number">1.10</span> All Together Now!</a></li>
<li><a href="#a-word-about-indentation"><span class="toc-section-number">1.11</span> A Word About Indentation</a></li>
<li><a href="#quiz"><span class="toc-section-number">1.12</span> Quiz</a></li>
<li><a href="#working-on-the-exercises"><span class="toc-section-number">1.13</span> Working on the Exercises</a></li>
<li><a href="#exercises"><span class="toc-section-number">1.14</span> Exercises</a></li>
</ul></li>
<li><a href="#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"><span class="toc-section-number">2.1</span> Recursion and Helper Functions</a></li>
<li><a href="#guards"><span class="toc-section-number">2.2</span> Guards</a></li>
<li><a href="#lists"><span class="toc-section-number">2.3</span> Lists</a></li>
<li><a href="#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"><span class="toc-section-number">2.5</span> A Word About Type Inference and Polymorphism</a></li>
<li><a href="#the-maybe-type"><span class="toc-section-number">2.6</span> The <code>Maybe</code> Type</a></li>
<li><a href="#sidenote-constructors"><span class="toc-section-number">2.7</span> Sidenote: Constructors</a></li>
<li><a href="#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"><span class="toc-section-number">2.9</span> The case-of Expression</a></li>
<li><a href="#recap-pattern-matching"><span class="toc-section-number">2.10</span> Recap: Pattern Matching</a></li>
<li><a href="#quiz-1"><span class="toc-section-number">2.11</span> Quiz</a></li>
<li><a href="#exercises-1"><span class="toc-section-number">2.12</span> Exercises</a></li>
</ul></li>
<li><a href="#lecture-3-catamorphic"><span class="toc-section-number">3</span> Lecture 3: Catamorphic</a><ul>
<li><a href="#functional-programming-at-last"><span class="toc-section-number">3.1</span> Functional Programming, at Last</a></li>
<li><a href="#partial-application"><span class="toc-section-number">3.2</span> Partial Application</a></li>
<li><a href="#prefix-and-infix-notations"><span class="toc-section-number">3.3</span> Prefix and Infix Notations</a></li>
<li><a href="#lambdas"><span class="toc-section-number">3.4</span> Lambdas</a></li>
<li><a href="#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"><span class="toc-section-number">3.6</span> Example: Rewriting <code>whatFollows</code></a></li>
<li><a href="#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"><span class="toc-section-number">3.8</span> Lists and Recursion</a></li>
<li><a href="#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"><span class="toc-section-number">3.10</span> Something Fun: Custom Operators</a></li>
<li><a href="#quiz-2"><span class="toc-section-number">3.11</span> Quiz</a></li>
<li><a href="#exercises-2"><span class="toc-section-number">3.12</span> Exercises</a></li>
</ul></li>
<li><a href="#lecture-4-real-classy"><span class="toc-section-number">4</span> Lecture 4: Real Classy</a><ul>
<li><a href="#sidenote-tuples"><span class="toc-section-number">4.1</span> Sidenote: Tuples</a></li>
<li><a href="#interlude-folding"><span class="toc-section-number">4.2</span> Interlude: Folding</a></li>
<li><a href="#type-classes"><span class="toc-section-number">4.3</span> Type Classes</a></li>
<li><a href="#type-constraints"><span class="toc-section-number">4.4</span> Type Constraints</a></li>
<li><a href="#standard-type-classes"><span class="toc-section-number">4.5</span> Standard Type Classes</a></li>
<li><a href="#more-data-structures"><span class="toc-section-number">4.6</span> More Data Structures</a></li>
<li><a href="#reading-docs"><span class="toc-section-number">4.7</span> Reading Docs</a></li>
<li><a href="#quiz-3"><span class="toc-section-number">4.8</span> Quiz</a></li>
<li><a href="#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"><span class="toc-section-number">5</span> Lecture 5: You Need String for a Knot</a><ul>
<li><a href="#algebraic-datatypes"><span class="toc-section-number">5.1</span> Algebraic Datatypes</a></li>
<li><a href="#type-parameters"><span class="toc-section-number">5.2</span> Type Parameters</a></li>
<li><a href="#recursive-types"><span class="toc-section-number">5.3</span> Recursive Types</a></li>
<li><a href="#record-syntax"><span class="toc-section-number">5.4</span> Record Syntax</a></li>
<li><a href="#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"><span class="toc-section-number">5.6</span> Sidenote: Other Ways of Defining Types</a></li>
<li><a href="#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"><span class="toc-section-number">5.8</span> Quiz</a></li>
<li><a href="#exercises-4"><span class="toc-section-number">5.9</span> Exercises</a></li>
</ul></li>
<li><a href="#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"><span class="toc-section-number">6.1</span> Syntax of Classes and Instances</a></li>
<li><a href="#sidenote-restrictions-on-instances"><span class="toc-section-number">6.2</span> Sidenote: Restrictions on Instances</a></li>
<li><a href="#default-implementations"><span class="toc-section-number">6.3</span> Default Implementations</a></li>
<li><a href="#useful-stuff"><span class="toc-section-number">6.4</span> Useful Stuff</a></li>
<li><a href="#hierarchies"><span class="toc-section-number">6.5</span> Hierarchies</a></li>
<li><a href="#quiz-5"><span class="toc-section-number">6.6</span> Quiz</a></li>
<li><a href="#exercises-5"><span class="toc-section-number">6.7</span> Exercises</a></li>
</ul></li>
<li><a href="#lecture-7-new-constellations"><span class="toc-section-number">7</span> Lecture 7: New Constellations</a><ul>
<li><a href="#modeling-with-boxes"><span class="toc-section-number">7.1</span> Modeling with Boxes</a></li>
<li><a href="#modeling-with-cases"><span class="toc-section-number">7.2</span> Modeling with Cases</a></li>
<li><a href="#monoids"><span class="toc-section-number">7.3</span> Monoids</a></li>
<li><a href="#open-and-closed-abstractions"><span class="toc-section-number">7.4</span> Open and Closed Abstractions</a></li>
<li><a href="#modeling-with-languages"><span class="toc-section-number">7.5</span> Modeling with Languages</a></li>
<li><a href="#exercises-6"><span class="toc-section-number">7.6</span> Exercises</a></li>
</ul></li>
<li><a href="#lecture-8-the-aftertaste"><span class="toc-section-number">8</span> Lecture 8: The Aftertaste</a><ul>
<li><a href="#a-taste-of-io"><span class="toc-section-number">8.1</span> A Taste of IO</a></li>
<li><a href="#summary"><span class="toc-section-number">8.2</span> Summary</a></li>
<li><a href="#what-next"><span class="toc-section-number">8.3</span> What Next?</a></li>
<li><a href="#final-project-graphics"><span class="toc-section-number">8.4</span> Final Project: Graphics</a></li>
<li><a href="#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 id="lecture-1-and-so-it-begins"><span class="header-section-number">1</span> Lecture 1: …And so It Begins</h1>
<h2 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>
<h3 id="course-structure"><span class="header-section-number">1.1.1</span> Course Structure</h3>
<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>
<h3 id="administrative-information-grading"><span class="header-section-number">1.1.2</span> Administrative Information, Grading</h3>
<p>The course is worth 5 ECTS credits.</p>
<p>Grading is Fail/Pass/5. To pass the course you must complete at least 50% of each lecture’s exercises. A special grade of 5 is awarded to those who complete 99% of all exercises.</p>
<h2 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://freenode.net/">freenode</a> is a nice place for beginners</li>
</ul></li>
</ul>
<h2 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 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"><a class="sourceLine" id="cb1-1" data-line-number="1">map length [<span class="st">"abc"</span>,<span class="st">"abcdef"</span>]</a></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"><a class="sourceLine" id="cb2-1" data-line-number="1">filter (\x <span class="ot">-></span> length x <span class="fu">></span> <span class="dv">1</span>) [<span class="st">"abc"</span>,<span class="st">"d"</span>,<span class="st">"ef"</span>]</a></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"><a class="sourceLine" id="cb3-1" data-line-number="1">map (<span class="fu">*</span><span class="dv">3</span>) [<span class="dv">1</span>,<span class="dv">2</span>,<span class="dv">3</span>]</a></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"><a class="sourceLine" id="cb4-1" data-line-number="1"><span class="kw">data</span> <span class="dt">Shape</span> <span class="fu">=</span> <span class="dt">Point</span> <span class="fu">|</span> <span class="dt">Rectangle</span> <span class="dt">Double</span> <span class="dt">Double</span> <span class="fu">|</span> <span class="dt">Circle</span> <span class="dt">Double</span></a></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"><a class="sourceLine" id="cb5-1" data-line-number="1">area <span class="dt">Point</span> <span class="fu">=</span> <span class="dv">0</span></a>
<a class="sourceLine" id="cb5-2" data-line-number="2">area (<span class="dt">Rectangle</span> width height) <span class="fu">=</span> width <span class="fu">*</span> height</a>
<a class="sourceLine" id="cb5-3" data-line-number="3">area (<span class="dt">Circle</span> radius) <span class="fu">=</span> <span class="dv">2</span> <span class="fu">*</span> pi <span class="fu">*</span> radius</a></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"><a class="sourceLine" id="cb6-1" data-line-number="1">[whole <span class="fu">|</span> first <span class="ot"><-</span> [<span class="st">"Eva"</span>, <span class="st">"Mike"</span>],</a>
<a class="sourceLine" id="cb6-2" data-line-number="2"> last <span class="ot"><-</span> [<span class="st">"Smith"</span>, <span class="st">"Wood"</span>, <span class="st">"Odd"</span>],</a>
<a class="sourceLine" id="cb6-3" data-line-number="3"> <span class="kw">let</span> whole <span class="fu">=</span> first <span class="fu">++</span> last,</a>
<a class="sourceLine" id="cb6-4" data-line-number="4"> even (length whole)]</a></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"><a class="sourceLine" id="cb7-1" data-line-number="1">primes <span class="fu">=</span> [ n <span class="fu">|</span> n <span class="ot"><-</span> [<span class="dv">2</span><span class="fu">..</span>] , all (\k <span class="ot">-></span> n <span class="ot">`mod`</span> k <span class="fu">/=</span> <span class="dv">0</span>) [<span class="dv">2</span><span class="fu">..</span>n <span class="ot">`div`</span> <span class="dv">2</span>] ]</a></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"><a class="sourceLine" id="cb8-1" data-line-number="1">take <span class="dv">10</span> primes</a></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 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://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf">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 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 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>
<h2 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 8.0.1: http://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 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 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 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 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"><a class="sourceLine" id="cb17-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> <span class="fu">:</span>t <span class="dv">1</span><span class="fu">+</span><span class="dv">1</span></a>
<a class="sourceLine" id="cb17-2" data-line-number="2"><span class="dv">1</span><span class="fu">+</span><span class="dv">1</span><span class="ot"> ::</span> <span class="dt">Num</span> a <span class="ot">=></span> a</a></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"><a class="sourceLine" id="cb18-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> <span class="fu">:</span>t <span class="st">"asdf"</span></a>
<a class="sourceLine" id="cb18-2" data-line-number="2"><span class="st">"asdf"</span><span class="ot"> ::</span> [<span class="dt">Char</span>]</a></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 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"><a class="sourceLine" id="cb19-1" data-line-number="1"><span class="kw">module</span> <span class="dt">Gold</span> <span class="kw">where</span></a>
<a class="sourceLine" id="cb19-2" data-line-number="2"></a>
<a class="sourceLine" id="cb19-3" data-line-number="3"><span class="co">-- The golden ratio</span></a>
<a class="sourceLine" id="cb19-4" data-line-number="4"><span class="ot">phi ::</span> <span class="dt">Double</span></a>
<a class="sourceLine" id="cb19-5" data-line-number="5">phi <span class="fu">=</span> (sqrt <span class="dv">5</span> <span class="fu">+</span> <span class="dv">1</span>) <span class="fu">/</span> <span class="dv">2</span></a>
<a class="sourceLine" id="cb19-6" data-line-number="6"></a>
<a class="sourceLine" id="cb19-7" data-line-number="7"><span class="ot">polynomial ::</span> <span class="dt">Double</span> <span class="ot">-></span> <span class="dt">Double</span></a>
<a class="sourceLine" id="cb19-8" data-line-number="8">polynomial x <span class="fu">=</span> x<span class="fu">^</span><span class="dv">2</span> <span class="fu">-</span> x <span class="fu">-</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb19-9" data-line-number="9"></a>
<a class="sourceLine" id="cb19-10" data-line-number="10">f x <span class="fu">=</span> polynomial (polynomial x)</a>
<a class="sourceLine" id="cb19-11" data-line-number="11"></a>
<a class="sourceLine" id="cb19-12" data-line-number="12">main <span class="fu">=</span> <span class="kw">do</span></a>
<a class="sourceLine" id="cb19-13" data-line-number="13"> print (polynomial phi)</a>
<a class="sourceLine" id="cb19-14" data-line-number="14"> print (f phi)</a></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"><a class="sourceLine" id="cb21-1" data-line-number="1"><span class="kw">module</span> <span class="dt">Gold</span> <span class="kw">where</span></a></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"><a class="sourceLine" id="cb22-1" data-line-number="1"><span class="co">-- The golden ratio</span></a></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"><a class="sourceLine" id="cb23-1" data-line-number="1"><span class="ot">phi ::</span> <span class="dt">Double</span></a>
<a class="sourceLine" id="cb23-2" data-line-number="2">phi <span class="fu">=</span> (sqrt <span class="dv">5</span> <span class="fu">+</span> <span class="dv">1</span>) <span class="fu">/</span> <span class="dv">2</span></a></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"><a class="sourceLine" id="cb24-1" data-line-number="1"><span class="ot">polynomial ::</span> <span class="dt">Double</span> <span class="ot">-></span> <span class="dt">Double</span></a>
<a class="sourceLine" id="cb24-2" data-line-number="2">polynomial x <span class="fu">=</span> x<span class="fu">^</span><span class="dv">2</span> <span class="fu">-</span> x <span class="fu">-</span> <span class="dv">1</span></a></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"><a class="sourceLine" id="cb25-1" data-line-number="1">f x <span class="fu">=</span> polynomial (polynomial x)</a></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"><a class="sourceLine" id="cb26-1" data-line-number="1">main <span class="fu">=</span> <span class="kw">do</span></a>
<a class="sourceLine" id="cb26-2" data-line-number="2"> print (polynomial phi)</a>
<a class="sourceLine" id="cb26-3" data-line-number="3"> print (f phi)</a></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 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"><a class="sourceLine" id="cb27-1" data-line-number="1"><span class="ot">polynomial ::</span> <span class="dt">Double</span> <span class="ot">-></span> <span class="dt">Double</span></a>
<a class="sourceLine" id="cb27-2" data-line-number="2">polynomial x <span class="fu">=</span> x<span class="fu">^</span><span class="dv">2</span> <span class="fu">-</span> x <span class="fu">-</span> <span class="dv">1</span></a></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 using <code>let</code>:</p>
<pre><code>Prelude> let 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"><a class="sourceLine" id="cb29-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> <span class="fu">:</span>{</a>
<a class="sourceLine" id="cb29-2" data-line-number="2"><span class="dt">Prelude</span><span class="fu">|</span><span class="ot"> polynomial ::</span> <span class="dt">Double</span> <span class="ot">-></span> <span class="dt">Double</span></a>
<a class="sourceLine" id="cb29-3" data-line-number="3"><span class="dt">Prelude</span><span class="fu">|</span> polynomial x <span class="fu">=</span> x<span class="fu">^</span><span class="dv">2</span> <span class="fu">-</span> x <span class="fu">-</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb29-4" data-line-number="4"><span class="dt">Prelude</span><span class="fu">|</span> <span class="fu">:</span>}</a>
<a class="sourceLine" id="cb29-5" data-line-number="5"><span class="dt">Prelude</span><span class="fu">></span> polynomial <span class="fl">3.0</span></a>
<a class="sourceLine" id="cb29-6" data-line-number="6"><span class="fl">5.0</span></a></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"><a class="sourceLine" id="cb30-1" data-line-number="1"><span class="co">-- first copy and paste the definition into Example.hs, then run GHCi</span></a>
<a class="sourceLine" id="cb30-2" data-line-number="2"><span class="dt">Prelude</span><span class="fu">></span> <span class="fu">:</span>load Example.hs</a>
<a class="sourceLine" id="cb30-3" data-line-number="3">[<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 )</a>
<a class="sourceLine" id="cb30-4" data-line-number="4"><span class="dt">Ok</span>, one <span class="kw">module</span> loaded<span class="fu">.</span></a>
<a class="sourceLine" id="cb30-5" data-line-number="5"><span class="fu">*</span><span class="dt">Main</span><span class="fu">></span> polynomial <span class="fl">3.0</span></a>
<a class="sourceLine" id="cb30-6" data-line-number="6"><span class="fl">5.0</span></a>
<a class="sourceLine" id="cb30-7" data-line-number="7"><span class="co">-- now you can edit the definition</span></a>
<a class="sourceLine" id="cb30-8" data-line-number="8"><span class="fu">*</span><span class="dt">Main</span><span class="fu">></span> <span class="fu">:</span>reload</a>
<a class="sourceLine" id="cb30-9" data-line-number="9">[<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 )</a>
<a class="sourceLine" id="cb30-10" data-line-number="10"><span class="dt">Ok</span>, one <span class="kw">module</span> loaded<span class="fu">.</span></a>
<a class="sourceLine" id="cb30-11" data-line-number="11"><span class="fu">*</span><span class="dt">Main</span><span class="fu">></span> polynomial <span class="dv">3</span></a>
<a class="sourceLine" id="cb30-12" data-line-number="12"><span class="fl">3.0</span></a></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 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"><a class="sourceLine" id="cb31-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> <span class="st">"string"</span> <span class="fu">++</span> <span class="dt">True</span></a>
<a class="sourceLine" id="cb31-2" data-line-number="2"></a>
<a class="sourceLine" id="cb31-3" data-line-number="3"><span class="fu"><</span>interactive<span class="fu">>:</span><span class="dv">1</span><span class="fu">:</span><span class="dv">13</span><span class="fu">:</span> error<span class="fu">:</span></a>
<a class="sourceLine" id="cb31-4" data-line-number="4"> • <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>’</a>
<a class="sourceLine" id="cb31-5" data-line-number="5"> • <span class="dt">In</span> the second argument <span class="kw">of</span> ‘(<span class="fu">++</span>)’, namely ‘<span class="dt">True</span>’</a>
<a class="sourceLine" id="cb31-6" data-line-number="6"> <span class="dt">In</span> the expression<span class="fu">:</span> <span class="st">"string"</span> <span class="fu">++</span> <span class="dt">True</span></a>
<a class="sourceLine" id="cb31-7" data-line-number="7"> <span class="dt">In</span> an equation for ‘it’<span class="fu">:</span> it <span class="fu">=</span> <span class="st">"string"</span> <span class="fu">++</span> <span class="dt">True</span></a></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"><a class="sourceLine" id="cb32-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> <span class="dt">True</span> <span class="fu">+</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb32-2" data-line-number="2"></a>
<a class="sourceLine" id="cb32-3" data-line-number="3"><span class="fu"><</span>interactive<span class="fu">>:</span><span class="dv">6</span><span class="fu">:</span><span class="dv">1</span><span class="fu">:</span> error<span class="fu">:</span></a>
<a class="sourceLine" id="cb32-4" data-line-number="4"> • <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="fu">+</span>’</a>
<a class="sourceLine" id="cb32-5" data-line-number="5"> • <span class="dt">In</span> the expression<span class="fu">:</span> <span class="dt">True</span> <span class="fu">+</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb32-6" data-line-number="6"> <span class="dt">In</span> an equation for ‘it’<span class="fu">:</span> it <span class="fu">=</span> <span class="dt">True</span> <span class="fu">+</span> <span class="dv">1</span></a></code></pre></div>
<p>This is the kind of error you get when you try to use a numeric function like <code>+</code> on something that’s not a number.</p>
<p>The hardest error to track down is usually this:</p>
<div class="sourceCode" id="cb33"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb33-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> <span class="dt">True</span> <span class="fu">+</span></a>
<a class="sourceLine" id="cb33-2" data-line-number="2"></a>
<a class="sourceLine" id="cb33-3" data-line-number="3"><span class="fu"><</span>interactive<span class="fu">>:</span><span class="dv">10</span><span class="fu">:</span><span class="dv">7</span><span class="fu">:</span> error<span class="fu">:</span></a>
<a class="sourceLine" id="cb33-4" data-line-number="4"> parse error (possibly incorrect indentation or mismatched brackets)</a></code></pre></div>
<p>There are many ways to cause it. Probably you’re missing some characters somewhere. We’ll get back to indentation later in this lecture.</p>
<!-- TODO more errors based on feedback -->
<h3 id="arithmetic"><span class="header-section-number">1.8.2</span> Arithmetic</h3>
<p>There’s one thing in Haskell arithmetic that often trips up beginners, and that’s division.</p>
<p>In Haskell there are two division functions, the <code>/</code> operator and the <code>div</code> function. The <code>div</code> function does integer division:</p>
<div class="sourceCode" id="cb34"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb34-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> <span class="dv">7</span> <span class="ot">`div`</span> <span class="dv">2</span></a>
<a class="sourceLine" id="cb34-2" data-line-number="2"><span class="dv">3</span></a></code></pre></div>
<p>The <code>/</code> operator performs the usual division:</p>
<div class="sourceCode" id="cb35"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb35-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> <span class="fl">7.0</span> <span class="fu">/</span> <span class="fl">2.0</span></a>
<a class="sourceLine" id="cb35-2" data-line-number="2"><span class="fl">3.5</span></a></code></pre></div>
<p>However, you can only use <code>div</code> on whole number types like <code>Int</code> and <code>Integer</code>, and you can only use <code>/</code> on decimal types like <code>Double</code>. Here’s an example of what happens if you try to mix them up:</p>
<div class="sourceCode" id="cb36"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb36-1" data-line-number="1"><span class="ot">halve ::</span> <span class="dt">Int</span> <span class="ot">-></span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb36-2" data-line-number="2">halve x <span class="fu">=</span> x <span class="fu">/</span> <span class="dv">2</span></a></code></pre></div>
<pre><code>error:
• No instance for (Fractional Int) arising from a use of ‘/’
• In the expression: x / 2
In an equation for ‘halve’: halve x = x / 2</code></pre>
<p>Just try to keep this in mind for now. We’ll get back to the difference between <code>/</code> and <code>div</code>, and what <code>Num</code> and <code>Fractional</code> mean when talking about type classes.</p>
<h2 id="how-do-i-get-anything-done"><span class="header-section-number">1.9</span> How Do I Get Anything Done?</h2>
<p>So far you’ve seen some arithmetic, reversing a string and so on. How does one write actual programs in Haskell? Many of the usual programming constructs like loops, statements and assignment are missing from Haskell. Next, we’ll go through the basic building blocks of Haskell programs:</p>
<ul>
<li>Conditionals</li>
<li>Local definitions</li>
<li>Pattern matching</li>
<li>Recursion</li>
</ul>
<h3 id="conditionals"><span class="header-section-number">1.9.1</span> Conditionals</h3>
<p>In other languages, <code>if</code> is a <em>statement</em>. It doesn’t have a value, it just conditionally executes other statements.</p>
<p>In Haskell, <code>if</code> is an <em>expression</em>. It has a value. It selects between two other expressions. It corresponds to the <code>?:</code> operator in C or Java.</p>
<div class="sourceCode" id="cb38"><pre class="sourceCode java"><code class="sourceCode java"><a class="sourceLine" id="cb38-1" data-line-number="1"><span class="co">// Java</span></a>
<a class="sourceLine" id="cb38-2" data-line-number="2"><span class="dt">int</span> price = product.<span class="fu">equals</span>(<span class="st">"milk"</span>) ? <span class="dv">1</span> : <span class="dv">2</span>;</a></code></pre></div>
<p>Python’s conditional expressions are quite close to haskell’s <code>if</code>:</p>
<div class="sourceCode" id="cb39"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb39-1" data-line-number="1"><span class="co"># Python</span></a>
<a class="sourceLine" id="cb39-2" data-line-number="2">price <span class="op">=</span> <span class="dv">1</span> <span class="cf">if</span> product <span class="op">==</span> <span class="st">"milk"</span> <span class="cf">else</span> <span class="dv">2</span></a></code></pre></div>
<p>This is how the same example looks in Haskell:</p>
<div class="sourceCode" id="cb40"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb40-1" data-line-number="1">price <span class="fu">=</span> <span class="kw">if</span> product <span class="fu">==</span> <span class="st">"milk"</span> <span class="kw">then</span> <span class="dv">1</span> <span class="kw">else</span> <span class="dv">2</span></a></code></pre></div>
<p>Because Haskell’s <code>if</code> <em>returns</em> a value, you <strong>always</strong> need an <code>else</code>!</p>
<h4 id="functions-returning-bool"><span class="header-section-number">1.9.1.1</span> Functions Returning <code>Bool</code></h4>
<p>In order to write if expressions, you need to know how to get values of type <code>Bool</code>. The most common way is comparisons. The usual <code>==</code>, <code><</code>, <code><=</code>, <code>></code> and <code>>=</code> operators work in Haskell. You can do ordered comparisons (<code><</code>, <code>></code>) on all sorts of numbers, and equality comparisons (<code>==</code>) on almost anything:</p>
<div class="sourceCode" id="cb41"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb41-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> <span class="st">"foo"</span> <span class="fu">==</span> <span class="st">"bar"</span></a>
<a class="sourceLine" id="cb41-2" data-line-number="2"><span class="dt">False</span></a>
<a class="sourceLine" id="cb41-3" data-line-number="3"><span class="dt">Prelude</span><span class="fu">></span> <span class="fl">5.0</span> <span class="fu"><=</span> <span class="fl">7.2</span></a>
<a class="sourceLine" id="cb41-4" data-line-number="4"><span class="dt">True</span></a>
<a class="sourceLine" id="cb41-5" data-line-number="5"><span class="dt">Prelude</span><span class="fu">></span> <span class="dv">1</span> <span class="fu">==</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb41-6" data-line-number="6"><span class="dt">True</span></a></code></pre></div>
<p>One oddity of Haskell is that the not-equals operator is written <code>/=</code> instead of the usual <code>!=</code>:</p>
<div class="sourceCode" id="cb42"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb42-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> <span class="dv">2</span> <span class="fu">/=</span> <span class="dv">3</span></a>
<a class="sourceLine" id="cb42-2" data-line-number="2"><span class="dt">True</span></a>
<a class="sourceLine" id="cb42-3" data-line-number="3"><span class="dt">Prelude</span><span class="fu">></span> <span class="st">"bike"</span> <span class="fu">/=</span> <span class="st">"bike"</span></a>
<a class="sourceLine" id="cb42-4" data-line-number="4"><span class="dt">False</span></a></code></pre></div>
<p>Remember that in addition to these comparisons, you can get <code>Bool</code> values out of other <code>Bool</code> values by using the <code>&&</code> (“and”) and <code>||</code> (“or”) operators, and the <code>not</code> function.</p>
<h4 id="examples"><span class="header-section-number">1.9.1.2</span> Examples</h4>
<div class="sourceCode" id="cb43"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb43-1" data-line-number="1">checkPassword password <span class="fu">=</span> <span class="kw">if</span> password <span class="fu">==</span> <span class="st">"swordfish"</span></a>
<a class="sourceLine" id="cb43-2" data-line-number="2"> <span class="kw">then</span> <span class="st">"You're in."</span></a>
<a class="sourceLine" id="cb43-3" data-line-number="3"> <span class="kw">else</span> <span class="st">"ACCESS DENIED!"</span></a></code></pre></div>
<div class="sourceCode" id="cb44"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb44-1" data-line-number="1">absoluteValue n <span class="fu">=</span> <span class="kw">if</span> n <span class="fu"><</span> <span class="dv">0</span> <span class="kw">then</span> <span class="fu">-</span>n <span class="kw">else</span> n</a></code></pre></div>
<div class="sourceCode" id="cb45"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb45-1" data-line-number="1">login user password <span class="fu">=</span> <span class="kw">if</span> user <span class="fu">==</span> <span class="st">"unicorn73"</span></a>
<a class="sourceLine" id="cb45-2" data-line-number="2"> <span class="kw">then</span> <span class="kw">if</span> password <span class="fu">==</span> <span class="st">"f4bulous!"</span></a>
<a class="sourceLine" id="cb45-3" data-line-number="3"> <span class="kw">then</span> <span class="st">"unicorn73 logged in"</span></a>
<a class="sourceLine" id="cb45-4" data-line-number="4"> <span class="kw">else</span> <span class="st">"wrong password"</span></a>
<a class="sourceLine" id="cb45-5" data-line-number="5"> <span class="kw">else</span> <span class="st">"unknown user"</span></a></code></pre></div>
<h3 id="local-definitions"><span class="header-section-number">1.9.2</span> Local Definitions</h3>
<p>Haskell has two different ways for creating local definitions: <code>let...in</code> and <code>where</code>.</p>
<p><code>where</code> adds local definitions to a definition:</p>
<div class="sourceCode" id="cb46"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb46-1" data-line-number="1"><span class="ot">circleArea ::</span> <span class="dt">Double</span> <span class="ot">-></span> <span class="dt">Double</span></a>
<a class="sourceLine" id="cb46-2" data-line-number="2">circleArea r <span class="fu">=</span> pi <span class="fu">*</span> rsquare</a>
<a class="sourceLine" id="cb46-3" data-line-number="3"> <span class="kw">where</span> pi <span class="fu">=</span> <span class="fl">3.1415926</span></a>
<a class="sourceLine" id="cb46-4" data-line-number="4"> rsquare <span class="fu">=</span> r <span class="fu">*</span> r</a></code></pre></div>
<p><code>let...in</code> is an expression:</p>
<div class="sourceCode" id="cb47"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb47-1" data-line-number="1">circleArea r <span class="fu">=</span> <span class="kw">let</span> pi <span class="fu">=</span> <span class="fl">3.1415926</span></a>
<a class="sourceLine" id="cb47-2" data-line-number="2"> rsquare <span class="fu">=</span> r <span class="fu">*</span> r</a>
<a class="sourceLine" id="cb47-3" data-line-number="3"> <span class="kw">in</span> pi <span class="fu">*</span> rsquare</a></code></pre></div>
<p>Local definitions can also be functions:</p>
<div class="sourceCode" id="cb48"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb48-1" data-line-number="1">circleArea r <span class="fu">=</span> pi <span class="fu">*</span> square r</a>
<a class="sourceLine" id="cb48-2" data-line-number="2"> <span class="kw">where</span> pi <span class="fu">=</span> <span class="fl">3.1415926</span></a>
<a class="sourceLine" id="cb48-3" data-line-number="3"> square x <span class="fu">=</span> x <span class="fu">*</span> x</a></code></pre></div>
<div class="sourceCode" id="cb49"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb49-1" data-line-number="1">circleArea r <span class="fu">=</span> <span class="kw">let</span> pi <span class="fu">=</span> <span class="fl">3.1415926</span></a>
<a class="sourceLine" id="cb49-2" data-line-number="2"> square x <span class="fu">=</span> x <span class="fu">*</span> x</a>
<a class="sourceLine" id="cb49-3" data-line-number="3"> <span class="kw">in</span> pi <span class="fu">*</span> square r</a></code></pre></div>
<p>We’ll get back to the differences between <code>let</code> and <code>where</code>, but mostly you can use which ever you like.</p>
<h3 id="a-word-about-immutability"><span class="header-section-number">1.9.3</span> A Word About Immutability</h3>
<p>Even though things like <code>pi</code> above are often called <em>variables</em>, I’ve chosen to call them <em>definitions</em> here. This is because unlike variables in Python or Java, the values of these definitions can’t be changed. Haskell variables aren’t boxes into which you can put new values, Haskell variables name a value (or rather, an expression) and that’s it.</p>
<p>We’ll talk about immutability again later on this course, but for now it’s enough to know that things like this don’t work.</p>
<div class="sourceCode" id="cb50"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb50-1" data-line-number="1">increment x <span class="fu">=</span> <span class="kw">let</span> x <span class="fu">=</span> x<span class="fu">+</span><span class="dv">1</span></a>
<a class="sourceLine" id="cb50-2" data-line-number="2"> <span class="kw">in</span> x</a></code></pre></div>
<p>This is just an infinite loop, because it tries to define a new variable <code>x</code> with the property <code>x = x+1</code>. Thus when evaluating <code>x</code>, Haskell just keeps computing <code>1+1+1+1+...</code> indefinitely.</p>
<div class="sourceCode" id="cb51"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb51-1" data-line-number="1">compute x <span class="fu">=</span> <span class="kw">let</span> a <span class="fu">=</span> x<span class="fu">+</span><span class="dv">1</span></a>
<a class="sourceLine" id="cb51-2" data-line-number="2"> a <span class="fu">=</span> a<span class="fu">*</span><span class="dv">2</span></a>
<a class="sourceLine" id="cb51-3" data-line-number="3"> <span class="kw">in</span> a</a></code></pre></div>
<pre><code>error:
Conflicting definitions for ‘a’
Bound at: <interactive>:14:17
<interactive>:15:17</code></pre>
<p>Here we get a straightforward error when we’re trying to “update” the value of <code>a</code>.</p>
<p>As a remark, local definitions can <em>shadow</em> the names of variables defined elsewhere. Shadowing is not a side-effect. Instead, shadowing creates a new variable within a more restricted scope that uses the same name as some variable in the outer scope. For example, all of the functions <code>f</code>, <code>g</code>, and <code>h</code> below are legal:</p>
<div class="sourceCode" id="cb53"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb53-1" data-line-number="1"><span class="ot">x ::</span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb53-2" data-line-number="2">x <span class="fu">=</span> <span class="dv">5</span></a>
<a class="sourceLine" id="cb53-3" data-line-number="3"></a>
<a class="sourceLine" id="cb53-4" data-line-number="4"><span class="ot">f ::</span> <span class="dt">Int</span> <span class="ot">-></span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb53-5" data-line-number="5">f x <span class="fu">=</span> <span class="dv">2</span> <span class="fu">*</span> x</a>
<a class="sourceLine" id="cb53-6" data-line-number="6"></a>
<a class="sourceLine" id="cb53-7" data-line-number="7"><span class="ot">g ::</span> <span class="dt">Int</span> <span class="ot">-></span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb53-8" data-line-number="8">g y <span class="fu">=</span> x <span class="kw">where</span> x <span class="fu">=</span> <span class="dv">6</span></a>
<a class="sourceLine" id="cb53-9" data-line-number="9"></a>
<a class="sourceLine" id="cb53-10" data-line-number="10"><span class="ot">h ::</span> <span class="dt">Int</span> <span class="ot">-></span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb53-11" data-line-number="11">h x <span class="fu">=</span> x <span class="kw">where</span> x <span class="fu">=</span> <span class="dv">3</span></a></code></pre></div>
<p>If we apply them to the global constant <code>x</code>, we see the effects of shadowing:</p>
<div class="sourceCode" id="cb54"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb54-1" data-line-number="1">f <span class="dv">1</span> <span class="fu">==></span> <span class="dv">2</span></a>
<a class="sourceLine" id="cb54-2" data-line-number="2">g <span class="dv">1</span> <span class="fu">==></span> <span class="dv">6</span></a>
<a class="sourceLine" id="cb54-3" data-line-number="3">h <span class="dv">1</span> <span class="fu">==></span> <span class="dv">3</span></a>
<a class="sourceLine" id="cb54-4" data-line-number="4"></a>
<a class="sourceLine" id="cb54-5" data-line-number="5">f x <span class="fu">==></span> <span class="dv">10</span></a>
<a class="sourceLine" id="cb54-6" data-line-number="6">g x <span class="fu">==></span> <span class="dv">6</span></a>
<a class="sourceLine" id="cb54-7" data-line-number="7">h x <span class="fu">==></span> <span class="dv">3</span></a></code></pre></div>
<p>It is best to always choose new names for local variables, so that shadowing never happens. That way, the reader of the code will understand where the variables that are used in an expression come from. Note that in the following example, <code>f</code> and <code>g</code> don’t shadow each others’ arguments:</p>
<div class="sourceCode" id="cb55"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb55-1" data-line-number="1"><span class="ot">f ::</span> <span class="dt">Int</span> <span class="ot">-></span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb55-2" data-line-number="2">f x <span class="fu">=</span> <span class="dv">2</span> <span class="fu">*</span> x <span class="fu">+</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb55-3" data-line-number="3"></a>
<a class="sourceLine" id="cb55-4" data-line-number="4"><span class="ot">g ::</span> <span class="dt">Int</span> <span class="ot">-></span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb55-5" data-line-number="5">g x <span class="fu">=</span> x <span class="fu">-</span> <span class="dv">2</span></a></code></pre></div>
<h3 id="pattern-matching"><span class="header-section-number">1.9.4</span> Pattern Matching</h3>
<p>A definition (of a function) can consist of multiple <em>equations</em>. The equations are matched in order against the arguments until a suitable one is found. This is called <em>pattern matching</em>.</p>
<p>Pattern matching in Haskell is very powerful, and we’ll keep learning new things about it along this course, but here are a couple of first examples:</p>
<div class="sourceCode" id="cb56"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb56-1" data-line-number="1"><span class="ot">greet ::</span> <span class="dt">String</span> <span class="ot">-></span> <span class="dt">String</span> <span class="ot">-></span> <span class="dt">String</span></a>
<a class="sourceLine" id="cb56-2" data-line-number="2">greet <span class="st">"Finland"</span> name <span class="fu">=</span> <span class="st">"Hei, "</span> <span class="fu">++</span> name</a>
<a class="sourceLine" id="cb56-3" data-line-number="3">greet <span class="st">"Italy"</span> name <span class="fu">=</span> <span class="st">"Ciao, "</span> <span class="fu">++</span> name</a>
<a class="sourceLine" id="cb56-4" data-line-number="4">greet <span class="st">"England"</span> name <span class="fu">=</span> <span class="st">"How do you do, "</span> <span class="fu">++</span> name</a>
<a class="sourceLine" id="cb56-5" data-line-number="5">greet _ name <span class="fu">=</span> <span class="st">"Hello, "</span> <span class="fu">++</span> name</a></code></pre></div>
<p>The function <code>greet</code> generates a greeting given a country and a name (both <code>String</code>s). It has special cases for three countries, and a default case. This is how it works:</p>
<div class="sourceCode" id="cb57"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb57-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> greet <span class="st">"Finland"</span> <span class="st">"Pekka"</span></a>
<a class="sourceLine" id="cb57-2" data-line-number="2"><span class="st">"Hei, Pekka"</span></a>
<a class="sourceLine" id="cb57-3" data-line-number="3"><span class="dt">Prelude</span><span class="fu">></span> greet <span class="st">"England"</span> <span class="st">"Bob"</span></a>
<a class="sourceLine" id="cb57-4" data-line-number="4"><span class="st">"How do you do, Bob"</span></a>
<a class="sourceLine" id="cb57-5" data-line-number="5"><span class="dt">Prelude</span><span class="fu">></span> greet <span class="st">"Italy"</span> <span class="st">"Maria"</span></a>
<a class="sourceLine" id="cb57-6" data-line-number="6"><span class="st">"Ciao, Maria"</span></a>
<a class="sourceLine" id="cb57-7" data-line-number="7"><span class="dt">Prelude</span><span class="fu">></span> greet <span class="st">"Greenland"</span> <span class="st">"Jan"</span></a>
<a class="sourceLine" id="cb57-8" data-line-number="8"><span class="st">"Hello, Jan"</span></a></code></pre></div>
<p>The special pattern <code>_</code> matches anything. It’s usually used for default cases. Because patterns are matched in order, it’s important to (<em>usually</em>) put the <code>_</code> case last. Consider:</p>
<div class="sourceCode" id="cb58"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb58-1" data-line-number="1">brokenGreet _ name <span class="fu">=</span> <span class="st">"Hello, "</span> <span class="fu">++</span> name</a>
<a class="sourceLine" id="cb58-2" data-line-number="2">brokenGreet <span class="st">"Finland"</span> name <span class="fu">=</span> <span class="st">"Hei, "</span> <span class="fu">++</span> name</a></code></pre></div>
<p>Now the first case gets selected for all inputs.</p>
<div class="sourceCode" id="cb59"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb59-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> brokenGreet <span class="st">"Finland"</span> <span class="st">"Varpu"</span></a>
<a class="sourceLine" id="cb59-2" data-line-number="2"><span class="st">"Hello, Varpu"</span></a>
<a class="sourceLine" id="cb59-3" data-line-number="3"><span class="dt">Prelude</span><span class="fu">></span> brokenGreet <span class="st">"Sweden"</span> <span class="st">"Ole"</span></a>
<a class="sourceLine" id="cb59-4" data-line-number="4"><span class="st">"Hello, Ole"</span></a></code></pre></div>
<p>GHC even gives you a warning about this code:</p>
<pre><code><interactive>:1:1: warning: [-Woverlapping-patterns]
Pattern match is redundant
In an equation for ‘brokenGreet’: brokenGreet "Finland" name = ...</code></pre>
<p>Some more examples follow. But first let’s introduce the standard library function <code>show</code> that can turn (almost!) anything into a string:</p>
<div class="sourceCode" id="cb61"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb61-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> show <span class="dt">True</span></a>
<a class="sourceLine" id="cb61-2" data-line-number="2"><span class="st">"True"</span></a>
<a class="sourceLine" id="cb61-3" data-line-number="3"><span class="dt">Prelude</span><span class="fu">></span> show <span class="dv">3</span></a>
<a class="sourceLine" id="cb61-4" data-line-number="4"><span class="st">"3"</span></a></code></pre></div>
<p>So, here’s an example of a function with pattern matching and a default case that actually uses the value (instead of just ignoring it with <code>_</code>):</p>
<div class="sourceCode" id="cb62"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb62-1" data-line-number="1"><span class="ot">describe ::</span> <span class="dt">Integer</span> <span class="ot">-></span> <span class="dt">String</span></a>
<a class="sourceLine" id="cb62-2" data-line-number="2">describe <span class="dv">0</span> <span class="fu">=</span> <span class="st">"zero"</span></a>
<a class="sourceLine" id="cb62-3" data-line-number="3">describe <span class="dv">1</span> <span class="fu">=</span> <span class="st">"one"</span></a>
<a class="sourceLine" id="cb62-4" data-line-number="4">describe <span class="dv">2</span> <span class="fu">=</span> <span class="st">"an even prime"</span></a>
<a class="sourceLine" id="cb62-5" data-line-number="5">describe n <span class="fu">=</span> <span class="st">"the number "</span> <span class="fu">++</span> show n</a></code></pre></div>
<p>This is how it works:</p>
<div class="sourceCode" id="cb63"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb63-1" data-line-number="1"><span class="dt">Prelude</span><span class="fu">></span> describe <span class="dv">0</span></a>
<a class="sourceLine" id="cb63-2" data-line-number="2"><span class="st">"zero"</span></a>
<a class="sourceLine" id="cb63-3" data-line-number="3"><span class="dt">Prelude</span><span class="fu">></span> describe <span class="dv">2</span></a>
<a class="sourceLine" id="cb63-4" data-line-number="4"><span class="st">"an even prime"</span></a>
<a class="sourceLine" id="cb63-5" data-line-number="5"><span class="dt">Prelude</span><span class="fu">></span> describe <span class="dv">7</span></a>
<a class="sourceLine" id="cb63-6" data-line-number="6"><span class="st">"the number 7"</span></a></code></pre></div>
<p>You can even pattern match on multiple arguments. Again, the equations are tried in order. Here’s a reimplementation of the <code>login</code> function from earlier:</p>
<div class="sourceCode" id="cb64"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb64-1" data-line-number="1"><span class="ot">login ::</span> <span class="dt">String</span> <span class="ot">-></span> <span class="dt">String</span> <span class="ot">-></span> <span class="dt">String</span></a>
<a class="sourceLine" id="cb64-2" data-line-number="2">login <span class="st">"unicorn73"</span> <span class="st">"f4bulous!"</span> <span class="fu">=</span> <span class="st">"unicorn73 logged in"</span></a>
<a class="sourceLine" id="cb64-3" data-line-number="3">login <span class="st">"unicorn73"</span> _ <span class="fu">=</span> <span class="st">"wrong password"</span></a>
<a class="sourceLine" id="cb64-4" data-line-number="4">login _ _ <span class="fu">=</span> <span class="st">"unknown user"</span></a></code></pre></div>
<h3 id="recursion"><span class="header-section-number">1.9.5</span> Recursion</h3>
<p>In Haskell, all sorts of loops are implemented with recursion. Function calls are very efficient, so you don’t need to worry about performance. (We’ll talk about performance later).</p>
<p>Learning how to do simple things with recursion in Haskell will help you use recursion on more complex problems later. Recursion is also often a useful way for thinking about solving harder problems.</p>
<p>Here’s our first recursive function which computes the factorial. In mathematics, factorial is the product of <em>n</em> first positive integers and is written as <em>n!</em>. The definition of factorial is</p>
<blockquote>
<p><em>n! = n * (n-1) * … * 1</em></p>
</blockquote>
<p>For example, <em>4! = 4*3*2*1 = 24</em>. Well anyway, here’s the Haskell implementation of factorial:</p>
<div class="sourceCode" id="cb65"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb65-1" data-line-number="1"><span class="ot">factorial ::</span> <span class="dt">Int</span> <span class="ot">-></span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb65-2" data-line-number="2">factorial <span class="dv">1</span> <span class="fu">=</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb65-3" data-line-number="3">factorial n <span class="fu">=</span> n <span class="fu">*</span> factorial (n<span class="fu">-</span><span class="dv">1</span>)</a></code></pre></div>
<p>This is how it works. We use <code>==></code> to mean “evaluates to”.</p>
<div class="sourceCode" id="cb66"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb66-1" data-line-number="1">factorial <span class="dv">3</span></a>
<a class="sourceLine" id="cb66-2" data-line-number="2"> <span class="fu">==></span> <span class="dv">3</span> <span class="fu">*</span> factorial (<span class="dv">3</span><span class="fu">-</span><span class="dv">1</span>)</a>
<a class="sourceLine" id="cb66-3" data-line-number="3"> <span class="fu">==></span> <span class="dv">3</span> <span class="fu">*</span> factorial <span class="dv">2</span></a>
<a class="sourceLine" id="cb66-4" data-line-number="4"> <span class="fu">==></span> <span class="dv">3</span> <span class="fu">*</span> <span class="dv">2</span> <span class="fu">*</span> factorial <span class="dv">1</span></a>
<a class="sourceLine" id="cb66-5" data-line-number="5"> <span class="fu">==></span> <span class="dv">3</span> <span class="fu">*</span> <span class="dv">2</span> <span class="fu">*</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb66-6" data-line-number="6"> <span class="fu">==></span> <span class="dv">6</span></a></code></pre></div>
<p>What happens when you evaluate <code>factorial (-1)</code>?</p>
<p>Here’s another example:</p>
<div class="sourceCode" id="cb67"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb67-1" data-line-number="1"><span class="co">-- compute the sum 1^2+2^2+3^2+...+n^2</span></a>
<a class="sourceLine" id="cb67-2" data-line-number="2">squareSum <span class="dv">0</span> <span class="fu">=</span> <span class="dv">0</span></a>
<a class="sourceLine" id="cb67-3" data-line-number="3">squareSum n <span class="fu">=</span> n<span class="fu">^</span><span class="dv">2</span> <span class="fu">+</span> squareSum (n<span class="fu">-</span><span class="dv">1</span>)</a></code></pre></div>
<p>A function can call itself recursively multiple times. As an example let’s consider the <em>Fibonacci sequence</em> from mathematics. The Fibonacci sequence is a sequence of integers with the following definition.</p>
<blockquote>
<p>The sequence starts with 1, 1. To get the next element of the sequence, sum the previous two elements of the sequence.</p>
</blockquote>
<p>The first elements of the Fibonacci sequence are 1, 1, 2, 3, 5, 8, 13 and so on. Here’s a function <code>fibonacci</code> which computes the <code>n</code>th element in the Fibonacci sequence. Note how it mirrors the mathematical definition.</p>
<div class="sourceCode" id="cb68"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb68-1" data-line-number="1"><span class="co">-- Fibonacci numbers, slow version</span></a>
<a class="sourceLine" id="cb68-2" data-line-number="2">fibonacci <span class="dv">1</span> <span class="fu">=</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb68-3" data-line-number="3">fibonacci <span class="dv">2</span> <span class="fu">=</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb68-4" data-line-number="4">fibonacci n <span class="fu">=</span> fibonacci (n<span class="fu">-</span><span class="dv">2</span>) <span class="fu">+</span> fibonacci (n<span class="fu">-</span><span class="dv">1</span>)</a></code></pre></div>
<p>Here’s how <code>fibonacci 5</code> evaluates:</p>
<div class="sourceCode" id="cb69"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb69-1" data-line-number="1">fibonacci <span class="dv">5</span></a>
<a class="sourceLine" id="cb69-2" data-line-number="2"> <span class="fu">==></span> fibonacci <span class="dv">3</span> <span class="fu">+</span> fibonacci <span class="dv">4</span></a>
<a class="sourceLine" id="cb69-3" data-line-number="3"> <span class="fu">==></span> (fibonacci <span class="dv">1</span> <span class="fu">+</span> fibonacci <span class="dv">2</span>) <span class="fu">+</span> fibonacci <span class="dv">4</span></a>
<a class="sourceLine" id="cb69-4" data-line-number="4"> <span class="fu">==></span> ( <span class="dv">1</span> <span class="fu">+</span> <span class="dv">1</span> ) <span class="fu">+</span> fibonacci <span class="dv">4</span></a>
<a class="sourceLine" id="cb69-5" data-line-number="5"> <span class="fu">==></span> ( <span class="dv">1</span> <span class="fu">+</span> <span class="dv">1</span> ) <span class="fu">+</span> (fibonacci <span class="dv">2</span> <span class="fu">+</span> fibonacci <span class="dv">3</span>)</a>
<a class="sourceLine" id="cb69-6" data-line-number="6"> <span class="fu">==></span> ( <span class="dv">1</span> <span class="fu">+</span> <span class="dv">1</span> ) <span class="fu">+</span> (fibonacci <span class="dv">2</span> <span class="fu">+</span> (fibonacci <span class="dv">1</span> <span class="fu">+</span> fibonacci <span class="dv">2</span>))</a>
<a class="sourceLine" id="cb69-7" data-line-number="7"> <span class="fu">==></span> ( <span class="dv">1</span> <span class="fu">+</span> <span class="dv">1</span> ) <span class="fu">+</span> ( <span class="dv">1</span> <span class="fu">+</span> ( <span class="dv">1</span> <span class="fu">+</span> <span class="dv">1</span> ))</a>
<a class="sourceLine" id="cb69-8" data-line-number="8"> <span class="fu">==></span> <span class="dv">5</span></a></code></pre></div>
<p>Note how <code>fibonacci 3</code> gets evaluated twice and <code>fibonacci 2</code> three times. This is not the most efficient implementation of the <code>fibonacci</code> function. We’ll get back to this in the next lecture. Another way to think about the evaluation of the fibonacci function is to visualize it as a tree (we abbreviate <code>fibonacci</code> as <code>fib</code>): <!-- There could be some animation or a clickable interactive element for
cycling through these images: --></p>
<p><img src="img/Fibonacci-step1.svg" /></p>
<p><img src="img/Fibonacci-step2.svg" /></p>
<p><img src="img/Fibonacci-step3.svg" /></p>
<p><img src="img/Fibonacci-step4.svg" /></p>
<p><img src="img/Fibonacci-step5.svg" /></p>
<p><img src="img/Fibonacci-step6.svg" /></p>
<p><img src="img/Fibonacci-step7.svg" /></p>
<p><img src="img/Fibonacci-step8.svg" /></p>
<!--
```
_____ + _____
fib 5 ==> | |
fib 3 fib 4
==> __________ + __________
| |
_____ + _____ _____ + _____
| | | |
fib 1 fib 2 fib 2 fib 3
==> __________ + __________
| |
_____ + _____ _____ + _____
| | | |
1 1 1 ___ + ___
| |
fib 1 fib 2
==> __________ + __________
| |
_____ + _____ _____ + _____
| | | |
1 1 1 ___ + ___
| |
1 1
```
-->
<p>This tree then exaclty corresponds with the expression <code>(1 + 1) + (1 + (1 + 1))</code>. Recursion can often produce chain-like, tree-like, nested, or loopy structures and computations. Recursion is one of the main techniques in functional programming, so it’s worth spending some effort in learning it.</p>
<!--  -->
<h2 id="all-together-now"><span class="header-section-number">1.10</span> All Together Now!</h2>
<p>Finally, here’s a complete Haskell module that uses ifs, pattern matching, local defintions and recursion. The module is interested in the <a href="https://en.wikipedia.org/wiki/Collatz_conjecture"><em>Collatz conjecture</em></a>, a famous open problem in mathematics. It asks:</p>
<blockquote>
<p>Does the Collatz sequence eventually reach 1 for all positive integer initial values?</p>
</blockquote>
<p>The Collatz sequence is defined by taking any number as a starting value, and then repeatedly performing the following operation:</p>
<ul>
<li>if the number is even, divide it by two</li>
<li>if the number is odd, triple it and add one</li>
</ul>
<p>As an example, the Collatz sequence for 3 is: 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1 … As you can see, once the number reaches 1, it gets caught in a loop.</p>
<div class="sourceCode" id="cb70"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb70-1" data-line-number="1"><span class="kw">module</span> <span class="dt">Collatz</span> <span class="kw">where</span></a>
<a class="sourceLine" id="cb70-2" data-line-number="2"></a>
<a class="sourceLine" id="cb70-3" data-line-number="3"><span class="co">-- one step of the Collatz sequence</span></a>
<a class="sourceLine" id="cb70-4" data-line-number="4"><span class="ot">step ::</span> <span class="dt">Integer</span> <span class="ot">-></span> <span class="dt">Integer</span></a>
<a class="sourceLine" id="cb70-5" data-line-number="5">step x <span class="fu">=</span> <span class="kw">if</span> even x <span class="kw">then</span> down <span class="kw">else</span> up</a>
<a class="sourceLine" id="cb70-6" data-line-number="6"> <span class="kw">where</span> down <span class="fu">=</span> div x <span class="dv">2</span></a>
<a class="sourceLine" id="cb70-7" data-line-number="7"> up <span class="fu">=</span> <span class="dv">3</span><span class="fu">*</span>x<span class="fu">+</span><span class="dv">1</span></a>
<a class="sourceLine" id="cb70-8" data-line-number="8"></a>
<a class="sourceLine" id="cb70-9" data-line-number="9"><span class="co">-- collatz x computes how many steps it takes for the Collatz sequence</span></a>
<a class="sourceLine" id="cb70-10" data-line-number="10"><span class="co">-- to reach 1 when starting from x</span></a>
<a class="sourceLine" id="cb70-11" data-line-number="11"><span class="ot">collatz ::</span> <span class="dt">Integer</span> <span class="ot">-></span> <span class="dt">Integer</span></a>
<a class="sourceLine" id="cb70-12" data-line-number="12">collatz <span class="dv">1</span> <span class="fu">=</span> <span class="dv">0</span></a>
<a class="sourceLine" id="cb70-13" data-line-number="13">collatz x <span class="fu">=</span> <span class="dv">1</span> <span class="fu">+</span> collatz (step x)</a>
<a class="sourceLine" id="cb70-14" data-line-number="14"></a>
<a class="sourceLine" id="cb70-15" data-line-number="15"><span class="co">-- longest finds the number with the longest Collatz sequence for initial values</span></a>
<a class="sourceLine" id="cb70-16" data-line-number="16"><span class="co">-- between 0 and upperBound</span></a>
<a class="sourceLine" id="cb70-17" data-line-number="17"><span class="ot">longest ::</span> <span class="dt">Integer</span> <span class="ot">-></span> <span class="dt">Integer</span></a>
<a class="sourceLine" id="cb70-18" data-line-number="18">longest upperBound <span class="fu">=</span> longest' <span class="dv">0</span> <span class="dv">0</span> upperBound</a>
<a class="sourceLine" id="cb70-19" data-line-number="19"></a>
<a class="sourceLine" id="cb70-20" data-line-number="20"><span class="co">-- helper function for longest</span></a>
<a class="sourceLine" id="cb70-21" data-line-number="21"><span class="ot">longest' ::</span> <span class="dt">Integer</span> <span class="ot">-></span> <span class="dt">Integer</span> <span class="ot">-></span> <span class="dt">Integer</span> <span class="ot">-></span> <span class="dt">Integer</span></a>
<a class="sourceLine" id="cb70-22" data-line-number="22"><span class="co">-- end of recursion, return longest length found</span></a>
<a class="sourceLine" id="cb70-23" data-line-number="23">longest' number _ <span class="dv">0</span> <span class="fu">=</span> number</a>
<a class="sourceLine" id="cb70-24" data-line-number="24"><span class="co">-- recursion step: check if n has a longer Collatz sequence than the current known longest</span></a>
<a class="sourceLine" id="cb70-25" data-line-number="25">longest' number maxlength n <span class="fu">=</span> <span class="kw">if</span> length <span class="fu">></span> maxlength</a>
<a class="sourceLine" id="cb70-26" data-line-number="26"> <span class="kw">then</span> longest' n length (n<span class="fu">-</span><span class="dv">1</span>)</a>
<a class="sourceLine" id="cb70-27" data-line-number="27"> <span class="kw">else</span> longest' number maxlength (n<span class="fu">-</span><span class="dv">1</span>)</a>
<a class="sourceLine" id="cb70-28" data-line-number="28"> <span class="kw">where</span> length <span class="fu">=</span> collatz n</a></code></pre></div>
<p>We can load the program in GHCi and play with it.</p>
<pre><code>$ stack ghci
GHCi, version 8.2.2: http://www.haskell.org/ghc/ :? for help
Prelude> :load Collatz.hs
[1 of 1] Compiling Collatz ( Collatz.hs, interpreted )
Ok, one module loaded.
*Collatz></code></pre>
<p>Let’s verify that our program computes the start of the Collatz sequence for 3 correctly.</p>
<pre><code>*Collatz> step 3
10
*Collatz> step 10
5
*Collatz> step 5
16</code></pre>
<p>How many steps does it take for 3 to reach 1?</p>
<pre><code>*Collatz> collatz 3
7</code></pre>
<p>What’s the longest Collatz sequence for a starting value under 10? What about 100?</p>
<pre><code>*Collatz> longest 10
9
*Collatz> longest 100
97</code></pre>
<p>The lengths of these Collatz sequences are:</p>
<pre><code>*Collatz> collatz 9
19
*Collatz> collatz 97
118</code></pre>
<h2 id="a-word-about-indentation"><span class="header-section-number">1.11</span> A Word About Indentation</h2>
<p>The previous examples have been fancily indented. In Haskell indentation matters, a bit like in Python. The complete set of rules for indentation is hard to describe, but you should get along fine with these rules of thumb:</p>
<ol type="1">
<li>Things that are grouped together start from the same column</li>
<li>If an expression (or equation) has to be split on to many lines, increase indentation</li>
</ol>
<p>While you can get away with using tabs, it is highly recommended to use spaces for all indenting.</p>
<p>Some examples are in order.</p>
<p>These all are ok:</p>
<div class="sourceCode" id="cb76"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb76-1" data-line-number="1">i x <span class="fu">=</span> <span class="kw">let</span> y <span class="fu">=</span> x<span class="fu">+</span>x<span class="fu">+</span>x<span class="fu">+</span>x<span class="fu">+</span>x<span class="fu">+</span>x <span class="kw">in</span> div y <span class="dv">5</span></a>
<a class="sourceLine" id="cb76-2" data-line-number="2"></a>
<a class="sourceLine" id="cb76-3" data-line-number="3"><span class="co">-- let and in are grouped together, an expression is split</span></a>
<a class="sourceLine" id="cb76-4" data-line-number="4">j x <span class="fu">=</span> <span class="kw">let</span> y <span class="fu">=</span> x<span class="fu">+</span>x<span class="fu">+</span>x</a>
<a class="sourceLine" id="cb76-5" data-line-number="5"> <span class="fu">+</span>x<span class="fu">+</span>x<span class="fu">+</span>x</a>
<a class="sourceLine" id="cb76-6" data-line-number="6"> <span class="kw">in</span> div y <span class="dv">5</span></a>
<a class="sourceLine" id="cb76-7" data-line-number="7"></a>
<a class="sourceLine" id="cb76-8" data-line-number="8"><span class="co">-- the definitions of a and b are grouped together</span></a>
<a class="sourceLine" id="cb76-9" data-line-number="9">k <span class="fu">=</span> a <span class="fu">+</span> b</a>
<a class="sourceLine" id="cb76-10" data-line-number="10"> <span class="kw">where</span> a <span class="fu">=</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb76-11" data-line-number="11"> b <span class="fu">=</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb76-12" data-line-number="12"></a>
<a class="sourceLine" id="cb76-13" data-line-number="13">l <span class="fu">=</span> a <span class="fu">+</span> b</a>
<a class="sourceLine" id="cb76-14" data-line-number="14"> <span class="kw">where</span></a>
<a class="sourceLine" id="cb76-15" data-line-number="15"> a <span class="fu">=</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb76-16" data-line-number="16"> b <span class="fu">=</span> <span class="dv">1</span></a></code></pre></div>
<p>These are not ok:</p>
<div class="sourceCode" id="cb77"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb77-1" data-line-number="1"><span class="co">-- indentation not increased even though expression split on many lines</span></a>
<a class="sourceLine" id="cb77-2" data-line-number="2">i x <span class="fu">=</span> <span class="kw">let</span> y <span class="fu">=</span> x<span class="fu">+</span>x<span class="fu">+</span>x<span class="fu">+</span>x<span class="fu">+</span>x<span class="fu">+</span>x</a>
<a class="sourceLine" id="cb77-3" data-line-number="3"><span class="kw">in</span> div y <span class="dv">5</span></a>
<a class="sourceLine" id="cb77-4" data-line-number="4"></a>
<a class="sourceLine" id="cb77-5" data-line-number="5"><span class="co">-- indentation not increased even though expression is split</span></a>
<a class="sourceLine" id="cb77-6" data-line-number="6">j x <span class="fu">=</span> <span class="kw">let</span> y <span class="fu">=</span> x<span class="fu">+</span>x<span class="fu">+</span>x</a>
<a class="sourceLine" id="cb77-7" data-line-number="7"> <span class="fu">+</span>x<span class="fu">+</span>x<span class="fu">+</span>x</a>
<a class="sourceLine" id="cb77-8" data-line-number="8"> <span class="kw">in</span> div y <span class="dv">5</span></a>
<a class="sourceLine" id="cb77-9" data-line-number="9"></a>
<a class="sourceLine" id="cb77-10" data-line-number="10"><span class="co">-- grouped things are not aligned</span></a>
<a class="sourceLine" id="cb77-11" data-line-number="11">k <span class="fu">=</span> a <span class="fu">+</span> b</a>
<a class="sourceLine" id="cb77-12" data-line-number="12"> <span class="kw">where</span> a <span class="fu">=</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb77-13" data-line-number="13"> b <span class="fu">=</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb77-14" data-line-number="14"></a>
<a class="sourceLine" id="cb77-15" data-line-number="15"><span class="co">-- grouped things are not aligned</span></a>
<a class="sourceLine" id="cb77-16" data-line-number="16">l <span class="fu">=</span> a <span class="fu">+</span> b</a>
<a class="sourceLine" id="cb77-17" data-line-number="17"> <span class="kw">where</span></a>
<a class="sourceLine" id="cb77-18" data-line-number="18"> a <span class="fu">=</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb77-19" data-line-number="19"> b <span class="fu">=</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb77-20" data-line-number="20"></a>
<a class="sourceLine" id="cb77-21" data-line-number="21"><span class="co">-- where is part of the equation, so indentation needs to increase</span></a>
<a class="sourceLine" id="cb77-22" data-line-number="22">l <span class="fu">=</span> a <span class="fu">+</span> b</a>
<a class="sourceLine" id="cb77-23" data-line-number="23"><span class="kw">where</span></a>
<a class="sourceLine" id="cb77-24" data-line-number="24"> a <span class="fu">=</span> <span class="dv">1</span></a>
<a class="sourceLine" id="cb77-25" data-line-number="25"> b <span class="fu">=</span> <span class="dv">1</span></a></code></pre></div>
<p>If you make a mistake with the indentation, you’ll typically get a parse error like this:</p>
<pre><code>Indent.hs:2:1: error: parse error on input ‘where’</code></pre>
<p>The error includes the line number, so just go over that line again. If you can’t seem to get indentation to work, try putting everything on just one long line at first.</p>
<h2 id="quiz"><span class="header-section-number">1.12</span> Quiz</h2>
<p>At the end of each lecture you’ll find a quiz like this. The quizes aren’t graded, they’re just here to help you check you’ve understood the chapter. You can check your answer by clicking on an option. You’ll see a green background if you were right, a red one if you were wrong. Feel free to guess as many times as you want, just make sure you understand why the right option is right in the end.</p>
<p>What is the Haskell equivalent of the C/Java/Python expression <code>combine(prettify(lawn),construct(house,concrete))</code>?</p>
<ol class="quiz">
<li>
<code>combine prettify (lawn) construct (house concerete)</code>
</li>
<li>
<code>combine (prettify lawn (counstruct house concrete))</code>
</li>
<li class="correct">
<code>combine (prettify lawn) (construct house concrete)</code>
</li>
</ol>
What is the C/Java/Python equivalent of the Haskell expression <code>send metric (double population + increase)</code>?
<ol class="quiz">
<li>
<code>send(metric(double(population+increase)))</code>
</li>
<li>
<code>send(metric(double(population)+increase))</code>
</li>
<li class="correct">
<code>send(metric,double(population)+increase)</code>
</li>
<li>
<code>send(metric,double(population+increase))</code>
</li>
</ol>
<p>Which one of the following claims is true in Haskell?</p>
<ol class="quiz">
<li class="correct">
Every value has a type
</li>
<li>
Every type has a value
</li>