-
Notifications
You must be signed in to change notification settings - Fork 0
/
ThinkingAlgebraicallyWithElm.tex
2389 lines (2142 loc) · 118 KB
/
ThinkingAlgebraicallyWithElm.tex
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
\documentclass[12pt]{amsbook}
\usepackage{amsmath,amssymb,graphicx}
\usepackage{mathpazo}
\usepackage{pdfsync}
\usepackage{listings}
\usepackage{hyperref}
\usepackage{color}
\usepackage[margin=2.25cm]{geometry}
\usepackage[all]{xy}
%\usepackage{draftwatermark}
%\SetWatermarkText{Rough Draft}
%\SetWatermarkScale{1}
% this defines the environment for typesetting bits of code
\lstnewenvironment{code}[0]
{\lstset{
backgroundcolor=\color{white},
tabsize=4,
rulecolor=\color{black},
language=haskell,
basicstyle=\Small,
aboveskip={1.5\baselineskip},
columns=fixed,
showstringspaces=false,
extendedchars=true,
breaklines=true,
prebreak = \raisebox{0ex}[0ex][0ex]{\ensuremath{\hookleftarrow}},
frame=none,
showtabs=false,
showspaces=false,
showstringspaces=false,
identifierstyle=\color[rgb]{0.0,0.0,0.0},
keywordstyle=\color[rgb]{0.0,0,0.0},
commentstyle=\color[rgb]{0,0,0},
stringstyle=\color[rgb]{0.0,0,0.0},
upquote=false
}}
{}
\newcommand{\elm}[1]{\texttt{#1}}
\title{Thinking Algebraically with Elm \\ Version 0.81}
\author{\copyright\ 2015-2017, Christopher Kumar Anand}
\date{9 October 2017}
\begin{document}
\maketitle
\vfill
\begin{center}
This book is dedicated to the student volunteers, teaching assistants and
graduate students for helping to reimagine literacy,
but especially to Curtis d'Alves.
\end{center}
\vfill
\newpage
\tableofcontents
%\chapter{Changes}\label{Ch:Changes}
%
%- hanoi
%
%- talk about pipelines more, "assembly lines"
% - move fold into chapter with map
% ( delete FRP )
%
%- graphicsApp chapter following map
% - draw a fence
%
%- basement
%
%- notificationsApp chapter follow stateDiagrams
% - add ELM Architecture
%
%- complexity (add diagrams?)
%
%- gameApp - pong
% - slides template
%
%- algebraic expressions
%
%- CPU
%\chapter*{ToDo}
%https://www.crcpress.com/A-Functional-Start-to-Computing-with-Python/Herman/9781466504554
\chapter*{Preface}
%
This edition of this evolving book has changed its name from ``Thinking Computationally'' to ``Thinking Algebraically''.
This reflects the coming into focus of why our approach to programming works,
and what we consider to be most important: giving people tools which (1) connect computing to the mathematics curriculum thereby giving children a better chance of succeeding in Algebra and opening up educational pathways, (2) making learning easier by building in knowledge gained since the 1970s, and (3) starting budding programmers off on a path will lead to high quality software at a time when careless, ignorant and unethical software developers are too often in the headlines.
Why have we abandoned the more common ``computational thinking''?
Mostly because it means too many things to different people, including well-intentioned claims which have not been backed up by evidence.
If you already know something about old-fashioned ``real-world'' programming,
welcome to the future!
Please send comments and bug-fixes to \verb|anandc@mcmaster.ca|.
\chapter{Tower of Hanoi}
We start with a seemingly simple children's puzzle, but whose solution involves some really powerful aspects of Algebraic Thinking.
In the Tower of Hanoi, your task is to move a tower made by stacking blocks of diminishing size, one on top of another. You can move one block at a time to one of three bases. At no time can a larger block rest on a smaller block. All the blocks have different sizes.
Assuming you are seeing this problem for the first time, the first question is, what questions should you ask yourself? For which sizes of tower can we solve the problem? How many moves are required to move the tower with a given number of blocks.
Take some time to think about the problem, and solve it if you can. If your solution is good, you should have no trouble explaining the solution to a friend.
How did you explain your solution to a friend? Did you use notation you have used before in algebra or geometry? Did you make up your own symbolic language? Could you explain your solution entirely in English?
If your math teachers have done a good job, you started by writing down what you know about the problem, and maybe even assigning variable names. Here's what I came up with:
\begin{verbatim}
n = number of blocks
{A,B,C} = set of places
{1,2,...n} = the blocks
\end{verbatim}
A surprising feature of this problem, which reflects a general trend in algebraic thinking, is that a seemingly more difficult problem has a simpler solution. In this case, figuring out how many moves it will take to move a tower of size $n$. Here is where using algebra, and the Divide \& Conquer principle makes the difference between impossibly convoluted and incredibly simple. Let $m_n$ be the number of moves required to move a tower of size $n$ from one place to another. That gives us simple notation.
The DnC principle appeals to a particular kind of teamwork. It asks us to assume we have friends who will share their solution to a simpler problem so that we can build on that. In this case, if we are asked to move a tower of size $n$, we can assume that friends have already figured out how to move a tower of size $1$ through $n-1$. The key is the $n-1$ solution.
Take a few minutes and try to describe a solution to the tower $n$ problem, assuming that you can call on friends to move a tower of size $n-1$.
Well, if friends will move a tower of size $n-1$, they will move the top part of your tower, which is itself a tower of size $n-1$, leaving you to move one block, the one on the bottom, which we will call the $n$th block. So if you need to move the tower from $A$ to $B$, your job is to move the $n$th block from $A$ to $B$. To be able to do your job, you need your friends to move the upper $n-1$ blocks from $A$ to $C$ to get them out of the way. Then you can move your block, after which your friends can move the $n-1$ blocks from $C$ to $B$. So the number of steps will be
$$
m_n = m_{n-1} + 1 + m_{n-1}
$$
Let's apply this formula to a specific case:
$$
\begin{aligned}
m_3 & = & m_2 + 1 + m_2 \\
& = & (m_1 + 1 + m_1) + 1 + (m_1 + 1 + m_1) \\
& = & (1 + 1 + 1) + 1 + (1 + 1 + 1) \\
& = & 7
\end{aligned}
$$
Now to get 7, we have used the hopefully obvious fact that we can move a tower with 1 block in 1 move. But there are no obvious facts for computers! If we had asked a computer to use the definition of $m_n$ in terms of $m_{n-1}$ it would have continued
{\small
$$
\begin{aligned}
m_3 & = & m_2 + 1 + m_2 \\
& = & (m_1 + 1 + m_1) + 1 + (m_1 + 1 + m_1) \\
& = & ((m_0 + 1 + m_0) + 1 + (m_0 + 1 + m_0)) + 1 + ((m_0 + 1 + m_0) + 1 + (m_0 + 1 + m_0)) \\
& = & (((m_{-1} + 1 + m_{-1}) + (m_{-1} + 1 + m_{-1})) + 1 + ((m_{-1} + 1 + m_{-1}) + (m_{-1} + 1 + m_{-1})) ) \\
& & + 1 + (((m_{-1} + 1 + m_{-1}) + (m_{-1} + 1 + m_{-1})) + 1 + ((m_{-1} + 1 + m_{-1}) + (m_{-1} + 1 + m_{-1})) ) \\
\end{aligned}
$$
}
and it would have continued to continue until the end of time or it ran out of memory to store the nonsense answer or some physical component failed.
Here is another good lesson about algebraic thinking. No matter what crazy thing a computer does, people have to take the blame, because people are doing the thinking, coming up with a set of rules and the computer faithfully carries them out. Until we figure out rules for common sense, computers will not have it, and while that may come sooner than many expect, you can bet it won't come before your next assignment is due---so you figure out the rules.
Philosophical discussions are great, but we still have a problem to solve! How can we do it? We need to put in the rule that a person with common sense would have inserted, that
$$
m_1 = 1
$$
So we could express our procedure as follows:
Given an $m_n$ to calculate, use repeated substitutions to reduce $m_n$ to a number, where we replace
$$
m_1 \text{ with } 1
$$
and for any values of n bigger than 1, we replace
$$
m_n \text{ with } m_{n-1} + 1 + m_{n-1}.
$$
There isn't really any point in writing all of this out, since a person would probably figure that out, but it happens to be very close to how we would use ELM to tell a computer the same thing.
\begin{code}
m n = case n of
1 -> 1
otherwise -> m (n-1) + 1 + m (n-1)
\end{code}
Note a few differences between standard algebraic notation and ELM. Instead of using subscripts to differentiate different values $m_1, m_2, ...$, we use a function \elm{m} depending on an input \elm{n}. For now, this is just a difference of notation, but functions have the potential to be more general. The next difference is that we capture all of the substitution rules together by considering all the different cases, using a \elm{case} statement. This takes up a bit more space on the page in some cases, but it is much clearer if all the rules are together, and the fact that there are multiple rules is signaled by \elm{case} and \elm{of}. The case statement always works the same way: The \elm{case} and \elm{of} bracket an expression whose value determines the case. In this case, the variable \elm{n}. On the following lines, values line up on the left, separated by \elm{->} (arrows) to the expression used to calculate the function value on the right. There is one special value, \elm{otherwise}, which catches all the values which do not match any of the other cases. Finally, unlike in algrebra, multiplication requires a symbol, \elm{*}, and ELM will not accept a definition like \elm{(x+a)(x+b)} in which writing expressions next to each other indicates multiplication, even though this is common in algebra. One good reason is that ELM allows variable names to be words, rather than single symbols.
You can try this definition for yourself, by typing this text into ***need url for box which captures function definition and tabulates some answers***
*** put in table here ***
At this point we have pointed out the differences, but there are more similarities than differences. For example, parentheses change the order of operations (which you probably didn't even think about), the operations + and - work as you would expect, and we have variables. We will talk more about variables, but for now, we'll rely on your understanding of variables from algebra.
One big difference between how we will use ELM and how you have previously used math, is that we just defined our own function \elm{m} on the first day. Whereas you probably used algebra to solve word problems for years before you learned about a function, maybe it was $\sin(\theta)$ or $\sqrt{x}$, and if you found the concept daunting, then you are not alone. The funny thing is that you have been using functions most of your life! Because $+$ is a function. It takes two numbers and gives you back their sum. In fact, ELM treats functions like \elm{+} like any other function, and you can even create your own functions written with a symbol or symbols between two input variables.
If you now feel silly for having struggled with the idea of a function, you are not alone, but in fact, there is more we can say about functions besides the fact that they have inputs and outputs, which will make things even clearer. But first we need to talk about the inputs and outputs, ie the values. And before that, we better finish our Tower of Hanoi example!
To solve the full problem, we will again use the DnC strategy, so let's spell out the strategy in more detail: We need to identify three steps:
\begin{itemize}
\item[\textbf{Divide:}] Within the original problem, identify smaller subproblems of the same type, unless it is small enough to solve immediately.
\item[\textbf{Conquer:}] Solve the subproblems using the same strategy.
\item[\textbf{Combine:}] Combine the solutions to the subproblems into a solution to the original problem
\end{itemize}
Sounds simple, but pay close attention to the requirement that the subproblems be of the same type and not subdivide infinitely. In our first example, the problem was to count the number of moves required to move a tower of size $n$. All of the problems involve moving a tower, only the size changes, and the towers are readily ranked by size.
Here's an example which fails: Mow a field by dividing it into two equal pieces and getting two friends to each mow half. When they are finished, the field is mowed. The problem: mow a piece of a field is always the same problem, and if your friends are as lazy as you, they will follow your lead and get two friends to mow halves of their halves. The problem is that there is no smallest size of field, so nobody would ever get around to doing any mowing. If we slightly change the problem, and start with a field of 32 hectares, and in the divide step we specify that when the patch to be mowed is 1 hectare, the unlucky friend of a friend will have to go buy a goat and supervise it to insure it munches evenly, then the Divide and Conquer strategy would work.
Here's another way it could fail: You sneak into the kitchen and steal a gingerbread person, but after escaping detection for a day, you start to worry about potential incarceration, and want to dispose of the body before any detectives come snooping. So you get some friends and break off the arms, legs and head, and give each friend a piece of anatomy to disappear. This time you will successfully disappear the evidence, but not using Divide and Conquer, because the subproblems (arms, legs, head, torso) are not the same as the whole person. You cannot break a leg off an arm, nor an arm off a head. So what we have is a strategy which disposes of one body, but it won't hide criminality at a large scale, involving, say, boxes of gingerbread people.
Back to the Tower of size $n$:
\begin{itemize}
\item[\textbf{Divide:}]
The top $n-1$ blocks are a tower in their own right, but smaller by one. A tower with 1 block cannot be divided, but it can be moved in one step.
\item[\textbf{Conquer:}]
Calculate the number of steps to move the tower of size $n-1$, call it $m_{n-1}$.
\item[\textbf{Combine:}]
To move the tower of size $n$, we need to move the smaller tower, move the bottom and move the smaller tower again, so we need $m_{n-1} + 1 + m_{n-1}$ steps.
\end{itemize}
What about moving the tower? You may have devised your own notation for moves, but some notation is required to avoid writing torturously long sentences in English.
Move Tower of size $n$ from $x$ to $y$ using additional place $z$.
\begin{itemize}
\item[\textbf{Divide:}] If the tower has size 1, move that piece from $x$ to $y$, which we will write as $(x,y)$, otherwise the top $n-1$ blocks are a smaller tower.
\item[\textbf{Conquer:}] Apply this procedure to produce a sequence of steps for moving the top tower from $x$ to $z$ using $y$. Call that sequence $s(x,z,y)$, and apply it again to find a sequence $s(z,y,x)$ to move a tower of size $n-1$ from $z$ to $y$ using $x$.
\item[\textbf{Combine:}] Join together the two sequences with one additional move: $s(X,Z,Y)$ followed by $(x,y)$ followed by $s(z,y,x)$.
\end{itemize}
To write this in ELM, we need to define our set of places, which is a distinct type of thing, apart from numbers, letters, words, buffalos, and every other thing we need in our program. We define a new type of thing like this:
\begin{code}
type Place = A | B | C
\end{code}
The type is obvious. Giving the new type of thing a name must use a capital letter, hence Place and not place, and the things of that type must also start with capital letters, and are separated by vertical bars.
For two things together, we can use a pair, ie (A,B), in the same way that we use (7,3) for Cartesian coordinates on the plane to group together the horizontal and vertical positions. We can use the pair to represent movements, but if we were already using pairs for other things, we should create a new type for movements to keep things straight. I'll show you how later.
Since we need many moves, we need a way of putting individual moves together in a finite sequence. ELM has a List type for this, with two functions we will need a lot:
[x] takes a thing x, and makes a list of length one with it.
xs ++ ys takes two lists of the same type of thing and joins them together into a bigger list.
With them, we can solve our tower problem:
\begin{code}
move n x y z = case n of
1 -> [(x,y)]
otherwise -> (move (n-1) x z y)++[(x,y)]++(move (n-1) z y x)
\end{code}
Woah! That was a long chapter, all to explain three lines of ELM! This is typical of the Divide and Conquer strategy. Once you figure out how to divide up your problem, it is usually easy to write the code, especially in a language like ELM. The tricky part is that the divide step is not always obvious. Let's make sure we remember the three parts: in the code above, underline the parts which correspond to conquering.
\begin{code}
move n x y z = case n of
1 -> [(x,y)]
otherwise -> (move (n-1) x z y)++[(x,y)]++(move (n-1) z y x)
\end{code}
Now underline the parts corresponding to combining:
\begin{code}
move n x y z = case n of
1 -> [(x,y)]
otherwise -> (move (n-1) x z y)++[(x,y)]++(move (n-1) z y x)
\end{code}
\chapter{\texttt{map} and Assembly Lines}
*** put fold here ***
We started this book with Divide \& Conquer because it captures so much of algebraic thinking.
(1) With the right scheme for division,
Divide \& Conquer enables the division of work
among a growing set of computers,
which is the key to scaling a solution up to
internet scale.
(2) With the right reformulation, any task a computer can perform, can be expressed as a Divide \& Conquer algorithm.
(3) Even though the individual tasks are simple, Divide \& Conquer procedures can accomplish complex tasks.
But every algorithm is not a Divide \& Conquer algorithm, and confusing different algorithm patterns is a good way to get stuck at the implementation step.
So let's look at some special cases of Divide \& Conquer which are easier to implement directly, starting with \texttt{map}.
When you can divide into \emph{smallest} problems in one step, rather than dividing into \emph{smaller} problems of the same type, you probably want to use map.
The \texttt{map} function applies to collections of data, but let's start with lists, which we have seen before.
\section{Map}
As a simple problem, let's say we have a list like\texttt{[1,2,3,4,5,6,7]} but we want to double each element to make a list of even numbers. The \texttt{map} function does this
\begin{code}
doubleElements list = map multByTwo list
multByTwo x = 2 * x
\end{code}
computes \textit{[2,4,6,8,10,12,14]}. Try it yourself on \texttt{http://elm-lang.org/try}.
Although they make nice, short examples, \texttt{map} is not restricted to numbers! Its type
\begin{code}
map : (a -> b) -> List a -> List b
\end{code}
says that map takes two arguments%
\footnote{Documentation for all of the core packages includes this type information.
See \texttt{http://package.elm-lang.org/packages/elm-lang/core/2.1.0/List}.
}.
The first one \texttt{(a -> b)} is a function from
type \texttt{a} to \texttt{b}.
In our example, both \texttt{a} and \texttt{b} are the type \texttt{Int}, but they could be anything.
They can be anything, but they determine the
types of the input and output lists (and vice versa).
The second argument is a list of type \texttt{a} (\texttt{: List a}) and the output a list of type
\texttt{b}.
Let's look at a practical real-world example.
First-year students, often living away from home for the first time,
need a lot of advice about things like what can safely go in the dishwasher.
So we made this handy data type and function.
\begin{code}
type KitchenStuff = Spoon | Plate | Ladle | Microwave | PizzaBox
dishwasherSafe x = case x of
Spoon -> True
Plate -> True
Ladle -> True
Microwave -> False
PizzaBox -> False
\end{code}
But with all the clubs, and the long walk across campus, they do not have time to apply the function to items individually, but with \texttt{map}, then don't have to!
\begin{code}
allSafe = map dishwasherSafe [Spoon,PizzaBox]
\end{code}
gives \texttt{[True,False]}.
So in this case, \texttt{map dishwasherSafe : List KitchenStuff -> List Bool}.
Using \texttt{map} looks powerful, and it is.
Instead of creating a recipe for programmers to implement,
the recipe is captured as function.
This is the common feature of functional programming languages like ELM which are driving their adoption in industry.
You may be aware that the most common languages in industry are object-oriented languages, and have heard of some like Java and C++.
A few decades ago, object-oriented languages offered software architects a way of organizing large pieces of software which, when done right,
offered much greater flexibility and extensibility than the previous procedural languages.
But over many years, a dark side to these languages emerged.
Projects often failed to meet their goals,
and often sinking more money into them hastened their collapse.
Managers were desperate to diagnose failing projects and successful architects wanted to explain why some of their projects succeeded.
The funny thing about software is that after writing a million lines of code,
you can easily be farther from your destination than when you started,
and to most outsiders, and even many insiders it is hard to tell when this is the case.
Well, a lot was learned by people who wrote a lot of software, and a practical cookbook for successful software design was written.
Called "Design Patterns: Elements of Reusable Object-Oriented Software" by Gamma, Johnson, Vlissides and Booch, it basically said, if you are going to implement a common pattern, do it in a standard way, and name it so developers coming after you know what you are aiming to do.
The standard patterns are called design patterns,
and the book sold over half a million copies,
and most people consider it to be wildly successful.
The weakness of design patterns
is that they still need to be implemented correctly,
and the languages at the time did very little to help programmers do this.
In contrast, design patterns implemented in functional languages can mostly be implemented as functions themselves,
and often in a couple of lines.
This is possible because functional languages treat functions the same as other variables,
which in Computer Science is the definition of being
``first class''%
\footnote{This is a weird cultural thing in Computer Science, that the default class is first class,
with the assumption that everyone deserves first class treatment, and anything less is implicitly treated as a defect in the system.
Compare this to airlines, where flying first class is ridiculously expensive and restricted to a privileged few.
}.
It is still possible to apply higher-order functions like \texttt{map} to the wrong inputs,
but many wrong inputs will be rejected as having incompatible types,
and the code is short enough to make the pattern and its inputs transparent.
In non-function languages, the pattern implementation is often spread over multiple modules making it difficult to check for consistency.
\medskip
Enough philosophy! We've seen how simple using \texttt{map} is.
But how is it a special case of Divide \& Conquer?
What are the subproblems? Here they are:
\begin{itemize}
\item[\textbf{Divide:}] Separate the first element from the rest of the input list. The rest of the list is still a list, so that's our subproblem.
\item[\textbf{Conquer:}] Apply this procedure to get a new list whose elements are the result of applying the function argument to the rest of the list.
\item[\textbf{Combine:}] Take the solution to the subproblem, which is a list, and prepend the result of applying the function argument to the first element.
\end{itemize}
When we implement this in ELM, we also need to take care of the base case, which here is when the list is empty, and so has no first element.
\begin{code}
map fun list = case list of
(x :: xs) -> (fun x) :: (map fun xs)
[] -> []
\end{code}
\subsection{Anonymous Functions}
%
On its own \texttt{map} is powerful,
but its usefulness is magnified by being able to
define simple functions right there in the first \texttt{map} argument, without having to give them a name, and use another line. Instead of defining
\texttt{multByTwo} above, we could instead use the
fact that we can use any infix operator like \texttt{+} or \texttt{*}, as a normal function by putting it in parentheses, like so
\begin{code}
multByTwo x = (*) 2 x
\end{code}
and to save a bit of typing could have used the definition
\begin{code}
multByTwo = (*) 2
\end{code}
which is called a partial application of the function \texttt{(*)}.
Now, I personally do not recommend using this style a lot, because you it is not visually obvious that \texttt{multByTwo} is a function taking one argument,
but inside a \texttt{map}
\begin{code}
evens n = map ((*) 2) [1..n]
\end{code}
cannot cause any confusion, and just saved us a line of code.
But it gets better, when we can compose these functions.
In math, functions can be composed with $\circ$, as in
$$
(f \circ g) (x) = f ( g (x) ),
$$
meaning that the function $f\circ g$ takes an input $x$, feeds it to $g$ and feeds that output to $f$ as an input.
In ELM, there are different composition operations
\begin{code}
f <| g x = f (g x) = g x |> f
\end{code}
depending on whether you want outputs to flow left or right into other functions as inputs.
You have probably seen this used to move shapes
\begin{code}
shape1 = filled red (circle 10) |> move (10,10)
\end{code}
and note that \texttt{move (10,10)} is a partially applied function, since \texttt{move} takes two inputs, but once we give it the first one (the shift vector),
we have a function with one input, which it gets from
the left of the \texttt{|>}.
So values move across the composition operators in the
direction of the pointy part.
So ELM notation is more flexible, in allowing both left-to-right and right-to-left compositions,
but this is not quite the same as the $\circ$ composition of mathematical functions.
The analogues of $\circ$ are \texttt{>>} and \texttt{<<}:
\begin{code}
(f << g) x = f (g x) = (g >> f) x
\end{code} % FIXME these are not ELM =, we should use something else
Which is actually less convenient than the preview composition operators.
In fact, we could insert those operators here as well
\begin{code}
(f << g) x = (f << g) <| x = x |> (f << g) = f (g x)
\end{code}
which is just confusing things,
so what is the point?
The point is that we can compose functions inside \texttt{map}.
So instead of defining a compound function to use in map
\begin{code}
sinePoint x = sin (2 * pi / 10 * x)
hillAndValley = map sinePoint [0..9]
\end{code}
we could use
\begin{code}
hillAndValley = map (sin << ((*) (2*pi/10))) [0..9]
\end{code}
which saves us a line.
Now you may wonder if this is really better,
since we have so many years of experience looking at expressions more like \texttt{sinePoint},
and you would have a point.
But first of all, this definitely does not apply
to most cases, e.g., if you need to move and rotate a bunch of shapes
\begin{code}
dancingShapes = map (move (10,10) << rotate (degrees 45)) standingShapes
\end{code}
and secondly, we have another way of putting the $x$ back into anonymous functions,
called a lambda expression
\begin{code}
hillAndValley = map (\ x -> sin(2*pi/10*x)) [0..9]
\end{code}
This looks a bit like a case in a \texttt{case}
expression,
and happily, it means the same thing, except
that there is only one case, and \texttt{x}
input which is mapped to \texttt{sin(2*pi/10*x)}.
They are called lambda expressions
because the Greek letter $\lambda$ was
used to represent the binding of a variable
to an expression to define a function,
almost exactly as in ELM,
except that we use \texttt{\symbol{92}} as a discount version of
$\lambda$, because typing $\lambda$ would be
too time consuming.
Since it was defined by Alonzo Church as a way of
defining computation,
and proving things about which functions can be computed (which, surprisingly, is not true of all functions),
it was shown to be equivalent to defining
computability in terms of a machine
(specifically a Turing machine, defined by Alan Turing),
and it has become a symbol of computer science.
The place where programming language enthusiasts meet is called \texttt{lambda-the-ultimate.org},
and a good place to find out what is cool in programming languages,
and all Computer Science superheros have $\lambda$s stitched into their stretchy suits.
\chapter{To be or not to be in the Basement}
%
Einstein used so-called thought-experiments,
in which he imagined an experiment to evaluate
the consequences of a theory.
His elevator experiment led to the formulation
of relativity, the most accurate theory we have of gravity.
We're going to do our own elevator experiment, and from it develop a theory for change and a tool for modelling change, called a state diagram.
With state diagrams, we can model changes to physical systems unlucky enough to be connected to our computers and changes to the graphical user interface through which we interact with our users.
You probably remember learning about state in science class.
And if you don't, just shake your head until the generated heat melts those frozen thoughts, and gets them flowing again.
The states of matter look like
\begin{center}
\includegraphics[width=0.4\textwidth]{gasLiquidSolid.png}
\end{center}
where each of the bubbles is a state,
and the arrows are called phase transitions.
In general, when we see a diagram like this in computer science, we call it a graph, the bubbles nodes, and the lines edges.
If the edges have arrows for direction,
it's a directed graph.
\section{State Diagrams}
A State Diagram is directed graph, with nodes we call states,
and edges we call transitions.
A game graph is very similar to a State Diagram, because there is always a place (state) we are in,
and for this to change, something has to happen.
The real state diagram corresponding to a game would also include any
items you are carrying, and in some games whether certain mosters are
dead or not.
This extra information significantly complicates the state diagram,
to the point where nobody could follow it.
Since keeping track of the state of mechanical devices, like elevators,
subway trains, etc., is rather important,
Computer Scientists have developed more complicated versions of state diagrams
called State Charts, which can include nesting (diagrams within diagrams),
and tools to create, visualize and verify charts.
Other tools can even create multiple programs to control the devices and
react to outside events, so that the diagrams themselves play the role of
the program, and the programmer gets to draw pictures instead of write code.
The only thing not normally allowed in a State Diagram is a bi-directional edge.
If the same transition can go in both directions, two arrows are drawn.
While we sometimes do not draw transitions which return to the same state
in order to simplify our diagrams,
it is unusual in state diagrams that each transition only effects one state,
as in the game graph.
State Diagrams, are a graphical representation of Finite State Machines,
which are the usual way of giving Computer Science an a mathematical foundation
allowing theoretical computer scientists to prove things like
that some programs will go on forever without stopping,
that one algorithm will take longer to solve a problem than another,
that a the solution produced by an algorithm is correct,
and that the running algorithm always has certain properties (importanly safety properties).
State is always present when software interacts with the real world.
\section{Implementing in ELM}
How do we model state and transitions in ELM?
$$\text{states} = \text{data}$$
$$\text{transitions} = \text{functions}$$
I know that is really complicated, but you just have to memorize it.
In ELM, we can always recognize data types by the \verb|type| keyword,
but forming lists and tuples is another way of creating data.
Be careful when using tuples that the meaning of the data is clear.
Although tuples are really convenient, you probably need a comment explaining
what the different components of the tuple represent,
because you do not have descriptive names the way you do with constructors.
\vspace{-12pt}
\begin{code}
module StateDiagram where
\end{code}
\subsection{Example: an Elevator}
\emph{State} captures everything we need to know about what is happening \emph{now},
so we know what can happen next, and what actions a user could request.
\begin{itemize}
\item doors, open and closed
\item be on a floor or in between floors
\item doing nothing, or going to a floor
\item call buttons can be pressed on floors, or in the elevator
\end{itemize}
\emph{Transitions} capture both user requests and actions and processes coming to a completion.
\begin{itemize}
\item elevator can arrive at a floor
\item doors can open
\item doors can close
\item people can press buttons
\item elevator arrives at place where button is lit, and button goes dark
\item door should close if no motion is detected
\end{itemize}
\medskip
Data recording the state of the elevator has multiple components.
Let's start small, with recording the state of one door:
\vspace{-12pt}
\begin{code}
type Door = Open | Closed
\end{code}
Two transitions (each function is represented by arrows labelled by function name).
\vspace{-12pt}
\begin{code}
openDoor Open = Open -- this is needed in ELM, sometimes omit in diagram
openDoor Closed = Open
closeDoor Open = Closed
closeDoor Closed = Closed
\end{code}
We can capture these two states and two transitions with a diagram
\begin{center}
\includegraphics[width=.5\textwidth]{openClose.pdf}
\end{center}
Note again that when things get complicated,
we often omit transition edges which come back to the same state.
\medskip
Going back to tracking state, we obviously need to know where the
elevator is.
There are many ways of doing this, and we came up with
different solutions, but decided to go with
recording the state as being at a floor, or going to a floor.
A more complicated elevator might record the exact position between
floors,
and if you are going to support smartphones apps which tell you
when your elevator will arrive,
you would need to keep track of the speed of the elevator
and the number of people getting on and off, ...
\vspace{-12pt}
\begin{code}
type Floor = Basement
| ToBasement
| Ground
| ToGround
| First
| ToFirst
\end{code}
The state of one button:
\vspace{-12pt}
\begin{code}
data Button = LitUp | Dark
\end{code}
Transitions corresponding to buttons being pressed
3 call buttons, these are user-initiated state transitions
Transition functions always have type \verb|State -> State|,
and we can give them all types together.
\vspace{-12pt}
\begin{code}
callToBasement, callToGround, callToFirst, arriveAtGround, arriveAtBasement, arriveAtFirst
: (Floor,(Button,Button,Button)) -> (Floor,(Button,Button,Button))
\end{code}
Some state transitions are initiated by the user, or by external events.
In this case, the user can call an elevator by pressing a button.
Elevators do not have many external events, but there probably some elevators
out there which detect earthquakes and come to a stop.
\vspace{-12pt}
\begin{code}
callToBasement state = case state of
(Basement, (bb,gb,fb)) -> (Basement, (Dark,Dark,Dark))
(ToBasement,(bb,gb,fb)) -> (ToBasement,(LitUp,Dark,Dark))
(Ground, (bb,gb,fb)) -> (ToBasement,(LitUp,Dark,Dark))
(First, (bb,gb,fb)) -> (ToBasement,(LitUp,Dark,Dark))
(ToGround, (bb,gb,fb)) -> (ToGround, (Dark,LitUp,Dark))
(ToFirst, (bb,gb,fb)) -> (ToFirst, (Dark,Dark,LitUp))
callToGround state = case state of
(Basement, (bb,gb,fb)) -> (ToGround, (Dark,LitUp,Dark))
(ToBasement,(bb,gb,fb)) -> (ToBasement,(LitUp,Dark,Dark))
(Ground, (bb,gb,fb)) -> (Ground, (Dark,Dark,Dark))
(First, (bb,gb,fb)) -> (ToGround, (Dark,LitUp,Dark))
(ToGround, (bb,gb,fb)) -> (ToGround, (Dark,LitUp,Dark))
(ToFirst, (bb,gb,fb)) -> (ToFirst, (Dark,Dark,LitUp))
\end{code}
We leave it as a homework problem to write the \verb|callToFirst| function.
There are also environment-initiated state transitions.
\vspace{-12pt}
\begin{code}
arriveAtGround state = case state of
(Basement, (bb,gb,fb)) -> (Ground, (Dark,Dark,Dark))
-- this should really cause an error, since we arrived somewhere we were not going
++" and got a signal that we arrived on the ground floor"
(ToBasement,(bb,gb,fb)) -> (ToBasement,(LitUp,Dark,Dark))
(Ground, (bb,gb,fb)) -> (Ground, (Dark,Dark,Dark))
(First, (bb,gb,fb)) -> error $ "oops, we think we are on the first floor,"
++" and got a signal that we arrived on the ground floor"
(ToGround, (bb,gb,fb)) -> (Ground, (Dark,Dark,Dark))
(ToFirst, (bb,gb,fb)) -> (ToFirst, (Dark,Dark,LitUp))
\end{code}
We leave it as a homework problem to write the
\verb|arriveAtBasement| and
\verb|arriveAtFirst| functions.
Our best hope of getting all of these cases right is
to \emph{start} with a state diagram,
or in this case, we can simplify things by drawing
separate diagrams for the position of the elevator:
\begin{center}
\includegraphics[width=0.75\textwidth]{elevator.pdf}
\end{center}
and the lighting of the buttons:
\begin{center}
\includegraphics[width=0.75\textwidth]{elevatorButtons.pdf}
\end{center}
But, in our defence, we were still learning about transitions when
we developed this example in class.
\medskip
\emph{Hey!} Why is the state of the door not integrated into the other state?
People are going to get pretty upset when they find out the door doesn't open!
To do this we would need to extend the state, by adding the door state to the
tuple, or creating a new set of constructors.
This is left as a homework problem.
\section{The StateDiagrams Module}
Let's return to basic science again, and the question that probably bugged you the most: who drew that masterpiece of a diagram?
ELM, of course!
And for the right price, you can draw your own neat diagrams, all you need is our \texttt{StateDiagrams} module which you import along with the graphics collage to draw it in,
\begin{code}
import StateDiagrams exposing (..)
import Graphics.Collage exposing (..)
\end{code}
then define a type with your favourite states,
\begin{code}
type States = Solid | Liquid | Gas
\end{code}
define the transitions via functions
(which in this case we define to leave all states alone, other than the ones they change),
\begin{code}
melt x = case x of
Solid -> Liquid
other -> other
freeze x = case x of
Liquid -> Solid
other -> other
sublimate x = case x of
Solid -> Gas
other -> other
deposit x = case x of
Gas -> Solid
other -> other
condense x = case x of
Gas -> Liquid
other -> other
vaporize x = case x of
Liquid -> Gas
other -> other
\end{code}
and use the \texttt{viewStateDiagram}
function to draw it:
\begin{code}
main = collage 400 400
[viewStateDiagram [(Solid,(-50,-50))
,(Gas,(-50,50))
,(Liquid,(40,0))
]
[(melt,"melt",[(Solid,(20,-40))])
,(freeze,"freeze",[(Liquid,(0,-20))])
,(vaporize,"vaporize",[(Liquid,(20,40))])
,(condense,"condense",[(Gas,(-5,25))])
,(deposit,"deposit",[(Gas,(-85,7))])
,(sublimate,"sublimate",[(Solid,(-45,-7))])
]
Nothing
Nothing
]
\end{code}
This is the hard part, because in addition to
a list of the states you want drawn, you need to figure out Cartesian coordinates to pin them to,
and in addition to the transitions,
you need to decide from which initial states to draw
them and where to pin the labels.
Note that while the states are data types,
and ELM just knows how to show them as strings of characters,
transitions are functions which ELM cannot show,
so we need to provide a string to display.
\chapter{Fold, Signals and Functional Reactive Programming}
%
I know you are impatient to learn about creating interactive programs,
and we do have the key concept behind us---State---but we need a bit
more practical knowledge to put this knowledge to use in ELM.
Let's take a look at a simple game, Peekaboo.
We need to import a couple of familiar modules,
and new modules for getting the position of the
mouse an something called \texttt{Signal}.
\begin{code}
module Peekaboo where
import Graphics.Element exposing (..)
import Graphics.Collage exposing (..)
import Color exposing (..)
import Mouse
import Signal
\end{code}
Next, we have a new type for the main function, \texttt{Signal Element},
and we use a new function \texttt{Signal.map},
which looks a lot like \texttt{List.map}, which we have seen before.
\begin{code}
main : Signal Element
main =
Signal.map draw Mouse.position
\end{code}
The type \texttt{Signal Element} uses a type constructor \texttt{Signal}
analogous to \texttt{List}, which took one type and defined the type of
a list of elements of that type.
A \texttt{Signal} is a lot like \texttt{List}.
Both are container types, but even more, they both define lists,
but whereas \texttt{List a} defines a list of values put together at one time,
\texttt{Signal a} defines a list of values which are generated one at a time.
Just as Einstein's thinking about elevators led to the unification of space and time in one mathematical object,
if we had a bank of elevators distributed in space,
we would need a type \texttt{List ElevatorState} to model their combined state,
and were we to model the state of an elevator as it changes in time, we would need a type
\texttt{Signal ElevatorState}, and for a whole bank of elevators changing in time,
\texttt{Signal (List ElevatorState)}.
Elevator space-time!
While we are waiting for Evan to be awarded a Nobel prize for inventing \texttt{Signal}s, let's look at the rest of the program.
We see a \texttt{Signal.map} which works analogously to \texttt{List.map}
by mapping a function over the values which arrive in the signal over time.
In this case, the incoming signals come from \texttt{Mouse.position},
which unsurprisingly is a list of positions of the mouse as it hovers over
our window,
and \texttt{draw} transforms them (into \texttt{Element}s, as specified by the type of \texttt{main}).
The draw function
\begin{code}
draw pos =
collage 400 400 [filled blue (circle 20) |> move (mouseToCollage pos)
]
\end{code}
moves a single blue circle to the position of the mouse, and puts it in a collage.
There is just one tiny wrinkle in the otherwise well-pressed code:
the coordinates in the \texttt{Mouse.position} signal and the coordinates
within the collage are incompatible, one is integral, and the other uses
floating-point fractions; one is centered on the mid-point of the collage, and
the other starts at the top-left corner of our window; one goes up, the other down.
The function \texttt{mouseToCollage} irons out this wrinkle, as best we can.
\begin{code}
mouseToCollage (x,y) = (toFloat x - 200 ,200 - toFloat y)
\end{code}
Now, if you're 8 months old, Peekaboo is a very satisfying game,
but if your guardian reads this chapter to you in a another year,
you will be somewhat less impressed,
because there is no development in this game,
every moment is just like the one before.
The problem lies in \texttt{Signal.map},
which applies \texttt{draw} to each mouse position.
This property of \texttt{map} is extremely useful for
three reasons: one, it means that we only need to understand the
evaluation of our function on one input at a time;
two, when applied to lists and other collections in space, since each application is independent, we can use multiple processors to operate on different inputs to speed things up, which process is called parallelization;
and three,
when applied to ``time'' to create an animation, we can very easily modify time by scrubbing, fast-forwarding, reversing, etc., and get the functionality of a movie editor.
You may have already thought of other things we can do with programs structured using \texttt{map}, but we need to get back to making our game more interesting.
What we need is something like \texttt{map}, but which ``remembers'' the past.
One option would be to dust off the chapter about Divide \& Conquer,
and create a new version of map, but it is easier to use functions which already exist.
The new functions are called ``fold'',
and the ``s'' in functions is not a typo,
because unlike map, there are different ways of implementing fold.
If you are a baker of interesting cakes,
then you are already familiar with \emph{fold}ing ingredients into your cakes.
If you sprinkle some hazelnuts into your batter and fold them in,
your final cake will have hazelnuts.
If you then fold some raisons, apricots, figs and finally pistacios into your cake, they are will all contribute to the tastiness of your final cake.
The fold operation takes two inputs, the cake batter and the new ingredient, and has one output, the cake batter (now containing the new ingredient).
\begin{code}
foldIn : Ingredient -> Batter -> Batter
\end{code}
The process of folding in all of the ingredients then has this type:
\begin{code}
fold : (Ingredient -> Batter -> Batter) -> Batter -> List Ingredient -> Batter
\end{code}
This is how your grandmother's cookbook would have explained it,
had your grandmother been Ada Lovelace.
We can also explain it in ELM.
For \texttt{List}, we have two folds, one which goes through the ingredients from left to right, and one from right to left.
\begin{code}
foldl f init xs = case xs of
[] -> init
y :: ys -> foldl f (f y :: init) ys
\end{code}
and
\begin{code}
foldr f init xs = foldl f init <| List.reverse ys
\end{code}
Let's look at a picture of map versus fold applied to lists
\[ \fbox{ \xygraph{
!{<0cm,0cm>;<1cm,0cm>:<0cm,1cm>::}
!{(1,6)}{\text{map}\ f}
!{(0,4)}*+[F.]{a_0}="a0"
!{(0,3)}*+[F.]{a_1}="a1"
!{(0,2)}*+[F.]{a_2}="a2"
!{(0,1)}{\vdots}="adots"
!{(0,0)}*+[F.]{a_{n-1}}="an1"
!{(0,-1)}*+[F.]{a_n}="an"
!{(2,4)}*+[F=]{b_0}="b0"
!{(2,3)}*+[F=]{b_1}="b1"
!{(2,2)}*+[F=]{b_2}="b2"
!{(2,1)}{\vdots}="bdots"
!{(2,0)}*+[F=]{b_{n-1}}="bn1"
!{(2,-1)}*+[F=]{b_n}="bn"
"a0":"b0"^*{f}
"a1":"b1"^*{f}
"a2":"b2"^*{f}
"an1":"bn1"^*{f}
"an":"bn"^*{f}
}}\quad
\fbox{ \xygraph{
!{<0cm,0cm>;<1cm,0cm>:<0cm,1cm>::}
!{(1,6)}{\text{fold}\ f\ b_{\text{init}}}
!{(0,4)}*+[F.]{a_0}="a0"
!{(0,3)}*+[F.]{a_1}="a1"
!{(0,2)}*+[F.]{a_2}="a2"
!{(0,1)}{\vdots}="adots"
!{(0,0)}*+[F.]{a_{n-1}}="an1"
!{(0,-1)}*+[F.]{a_n}="an"
!{(2,5)}*+[F.]{b_{\text{init}}}="binit"
!{(2,4)}{b_0}="b0"
!{(2,3)}{b_1}="b1"
!{(2,2)}{b_2}="b2"
!{(2,1)}{\vdots}="bdots"
!{(2,0)}*{b_{n-1}}="bn1"
!{(2,-1)}*+[F=]{b_n}="bn"
"a0":@/^{0.4cm}/"b0"^>>*{g}
"a1":@/^{0.4cm}/"b1"^>>*{g}
"a2":@/^{0.4cm}/"b2"^>>*{g}
"an1":@/^{0.4cm}/"bn1"^>>*{g}
"an":@/^{0.4cm}/"bn"^>>*{g}
"binit":@/^{-0.2cm}/"b0"
"b0":@/^{-0.2cm}/"b1"
"b1":@/^{-0.2cm}/"b2"
"b2":@/^{-0.2cm}/"bdots"
"bdots":@/^{-0.2cm}/"bn1"
"bn1":@/^{-0.2cm}/"bn"
}}
\quad
\fbox{ \xygraph{
!{<0cm,0cm>;<1cm,0cm>:<0cm,1cm>::}
!{(0,5)}*+[F.]{\text{inputs}}
!{(0,4)}*+[F=]{\text{outputs}}
}}
\]
where we see that both take a list of inputs $a_0,a_1,\dots,a_n$
and both compute a list $b_0,b_1,\dots,b_n$,
but whereas \texttt{map} outputs all of the $b$s,
\texttt{fold} only outputs the final value,
and \texttt{fold} needs an initial value which it updates with every new input.
Both map and fold are implemented for many container types in ELM,
including \texttt{Array}, \texttt{Dict}, \texttt{List}, \texttt{Set} and \texttt{String},
and works in an analogous way.
For \texttt{Signal}s, \texttt{map} works exactly as you would expect,
but fold runs into a problem---namely, most signals, like the position
of the mouse do not have a known number of elements,
and for many programs might as well be thought of as infinite,
since they will go on until someone closes the web page where they are running.
Getting a value from a folded signal only as the program terminates is not very helpful!
So fold for \texttt{Signal}s \emph{does} output all of the $b$ values in a their own \texttt{Signal}.
\begin{code}
foldp : (input -> state -> state) -> state -> Signal input -> Signal state
\end{code}
Where the ``p'' comes from ``past'',
because at any point in time,
the current state depends on the past states and past inputs.
This is exactly what we need to give our game a sense of progress!
Before we go on,
we should note that it is somewhat unusual to use ``fold'' for a function with a different type signature (i.e., multiple outputs),
since it makes the fold family less consistent.
Consistency makes things easy to remember,
which gives you time to think of other things.
And I do not know of another languages with a special fold, like this.
For comparison, look at the Haskell function \emph{mapAccumL}.
\medskip
Now we'll put it together into a game, using the arrow keys on the keyboard.
The first step is to use our newly discovered fold function on events
\begin{code}
main = Signal.foldp update initState events
|> Signal.map view
\end{code}
which will fold a stream of events \texttt{events} into succeeding states
starting with \texttt{initState} using a combining function \texttt{update}.