-
Notifications
You must be signed in to change notification settings - Fork 0
/
haskelltutintro.html
1701 lines (1447 loc) · 86.6 KB
/
haskelltutintro.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
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<!-- 2022-06-12 Sun 15:16 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>‎</title>
<meta name="generator" content="Org Mode" />
<link rel="stylesheet" href="./tufte.css" type="text/css">
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
displayAlign: "center",
displayIndent: "0em",
"HTML-CSS": { scale: 100,
linebreaks: { automatic: "false" },
webFont: "TeX"
},
SVG: {scale: 100,
linebreaks: { automatic: "false" },
font: "TeX"},
NativeMML: {scale: 100},
TeX: { equationNumbers: {autoNumber: "AMS"},
MultLineWidth: "85%",
TagSide: "right",
TagIndent: ".8em"
}
});
</script>
<script src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS_HTML"></script>
</head>
<body>
<div id="content" class="content">
<div class="header">
<link rel="stylesheet" href="hamb.css">
<link rel="stylesheet" href="tufte.css">
<img src="./images/heading6.png" style="padding: 0px 0px 22px 0px" alt="3-d graph" class="center">
<p>
<nav role="navigation">
<div id="menuToggle">
<!--
A fake / hidden checkbox is used as click reciever,
so you can use the :checked selector on it.
-->
<input type="checkbox" />
<!--
Some spans to act as a hamburger.
They are acting like a real hamburger,
not that McDonalds stuff.
-->
<span></span>
<span></span>
<span></span>
<!--
Too bad the menu has to be inside of the button
but hey, it's pure CSS magic.
-->
<ul id="menu">
<a href="index.html" target="_blank"><li>Home</li></a>
<a href="preface.html" target="_blank"><li>Preface</li></a>
<a href="preliminaries.html" target="_blank"><li>Rabbit Holes</li></a>
<a href="numbers.html" target="_blank"><li>Numbers</li></a>
</ul>
</div>
</nav>
</div>
</p>
<div id="outline-container-org2f8bca0" class="outline-2">
<h2 id="org2f8bca0">Haskell tutorial introduction</h2>
<div class="outline-text-2" id="text-org2f8bca0">
<p>
<label for="mn-demo" class="margin-toggle"></label>
<input type="checkbox" id="mn-demo" class="margin-toggle">
<span class="marginnote"><span class="cap">
<img src="images/CurrySign.png" alt="CurrySign.png" />
Haskell Curry is the namesake of the programming language Haskell.
</span></span>
</p>
<p>
This will be a compliment to the actual online Haskell tutorials
listed below, emphasizing and expanding various points as they come
up. Specifically, <font color = "#650d1c">we’ll <i>shadow</i>
LYAHFGG</font>, the first and primary tutorial, pulling in
extra examples and giving methods and concepts more depth.
</p>
<p>
There are many paths taken when learning Haskell. Being a very
advanced programming environment, it is rich in theoretical computer
science lore. But more than any other language (besides its cousins
Ocaml, SML, and F#) Haskell includes a surprising amount of higher
math. For example, Haskell leverages the abstract algebra concepts of
semigroups and monoids.
</p>
<p>
We’ll save the more mathematical things for the main CIMIC show and
just concentrate on the Haskell programming nuts-and-bolts.
</p>
</div>
</div>
<div id="outline-container-org8b89da3" class="outline-2">
<h2 id="org8b89da3">Rabbit holes</h2>
<div class="outline-text-2" id="text-org8b89da3">
<p>
Let’s repeat (most of) the Haskell rabbit hole list. Note that the
first one is the compulsory dive.
</p>
<p>
<font color = "#375e79">
⌜🐇
</p>
<ol class="org-ol">
<li><a href="http://learnyouahaskell.com/chapters">Learn You a Haskell for Great Good!</a> (LYAHFGG) is a widely-used,
often-suggested beginners site for starting out with Haskell. We’ll
work through it in our CIIC tutorial. (<i>R<sub>C</sub>-hole</i>)</li>
<li>A site haskell.org is suggesting is the UPenn course CIS194. We
suggest the <a href="https://www.seas.upenn.edu/~cis194/spring15/">Spring 2015</a> version since it includes haskell source
files. This is a college course, but for beginners. Click on the
<i>Lectures & Assignments</i> link at the top. (If you’ve got <a href="https://github.com/borgauf/omnimath">our github
repository</a> there’s a directory containing all the Haskell files.)
(<i>R<sub>O</sub>-hole</i>)</li>
<li>An older but still go-to site recommended by many is the <i><a href="http://book.realworldhaskell.org/read/">Real
World Haskell</a></i> site (also book). As the title suggests, it has a
more real-applications slant, and yes, the material can get into
heavy lifting, but one great advantage is it has prodigious
<i>comments</i> attached to ever web page section. So if you didn’t
understand something, typically somebody has already explained it
in depth.</li>
<li>Book-wise, a nice, well-paced text would be <i><a href="https://www.manning.com/books/get-programming-with-haskell#:~:text=about%20the%20book,dive%20into%20custom%20Haskell%20modules.">Get Programming with
Haskell</a></i> by Will Kurt. Will bridges a lot of chasms between
beginner, intermediary, and advanced ideas. In other words, GPWH
gives plain-English explanations of things other treatments might go
deep into theory on. Really helpful, that. (<i>R<sub>O</sub>-hole</i>)</li>
<li>Another big favorite for Haskell starters, but slightly more
challenging is <i><a href="https://www.haskell.org/tutorial/haskell-98-tutorial.pdf">A Gentle Introduction to Haskell 98</a></i>. AGITH uses
more math terminology, which is what we’re doing, but from the
shallow end first. (<i>R<sub>O</sub>-hole</i>)</li>
<li>A while back the programming language Prolog created a list of
ninety-nine sample problems that were solved using Prolog. Since
then many languages have cooked up their own versions of answering
the ninety-nine. Haskell’s is <a href="https://wiki.haskell.org/H-99:_Ninety-Nine_Haskell_Problems">here</a>. We’ll refer to this a lot. When
you peek at the solutions, don’t get psyched out by some of the
answers. Haskell Wiki is a volunteer site and very smart people
like show off their skills resulting in some serious overkill. Just
make sure you can handle the basic answers, and maybe just peruse
the wilder versions. (<i>R<sub>O</sub>-hole</i>)</li>
</ol>
<p>
</font>🐇⌟
</p>
</div>
</div>
<div id="outline-container-orgc739fa4" class="outline-2">
<h2 id="orgc739fa4">Setting up Haskell</h2>
<div class="outline-text-2" id="text-orgc739fa4">
<p>
We will use <a href="https://docs.haskellstack.org/en/stable/README/">The Haskell Tool Stack</a>, which is a project/package
management system for Haskell. In a nutshell, we will install stack,
and then use stack to set up a custom Haskell programming
environment. Besides the executable <code>stack</code>, there will also be the
Haskell compiler <code>ghc</code> and the Haskell interactive mode <code>ghci</code> which
are called as stack arguments <br />
<code>> stack ghci</code> <br />
<code>> stack ghc</code> <br />
More on using them later.
</p>
<p>
This setup guide will go into detail only on the Linux Haskell
install. For full details (also for other OS types) see <a href="https://docs.haskellstack.org/en/stable/install_and_upgrade/">The Haskell
Tool Stack</a>.
</p>
<ul class="org-ul">
<li>The very first step might not be needed, but we’ll do it just to
make sure. Haskell requires (and recommends) a set of Linux system
programs and libraries. Run this at the command line (all on one
line)</li>
<li><code>> sudo apt-get install g++ gcc libc6-dev libffi-dev libgmp-dev make
xz-utils zlib1g-dev git gnupg netbase curl</code> <br />
Typically all of these (with the exception of curl) are already on
your system and won’t be updated.</li>
<li>To install stack run <br />
<code>> curl -sSL https://get.haskellstack.org/ | sh</code> <br />
This will ask for your password; enter it to allow system-wide
install.</li>
<li>Now you should have Haskell stack on your system. For confirmation
of success run <br />
<code>> which stack</code> <br />
This should return <br />
<code>/usr/local/bin/stack</code> <br />
or wherever the <code>stack</code> executable was installed.</li>
<li>Now, run <br />
<code>> echo 'PATH=$HOME/.local/bin:$PATH' >> ~/.bashrc</code> <br />
This tells your shell environment<label for="1" class="margin-toggle sidenote-number"></label><input type="checkbox" id="1" class="margin-toggle"/><span class="sidenote">
Another name for terminal or command line is <i>shell</i>. Each
terminal you start with a command line interface is a <i>shell</i> with a
<i>shell environment</i>. The <code>.bashrc</code> file is its configuration file that
is read and set up each time you start another terminal command line
instance.
</span> about this new location
where some of Haskell executables might be later on if we choose to
install them. We’re not now, but it’s good to have this ahead of
time. Kill your terminal, restart it, then check with <br />
<code>> echo $PATH</code> <br />
You should see something like <br />
<code>> /home/myhomedir/.local/bin:/usr/local/sbin:/usr/local/bin:...</code> <br />
…and many others possibly. But we see our
<code>/home/myhomedir/.local/bin</code>. Good.</li>
</ul>
<p>
Again, stack is project-oriented. That means you have one programming
“project” that you want to accomplish. But for the time being we only
want to use the Haskell REPL<label for="2" class="margin-toggle sidenote-number"></label><input type="checkbox" id="2" class="margin-toggle"/><span class="sidenote">
<b>REPL</b> stands for <i>read, evaluate, print, loop</i>, which is
essentially what your terminal command line is doing. That is to say,
the Haskell REPL, called <i>ghci</i> is an interactive world: Give it a
task, e.g., <code>1 + 1</code>, and it returns a response, <code>2</code>, then it gives you
back a prompt and waits for your next task. This is how LYAHFGG starts
out executing Haskell code.
</span> to load the practice code we saved
into <code>*.hs</code> files, i.e., not a single project. Still, these <code>*.hs</code>
will reside in a project directory, a project that we set up with
stack — even though we won’t use the project files
specifically. Eventually, we’ll convert from using <code>hs</code> loaded into
the REPL session to using Emacs’ powerful <i>org-mode literate
programming</i> with the REPL. And then we might actually use the project
way to program in Haskell, especially if we want to create a
stand-alone executable.
</p>
<ul class="org-ul">
<li>In your top home directory<label for="3" class="margin-toggle sidenote-number"></label><input type="checkbox" id="3" class="margin-toggle"/><span class="sidenote">
You can always get back home by typing <code>cd</code> and Enter. Then do
<code>pwd</code> to confirm you’ve gone to top home. And you can always test
where you are with <code>> pwd</code> (present working directory).
</span> create an org<label for="4" class="margin-toggle sidenote-number"></label><input type="checkbox" id="4" class="margin-toggle"/><span class="sidenote">
…anticipating using org mode.
</span> directory <br />
<code>> mkdir org</code> <br />
and <code>cd</code> into it <br />
<code>> cd org</code></li>
<li>Now we’ll create a project, which will automatically create a new
directory with the same name under <code>~/org/</code>. Type <br />
<code>> stack new haskellwork1</code> (or whatever you want to call it) <br />
which will set up a project in a subdirectory of <code>org</code> called
<code>haskellwork1</code>.</li>
<li><code>cd</code> into <code>haskellwork1</code> and do <code>ls</code> to get a file listing. You’ll
see many newly created files and directories. But again, we will not
use them at this point.</li>
<li>Still in the <code>haskellwork1</code> directory type
<code>> stack setup</code> <br />
which should give a short message about using a sandboxed GHC etc.</li>
<li>Next, type <code>> stack build</code> <br />
which will run through an executable build procedure and return you
the prompt. This actually builds the starter-dummy project we just
created. All of this creates a Haskell programming environment we
want.</li>
<li>To test our starter-dummy project’s new executable run <br />
<code>> stack exec haskellwork1-exe</code> <br />
which will return <code>someFucn</code>, i.e., the output of the project’s
dummy starter code. Again, this is just testing that the Haskell
environment is ready. We’ll be creating our practice files in the
<code>haskellwork1</code> directory completely independent of the
<code>haskellwork1</code> project.</li>
</ul>
</div>
</div>
<div id="outline-container-org57e19ea" class="outline-2">
<h2 id="org57e19ea">Let’s start</h2>
<div class="outline-text-2" id="text-org57e19ea">
<p>
At this point we’re ready to go over to Miran Lipovača’s very popular
<i>Learn You a Haskell For Great Good</i> site and start in<label for="5" class="margin-toggle sidenote-number"></label><input type="checkbox" id="5" class="margin-toggle"/><span class="sidenote">
Maybe check out the <a href="http://learnyouahaskell.com/faq">FAQ</a>.
</span>. Our
first stop will be his <a href="http://learnyouahaskell.com/introduction">Introduction</a>. But before you start on this
tutorial, go ahead and read his introduction, then move into <a href="http://learnyouahaskell.com/starting-out">Starting
Out</a>, then the next chapter <a href="http://learnyouahaskell.com/types-and-typeclasses">Types and Typeclasses</a>. Just read and try to
understand at this point. We’ll borrow a few very rudimentary things
from these chapters right here just for demonstration purposes. As
you’ll see as we advance, we’ll typically explain one thing while
relying on future (lightly), past (heavily), or parallel
(appropriately) materials. \(\mathfrak{Fazit}\;\): Get in the habit of
reading ahead<label for="6" class="margin-toggle sidenote-number"></label><input type="checkbox" id="6" class="margin-toggle"/><span class="sidenote">
We’re diving into the Introduction because it contains lots of
ideas we really need to grok before we get going.
</span>.
</p>
</div>
<div id="outline-container-org2bd1757" class="outline-3">
<h3 id="org2bd1757"><i>So what’s Haskell?</i> State and referential transparency</h3>
<div class="outline-text-3" id="text-org2bd1757">
<p>
In just his <i>So what’s Haskell?</i> section Miran says a lot, so let’s
unpack it a bit<label for="7" class="margin-toggle sidenote-number"></label><input type="checkbox" id="7" class="margin-toggle"/><span class="sidenote">
Actually, this page will deal only with that first
paragraph. The rest we’ll incorporate in later pages.
</span>. First is the concept of <i>state</i>, which is a
very big deal in computers, physics and engineering, as well as many
other STEM and soft-science fields. When we say <i>the state of things</i>
we mean the present conditions — which implies that the state might
change. And we might have heard of <i>phase</i>, e.g., the three phases of
matter: solid, liquid, and gaseous<label for="8" class="margin-toggle sidenote-number"></label><input type="checkbox" id="8" class="margin-toggle"/><span class="sidenote">
In addition to the states solid, liquid, gas, there’s also
crystalline, colloid, glassy, amorphous, and plasma.
</span>. You’ll hear the terms phase
of matter and the state of matter used interchangeably. In our
treatment we will borrow from an explanation given by Susskind and
Hrabovsky in their book <i>The Theoretical Minimum</i><label for="9" class="margin-toggle sidenote-number"></label><input type="checkbox" id="9" class="margin-toggle"/><span class="sidenote">
See the video <a href="https://youtu.be/ApUFtLCrU90">here</a>. Just the first part is germane to our
discussion here.
</span>.
</p>
<p>
Basically, a given situation we’re examining, a given <i>system</i>, can
have
</p>
<ul class="org-ul">
<li><a href="https://en.wikipedia.org/wiki/Degrees_of_freedom">degrees of freedom</a> (DOF)</li>
<li>states</li>
<li>rules or laws describing the system’s progress or behavior</li>
</ul>
<p>
In their book, Susskind and Hrabovsky begin with a system consisting
of one coin glued down to a table with heads up. So we have <b>one coin</b>
(corresponding to one parameter or DOF) and just one possible <b>state</b>
of this single DOF<label for="10" class="margin-toggle sidenote-number"></label><input type="checkbox" id="10" class="margin-toggle"/><span class="sidenote">
Degrees of freedom are not exactly the same as variables. A
Cartesian coordinate system (CCS) with \(x\) and \(y\) axes can be thought
of as a system with two DOF — or just one DOF. The difference is the
relationship \(x\) and \(y\) are in. DOFs must be truly independent of one
another. So if we’re just establishing a CCS as <i>all possible
coordinate pairs</i>, both elements of a pair corresponding to all the
real numbers running up and down each axis, then yes, the CCS has two
DOFs. But if we’re talking about a function \(f(x) = y\;\) depicted on a
CCS then we mean only one DOF, \(x;\) since the \(y\) is now considered
<i>dependent</i> on \(x\), i.e., not free. Knowing this, how many DOFs does
an operating traffic light have, one, two, three?
</span> coin, namely <b>heads</b>. If we try to describe
this system, i.e., describe a <b>law</b> for the behavior of this system,
we can intuitively see that it’s extremely restricted and
minimalistic. The law for this system would simply be <i>the state is
always heads</i>, i.e., the state never changes. Not very interesting,
not very information-rich<label for="11" class="margin-toggle sidenote-number"></label><input type="checkbox" id="11" class="margin-toggle"/><span class="sidenote">
Contrast this with a <i>writing system</i> like English with
twenty-six letters, which in comp-sci-speak is a “nonempty finite set
of symbols.” There’s an infinite number of possible states of our
English writing system, especially considering all the millions of
people using it!
</span>.
</p>
<p>
We know intuitively what <i>always</i> means: constant, eternal, never
ending. Such words imply time passing, steps, iterations taken — and
a thing, a system remaining basically constant, the same. Words like
<i>perpetual</i>, <i>continual</i>, <i>periodic</i>, <i>intermittent</i>, <i>random</i>,
<i>cyclic</i>, <i>acyclic</i>, <i>terminating</i>, <i>non-terminating</i>, <i>dynamic</i>,
<i>static</i> and many others all beg the notion of some process moving
along, step-by-step perhaps, or assessed at intervals of time. Even
words like <i>deterministic</i> and <i>chaotic</i> invoke the idea of something
being repeatedly measured as to its state, then a <i>pattern</i>, a
<i>sequence</i><label for="12" class="margin-toggle sidenote-number"></label><input type="checkbox" id="12" class="margin-toggle"/><span class="sidenote">
When we use <i>sequence</i> we’ll be leaning into the mathematical
meaning. Basically, a sequence is a an <i>ordered</i> list of things,
objects, numbers that may or may not exhibit a pattern. As we explore
<i>set theory</i> we’ll see math explained in terms of sets. For example, a
sequence can be thought of as a function that maps the <i>set</i> of
natural counting numbers (\(\mathbb{N} = 0,1,2,3,\ldots\;\;\;\)) to the
<i>set</i> of objects that make up our ordered list. This may seem odd at
first, but we just introduced the idea of <i>indexing</i> or <i>enumerating</i>
the numerical position of the elements of our sequence.
</span> of states is generalized to a descriptive adjective.
</p>
<p>
A single coin system — not glued down — has one DOF with just two
possible states, to be decided by flipping the coin. We may then
perform a <i>sequence</i> of coin flips at our leisure to determine this
sequence of flips’ pattern, i.e., the coin-flip system’s
law<label for="13" class="margin-toggle sidenote-number"></label><input type="checkbox" id="13" class="margin-toggle"/><span class="sidenote">
Think about how a car moving <i>continuously</i> along a road. We
could literally check its location down to the millisecond, giving us
a very fine, very time-dependent snapshot of its location. However,
coin flipping, which results in heads or tails, is <i>discrete</i>, i.e.,
when the coin lands it is instantly one or the other; hence, the
continuous passing of time isn’t relevant in the discrete world. Lots
more on <i>discrete</i> math coming.
</span>. For example, if we flip our coin over and over and it
magically alternates between heads or tails, never deviating, we may
describe it, establish its law as following this formula<label for="14" class="margin-toggle sidenote-number"></label><input type="checkbox" id="14" class="margin-toggle"/><span class="sidenote">
(1) is an example of a <i>recurrence relation</i>. You’re probably
more used to <i>closed</i> formulae. For example \(f(x) = x^{2}\;\) is a closed
version of this recurrence relation <br />
\begin{align*}
f(0) &= 0 \\
f(n) &= f(n-1) + 2n-1 \;\; for \; n \ge 1
\end{align*}
Lots more on recurrence relations and recursion in general later.
</span>
</p>
\begin{align}
\sigma(n+1) = -\sigma(n)
\end{align}
<p>
In (1), \(\sigma\) (<i>sigma</i>) will stand for our single DOF. For the possible
values of \(\sigma\) we say \(1\) means heads and \(-1\) means tails. \(n\) stands
for the counting numbers (\(1,2,3,\ldots\;\)) that will serve to <i>index</i>
each coin flip in a sequence of coin flips. For example, if on our
first flip \(\sigma(1) = 1\;\), heads, then according to (1) our second flip
\(\sigma(2)\;\) will be \(-1\;\) or tails since
</p>
\begin{align*}
\sigma(1) &= 1\;\;\ldots\;\; \text{heads is our starting point} \\
\sigma(2) &= -\sigma(1) \;\;\ldots\;\; \text{using (1)} \\
\sigma(2) &= -(1) \;\;\ldots\;\; \text{substituting} \\
\sigma(2) &= -1 \quad \ldots\;\text{tails}
\end{align*}
<p>
The third flip in our sequence is
</p>
\begin{align*}
\sigma(2) &= -1\;\;\ldots\;\; \text{tails is our starting point} \\
\sigma(3) &= -\sigma(2) \;\;\ldots\;\; \text{using (1)} \\
\sigma(3) &= -(-1) \;\;\ldots\;\; \text{substituting} \\
\sigma(3) &= 1 \;\;\ldots\;\; \text{heads}
\end{align*}
<p>
A table of the sequence of coin-flip states would be
</p>
<table id="org5c773e5" border="2" cellspacing="0" cellpadding="6" rules="all" frame="border">
<caption class="t-above"><span class="table-number">Table 1:</span> Coin-flip table</caption>
<colgroup>
<col class="org-left" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
</colgroup>
<tbody>
<tr>
<td class="org-left">n</td>
<td class="org-right">1</td>
<td class="org-right">2</td>
<td class="org-right">3</td>
<td class="org-right">4</td>
<td class="org-right">5</td>
<td class="org-right">6</td>
<td class="org-right">7</td>
<td class="org-right">8</td>
</tr>
<tr>
<td class="org-left">σ</td>
<td class="org-right">1</td>
<td class="org-right">-1</td>
<td class="org-right">1</td>
<td class="org-right">-1</td>
<td class="org-right">1</td>
<td class="org-right">-1</td>
<td class="org-right">1</td>
<td class="org-right">-1</td>
</tr>
</tbody>
</table>
<p>
A Haskell version of (1) looks very similar<label for="15" class="margin-toggle sidenote-number"></label><input type="checkbox" id="15" class="margin-toggle"/><span class="sidenote">
This Haskell code is meant to be just show-and-tell. If you’ve
read ahead you should be able to follow it. Quickly, we have a <i>base
case</i>, i.e., the first line where we establish whether the first flip
is heads or tails, then the recurrence relationship. <i>Lots</i> more about
Haskell recursion soon. (BTW, <code>--</code> is a Haskell comment, not part of
the program.)
</span>
</p>
<pre class="code"><code><span class="org-haskell-constructor">:</span><span class="org-rainbow-delimiters-depth-1">{</span>
<span class="org-haskell-definition">σ</span> 1 <span class="org-haskell-operator">=</span> 1 <span class="org-comment-delimiter">-- </span><span class="org-comment">we start with 1, heads</span>
<span class="org-haskell-definition">σ</span> n <span class="org-haskell-operator">=</span> <span class="org-rainbow-delimiters-depth-2">(</span><span class="org-haskell-operator">-</span>1<span class="org-rainbow-delimiters-depth-2">)</span> <span class="org-haskell-operator">*</span> σ <span class="org-rainbow-delimiters-depth-2">(</span>n <span class="org-haskell-operator">-</span> 1<span class="org-rainbow-delimiters-depth-2">)</span>
<span class="org-haskell-constructor">:</span><span class="org-rainbow-delimiters-depth-1">}</span>
</code></pre>
<p>
The only real difference is we’ve indicated in the base case (line 1)
that flip 1 starts things off as heads. Also, we’ve reduced the
function argument \(n\) by \(1\) on both side, which doesn’t affect
it. Testing
</p>
<pre class="code"><code><span class="org-haskell-definition">σ</span> 7
</code></pre>
<pre class="example">
1
</pre>
<p>
and this value checks against Table 1<label for="16" class="margin-toggle sidenote-number"></label><input type="checkbox" id="16" class="margin-toggle"/><span class="sidenote">
Again, this is show code. We’ve used the unicode symbol σ for
sigma because Haskell recognizes it and it’s cool to look as
mathematical as possible, but usually we’ll just spell out function
names.
</span>. We can produce a Haskell
version of a sequence of coin flip state changes with <code>map</code><label for="17" class="margin-toggle sidenote-number"></label><input type="checkbox" id="17" class="margin-toggle"/><span class="sidenote">
<code>map</code> is a function that takes a function, in our case σ, and
applies it to the individual elements of a <b>list</b>, then outputs the
resulting new list. This is our first demonstration of a functional
programming superpower, i.e., functions using not just regular data as
input, but other functions as well. Lots to come on this subject.
</span>,
feeding it our <code>σ</code> function and a list generated from a Haskell
enumeration range from \(1\) to \(15\) corresponding to fifteen coin flips
</p>
<pre class="code"><code><span class="org-haskell-definition">map</span> σ <span class="org-rainbow-delimiters-depth-1">[</span>1<span class="org-haskell-operator">..</span>15<span class="org-rainbow-delimiters-depth-1">]</span>
</code></pre>
<pre class="example">
[1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1]
</pre>
<p>
Since Haskell is a typed language we could do better that faking heads
with \(1\) and tails with \(-1\). We could create an actual custom-made
<i>data type</i> for our state space
</p>
<pre class="code"><code><span class="org-haskell-keyword">data</span> <span class="org-haskell-type">Coin</span> <span class="org-haskell-operator">=</span> <span class="org-haskell-constructor">Heads</span> <span class="org-haskell-operator">|</span> <span class="org-haskell-constructor">Tails</span>
</code></pre>
<p>
We won’t go into how this can be incorporated into our function <code>σ</code>
yet, but notice that we have a “means the same thing” correspondence
between \(1\) and \(-1\) and <code>Heads</code> and <code>Tails</code>. In Haskell (and the type
theory math world) this correspondence is called an
<i>isomorphism</i>. Which basically means we can set up a translation
between these two representations of a flip outcome. Can you think of
other “either-or” two-possibility types? <i>True</i> and <i>False</i>, or <i>Top</i>
and <i>Bottom</i>, <i>Left</i> and <i>Right</i>, or even <i>Sun</i> and <i>Moon</i> or <i>Mine</i>
and <i>Not-mine</i>. For all of these versions of two-state either-or we
can create a translation from one to the other<label for="18" class="margin-toggle sidenote-number"></label><input type="checkbox" id="18" class="margin-toggle"/><span class="sidenote">
One way of “jumping” in a two-state system from one state to
the other would be <i>negation</i>, e.g., \(Negate(1) = -1\;\;\). The Haskell
operator <code>not</code> does this (the math logic symbol is \(\lnot\;\;\)), which
works out of the box for some types, while for others the concept of
negation must be defined. Right. What would it mean to <i>negate</i> <code>Moon</code>
to <code>Sun</code> back to <code>Moon</code> again? More on this trick later.
</span>. As we’ll see in
the not too distant future, Haskell likes to leverage isomorphisms…
</p>
</div>
</div>
<div id="outline-container-orgccc997a" class="outline-3">
<h3 id="orgccc997a">Modular arithmetic</h3>
<div class="outline-text-3" id="text-orgccc997a">
<p>
Everyone is familiar with <i>clock modularity</i>. So what time is it \(3\)
hours past \(2\;\) o’clock? Obviously \(5\;\) o’clock. But what about \(15\)
hours past \(2\!:\!00\;\)? So \(2 + 15 = 17\;\). Yes, but we ran out of
clock at \(12\!:\!00\;\); anything beyond begins to repeat on the clock
face. Therefore, an analog clock is said to have a <i>modularity of
\(12\;\)</i>. This means a single state change, i.e., adding \(1\) hour, or
conducting a sequence<label for="19" class="margin-toggle sidenote-number"></label><input type="checkbox" id="19" class="margin-toggle"/><span class="sidenote">
In math the elements of a sequence are strictly
consecutive. Again, a sequence’s elements <i>and</i> their order makes it
unique.
</span> of state changes, e.g., adding \(x\) hours,
can only match with one of twelve possible hours. In math-speak, our
system’s law places us in a <i>modulo-12</i> world where every enumerated
state change is <i>congruent</i> to one of the twelve numbers of the clock
face. Right.
</p>
<table id="orgd31fee3" border="2" cellspacing="0" cellpadding="6" rules="all" frame="border">
<caption class="t-above"><span class="table-number">Table 2:</span> Twelve-hour clock table</caption>
<colgroup>
<col class="org-left" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
</colgroup>
<tbody>
<tr>
<td class="org-left">n</td>
<td class="org-right">1</td>
<td class="org-right">2</td>
<td class="org-right">3</td>
<td class="org-right">4</td>
<td class="org-right">5</td>
<td class="org-right">6</td>
<td class="org-right">7</td>
<td class="org-right">8</td>
<td class="org-right">9</td>
<td class="org-right">10</td>
<td class="org-right">11</td>
<td class="org-right">12</td>
<td class="org-right">13</td>
<td class="org-right">14</td>
<td class="org-right">15</td>
<td class="org-right">16</td>
<td class="org-right">17</td>
<td class="org-right">18</td>
<td class="org-right">19</td>
<td class="org-right">20</td>
<td class="org-right">21</td>
<td class="org-right">22</td>
<td class="org-right">23</td>
<td class="org-right">24</td>
<td class="org-right">25</td>
<td class="org-right">26</td>
</tr>
<tr>
<td class="org-left">h</td>
<td class="org-right">1</td>
<td class="org-right">2</td>
<td class="org-right">3</td>
<td class="org-right">4</td>
<td class="org-right">5</td>
<td class="org-right">6</td>
<td class="org-right">7</td>
<td class="org-right">8</td>
<td class="org-right">9</td>
<td class="org-right">10</td>
<td class="org-right">11</td>
<td class="org-right">12</td>
<td class="org-right">1</td>
<td class="org-right">2</td>
<td class="org-right">3</td>
<td class="org-right">4</td>
<td class="org-right">5</td>
<td class="org-right">6</td>
<td class="org-right">7</td>
<td class="org-right">8</td>
<td class="org-right">9</td>
<td class="org-right">10</td>
<td class="org-right">11</td>
<td class="org-right">12/0</td>
<td class="org-right">1</td>
<td class="org-right">2</td>
</tr>
</tbody>
</table>
<p>
Since we know timekeeping, we’re familiar with this idea of \(x\) hours
from now is \(y\) o’clock. According to our table above, \(17\) or
\(17\!:\!00\;\) matches with \(5\;\) o’clock, again, this is just military
time. Now, what time would it be \(237\) hours from \(2:00\;\)<label for="20" class="margin-toggle sidenote-number"></label><input type="checkbox" id="20" class="margin-toggle"/><span class="sidenote">
Let’s forget counting days for now.
</span>?
Or, at the \(2 + 237 = 239\;\;\) state change, what is the state of our
system given our system law is \(12\) strictly increasing and repeating
states?
</p>
<p>
In modularity arithmetic we’re asking what number(s) is(are)
<i>congruent</i> with \(239\) <i>modulo</i> \(12\;\), written \(239 \equiv x (mod
12)\;\;\)? This means if we line up \(1\) through \(12\;\), strictly
increasing, over and over, back to back, matching them to our counting
number index, \(239\) must match with some possible hour between \(1\) and
\(12\;\).
</p>
<p>
Probably your first intuitive idea would be to just divide: \(239 \div 12
=\; ?\;\) … But we must be careful here, we’re in the realm of
discrete numbers. Just any old calculator will give you a decimal
number if it doesn’t divide it evenly, i.e., remainder zero. Let’s
take a look at what Haskell does with a simpler situation from our
table above. Consider \(14\) hours after starting. Again, with military
time we see it corresponds to \(2\;\) o’clock, however,
</p>
<pre class="code"><code>14 <span class="org-haskell-operator">/</span> 12
</code></pre>
<pre class="example">
1.1666666666666667
</pre>
<p>
Unless we want to do some extra math (\(0.166667 \cdot 12 = 2.0\;\;\;\)), we
should try something else. Here’s a better way: Haskell’s <code>quot</code> will
give only the <i>quotient</i> part of a division
</p>
<pre class="code"><code>14 <span class="org-haskell-operator">`quot`</span> 12
</code></pre>
<pre class="example">
1
</pre>
<p>
So \(12\) “goes into” \(14\) one time, and the <i>remainder</i> of \(14 \div 12\;\)
is
</p>
<pre class="code"><code>14 <span class="org-haskell-operator">`rem`</span> 12
</code></pre>
<pre class="example">
2
</pre>
<p>
or, even handier
</p>
<pre class="code"><code>14 <span class="org-haskell-operator">`quotRem`</span> 12
</code></pre>
<pre class="example">
(1,2)
</pre>
<p>
where the pair <code>(1,2)</code> indicates \(1\) for the quotient and \(2\) for the
remainder. Let’s try it on our bigger number
</p>
<pre class="code"><code>239 <span class="org-haskell-operator">`quotRem`</span> 12
</code></pre>
<pre class="example">
(19,11)
</pre>
<p>
Hmmm. Is one of these our answer, i.e., the first or second number in
this <i>tuple</i>? Well, our table above only seems to match two
twelve-hour clocks with a twenty-four-hour clock, then two more into
the third twelve-hour clock. Perhaps the answer is saying we went \(19\)
bunches of \(12\) forward, which amounted to \(228\;\), then we needed to
go \(11\) additional hours to get to hour \(239\;\). Does that make sense?
</p>
<p>
One calculator on the Internet says \(239\) hours is \(9\) days and \(23\)
hours. But since a day is \(24\) hours, we should double \(9\) since there
are two go-rounds of the clock per day. That means \(18\) twelve-hour
half-days. Now \(23 - 12 = 11\;\;\). So adding in that last \(12\) hours
to \(18\) to get \(19\), we have what our <code>quotRem</code> calculation gave us,
\(19\) twelve-hour blocks, plus the additional \(11\) hours. In modular
math, we would say \(239 \equiv 11 \;mod\; (12)\;\), that is, \(239\) is
congruent to \(11\) modulo \(12\), which effectively means that as the
hours or state changes continue, \(11\) and \(239\) are related by being
multiples of \(12\) from each other, in fact, \(19\) multiples of \(12\)
separate them.
</p>
</div>
</div>
<div id="outline-container-org4b80dd3" class="outline-3">
<h3 id="org4b80dd3">Throwing dice</h3>
<div class="outline-text-3" id="text-org4b80dd3">
<p>
Let’s look at dice as a system. Actually, we’ll just consider one
single six-sided die, i.e., the six possible states in which the die
system might be in after a throw. Using the Haskell <b>list</b> <i>data
structure</i>, the <i>state space</i> can be expressed as elements of a list
</p>
<pre class="code"><code><span class="org-haskell-definition">dieState</span> <span class="org-haskell-operator">=</span> <span class="org-rainbow-delimiters-depth-1">[</span>1,2,3,4,5,6<span class="org-rainbow-delimiters-depth-1">]</span>
</code></pre>
<p>
➝ Question: Does the <i>order</i> of our states list matter, i.e., we have
<i>enumeration</i> of the six states, but is there <i>ordinality</i>? <br />
➝ Answer: Yes and no. Just considering a listing of the possible
states, i.e., a state space list, no. But if we talk about a
sequence of throws, then a list of the sequential progression of
state changes would of course depend on order.
</p>
<p>
Again, the Haskell list data structure will be our best substitute for
a mathematical set or sequence, and we’ll work around its
limitations. For example, the Haskell lists <code>[1,2,3,4,5,6]</code> and
<code>[6,5,4,3,2,1]</code> are two different and unequal lists, even though as
mathematical sets they are considered the same. Hence, Haskell lists
aren’t the best for math sets where order (and even repeating
elements) don’t matter. But lists are adequate in depicting a math
sequence where the sequential order matters and a repeating element
does in fact mean a state has been repeated at that point.
</p>
<p>
Like in our coin example, we’ll start with a loaded or trick die that
produces a steady repeating pattern of
\(1,2,3,4,5,6,1,2,3,4,5,6,\ldots\;\;\;\) for \(1,2,3,\ldots,n\;\)
rolls. The system <i>cycles</i>, i.e., repeats a six-throw sequence
pattern<label for="21" class="margin-toggle sidenote-number"></label><input type="checkbox" id="21" class="margin-toggle"/><span class="sidenote">
Interestingly, a system that cycles in a <i>probabilistic</i> way,
i.e., there’s a given <i>chance</i> of a certain state change happening,
would be the domain of <a href="https://www.fa17.eecs70.org/static/notes/n24.html">Markov chains</a>, which we’ll look at later.
</span>. Hence, it is <i>modular</i> like our clock example above
where <font color = "#650d1c">every state of the sequence
will be <i>congruent</i> to one of the elements of the state
space</font>.
</p>
<table id="orgd6f0fff" border="2" cellspacing="0" cellpadding="6" rules="all" frame="border">
<caption class="t-above"><span class="table-number">Table 3:</span> Trick die rolls</caption>
<colgroup>
<col class="org-left" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
</colgroup>
<tbody>
<tr>
<td class="org-left">n</td>
<td class="org-right">1</td>
<td class="org-right">2</td>
<td class="org-right">3</td>
<td class="org-right">4</td>
<td class="org-right">5</td>
<td class="org-right">6</td>
<td class="org-right">7</td>
<td class="org-right">8</td>
<td class="org-right">9</td>
<td class="org-right">10</td>
<td class="org-right">11</td>
<td class="org-right">12</td>
<td class="org-right">13</td>
<td class="org-right">14</td>
<td class="org-right">15</td>
<td class="org-right">16</td>
<td class="org-right">17</td>
<td class="org-right">18</td>
</tr>
<tr>
<td class="org-left">r</td>
<td class="org-right">1</td>
<td class="org-right">2</td>
<td class="org-right">3</td>
<td class="org-right">4</td>
<td class="org-right">5</td>
<td class="org-right">6</td>
<td class="org-right">1</td>
<td class="org-right">2</td>
<td class="org-right">3</td>
<td class="org-right">4</td>
<td class="org-right">5</td>
<td class="org-right">6</td>
<td class="org-right">1</td>
<td class="org-right">2</td>
<td class="org-right">3</td>
<td class="org-right">4</td>
<td class="org-right">5</td>
<td class="org-right">6</td>
</tr>
</tbody>
</table>
<p>
What about a six-throw sequence that repeats a pattern, but not