-
Notifications
You must be signed in to change notification settings - Fork 68
Expand file tree
/
Copy pathfor-a-few-monads-more.html
More file actions
1956 lines (1932 loc) · 109 KB
/
for-a-few-monads-more.html
File metadata and controls
1956 lines (1932 loc) · 109 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN"
"https://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>For a Few Monads More - Learn You a Haskell for Great Good!</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<base href="">
<style type="text/css">
@import url('reset.css');
@import url('style.css');
</style>
<link rel="shortcut icon" href="assets/images/favicon.png" type="image/png">
<link rel="prev" href="a-fistful-of-monads.html">
<link rel="next" href="zippers.html">
<link type="text/css" rel="stylesheet" href="sh/Styles/SyntaxHighlighter.css">
<link href="rss.php" rel="alternate" type="application/rss+xml" title="Learn You a Haskell for Great Good! feed">
</head>
<body class="introcontent">
<div class="bgwrapper">
<div id="content">
<div class="footdiv" style="margin-bottom:25px;">
<ul>
<li style="text-align:left">
<a href="a-fistful-of-monads.html" class="prevlink">A Fistful of Monads</a>
</li>
<li style="text-align:center">
<a href="chapters.html">Table of contents</a>
</li>
<li style="text-align:right">
<a href="zippers.html" class="nxtlink">Zippers</a>
</li>
</ul>
</div>
<h1 id="for-a-few-monads-more">For a Few Monads More</h1>
<p><img src="assets/images/for-a-few-monads-more/clint.png"
class="right" width="189" height="400"
alt="there are two kinds of people in the world, my friend. those who learn them a haskell and those who have the job of coding java" /></p>
<p>We’ve seen how monads can be used to take values with contexts and
apply them to functions and how using <code>>>=</code> or
<code>do</code> notation allows us to focus on the values themselves
while the context gets handled for us.</p>
<p>We’ve met the <code>Maybe</code> monad and seen how it adds a context
of possible failure to values. We’ve learned about the list monad and
saw how it lets us easily introduce non-determinism into our programs.
We’ve also learned how to work in the <code>IO</code> monad, even before
we knew what a monad was!</p>
<p>In this chapter, we’re going to learn about a few other monads. We’ll
see how they can make our programs clearer by letting us treat all sorts
of values as monadic ones. Exploring a few monads more will also
solidify our intuition for monads.</p>
<p>The monads that we’ll be exploring are all part of the
<code>mtl</code> package. A Haskell package is a collection of modules.
The <code>mtl</code> package comes with the Haskell Platform, so you
probably already have it. To check if you do, type
<code>ghc-pkg list</code> in the command-line. This will show which
Haskell packages you have installed and one of them should be
<code>mtl</code>, followed by a version number.</p>
<h2 id="writer">Writer? I hardly know her!</h2>
<p>We’ve loaded our gun with the <code>Maybe</code> monad, the list
monad and the <code>IO</code> monad. Now let’s put the
<code>Writer</code> monad in the chamber and see what happens when we
fire it!</p>
<p>Whereas <code>Maybe</code> is for values with an added context of
failure and the list is for non-deterministic values, the
<code>Writer</code> monad is for values that have another value attached
that acts as a sort of log value. <code>Writer</code> allows us to do
computations while making sure that all the log values are combined into
one log value that then gets attached to the result.</p>
<p>For instance, we might want to equip our values with strings that
explain what’s going on, probably for debugging purposes. Consider a
function that takes a number of bandits in a gang and tells us if that’s
a big gang or not. That’s a very simple function:</p>
<pre class="haskell:hs"><code>isBigGang :: Int -> Bool
isBigGang x = x > 9</code></pre>
<p>Now, what if instead of just giving us a <code>True</code> or
<code>False</code> value, we want it to also return a log string that
says what it did? Well, we just make that string and return it along
side our <code>Bool</code>:</p>
<pre class="haskell:hs"><code>isBigGang :: Int -> (Bool, String)
isBigGang x = (x > 9, "Compared gang size to 9.")</code></pre>
<p>So now instead of just returning a <code>Bool</code>, we return a
tuple where the first component of the tuple is the actual value and the
second component is the string that accompanies that value. There’s some
added context to our value now. Let’s give this a go:</p>
<pre class="haskell:hs"><code>ghci> isBigGang 3
(False,"Compared gang size to 9.")
ghci> isBigGang 30
(True,"Compared gang size to 9.")</code></pre>
<p><img src="assets/images/for-a-few-monads-more/tuco.png" class="left"
width="196" height="280"
alt="when you have to poop, poop, don’t talk" /></p>
<p>So far so good. <code>isBigGang</code> takes a normal value and
returns a value with a context. As we’ve just seen, feeding it a normal
value is not a problem. Now what if we already have a value that has a
log string attached to it, such as <code>(3, "Smallish gang.")</code>,
and we want to feed it to <code>isBigGang</code>? It seems like once
again, we’re faced with this question: if we have a function that takes
a normal value and returns a value with a context, how do we take a
value with a context and feed it to the function?</p>
<p>When we were exploring the <code>Maybe</code> monad, we made a
function <code>applyMaybe</code>, which took a <code>Maybe a</code>
value and a function of type <code>a -> Maybe b</code> and fed that
<code>Maybe a</code> value into the function, even though the function
takes a normal <code>a</code> instead of a <code>Maybe a</code>. It did
this by minding the context that comes with <code>Maybe a</code> values,
which is that they are values with possible failure. But inside the
<code>a -> Maybe b</code> function, we were able to treat that value
as just a normal value, because <code>applyMaybe</code> (which later
became <code>>>=</code>) took care of checking if it was a
<code>Nothing</code> or a <code>Just</code> value.</p>
<p>In the same vein, let’s make a function that takes a value with an
attached log, that is, an <code>(a,String)</code> value and a function
of type <code>a -> (b,String)</code> and feeds that value into the
function. We’ll call it <code>applyLog</code>. But because an
<code>(a,String)</code> value doesn’t carry with it a context of
possible failure, but rather a context of an additional log value,
<code>applyLog</code> is going to make sure that the log of the original
value isn’t lost, but is joined together with the log of the value that
results from the function. Here’s the implementation of
<code>applyLog</code>:</p>
<pre class="haskell:hs"><code>applyLog :: (a,String) -> (a -> (b,String)) -> (b,String)
applyLog (x,log) f = let (y,newLog) = f x in (y,log ++ newLog)</code></pre>
<p>When we have a value with a context and we want to feed it to a
function, we usually try to separate the actual value from the context
and then try to apply the function to the value and then see that the
context is taken care of. In the <code>Maybe</code> monad, we checked if
the value was a <code>Just x</code> and if it was, we took that
<code>x</code> and applied the function to it. In this case, it’s very
easy to find the actual value, because we’re dealing with a pair where
one component is the value and the other a log. So first we just take
the value, which is <code>x</code> and we apply the function
<code>f</code> to it. We get a pair of <code>(y,newLog)</code>, where
<code>y</code> is the new result and <code>newLog</code> the new log.
But if we returned that as the result, the old log value wouldn’t be
included in the result, so we return a pair of
<code>(y,log ++ newLog)</code>. We use <code>++</code> to append the new
log to the old one.</p>
<p>Here’s <code>applyLog</code> in action:</p>
<pre class="haskell:hs"><code>ghci> (3, "Smallish gang.") `applyLog` isBigGang
(False,"Smallish gang.Compared gang size to 9")
ghci> (30, "A freaking platoon.") `applyLog` isBigGang
(True,"A freaking platoon.Compared gang size to 9")</code></pre>
<p>The results are similar to before, only now the number of people in
the gang had its accompanying log and it got included in the result log.
Here are a few more examples of using <code>applyLog</code>:</p>
<pre class="haskell:hs"><code>ghci> ("Tobin","Got outlaw name.") `applyLog` (\x -> (length x, "Applied length."))
(5,"Got outlaw name.Applied length.")
ghci> ("Bathcat","Got outlaw name.") `applyLog` (\x -> (length x, "Applied length"))
(7,"Got outlaw name.Applied length")</code></pre>
<p>See how inside the lambda, <code>x</code> is just a normal string and
not a tuple and how <code>applyLog</code> takes care of appending the
logs.</p>
<h3 id="monoids-to-the-rescue">Monoids to the rescue</h3>
<div class="hintbox">
<p>Be sure you know what <a
href="functors-applicative-functors-and-monoids.html#monoids">monoids</a>
are at this point! Cheers.</p>
</div>
<p>Right now, <code>applyLog</code> takes values of type
<code>(a,String)</code>, but is there a reason that the log has to be a
<code>String</code>? It uses <code>++</code> to append the logs, so
wouldn’t this work on any kind of list, not just a list of characters?
Sure it would. We can go ahead and change its type to this:</p>
<pre class="haskell:hs"><code>applyLog :: (a,[c]) -> (a -> (b,[c])) -> (b,[c])</code></pre>
<p>Now, the log is a list. The type of values contained in the list has
to be the same for the original list as well as for the list that the
function returns, otherwise we wouldn’t be able to use <code>++</code>
to stick them together.</p>
<p>Would this work for bytestrings? There’s no reason it shouldn’t.
However, the type we have now only works for lists. It seems like we’d
have to make a separate <code>applyLog</code> for bytestrings. But wait!
Both lists and bytestrings are monoids. As such, they are both instances
of the <code>Monoid</code> type class, which means that they implement
the <code>mappend</code> function. And for both lists and bytestrings,
<code>mappend</code> is for appending. Watch:</p>
<pre class="haskell:hs"><code>ghci> [1,2,3] `mappend` [4,5,6]
[1,2,3,4,5,6]
ghci> B.pack [99,104,105] `mappend` B.pack [104,117,97,104,117,97]
Chunk "chi" (Chunk "huahua" Empty)</code></pre>
<p>Cool! Now our <code>applyLog</code> can work for any monoid. We have
to change the type to reflect this, as well as the implementation,
because we have to change <code>++</code> to <code>mappend</code>:</p>
<pre class="haskell:hs"><code>applyLog :: (Monoid m) => (a,m) -> (a -> (b,m)) -> (b,m)
applyLog (x,log) f = let (y,newLog) = f x in (y,log `mappend` newLog)</code></pre>
<p>Because the accompanying value can now be any monoid value, we no
longer have to think of the tuple as a value and a log, but now we can
think of it as a value with an accompanying monoid value. For instance,
we can have a tuple that has an item name and an item price as the
monoid value. We just use the <code>Sum</code> newtype to make sure that
the prices get added as we operate with the items. Here’s a function
that adds drink to some cowboy food:</p>
<pre class="haskell:hs"><code>import Data.Monoid
type Food = String
type Price = Sum Int
addDrink :: Food -> (Food,Price)
addDrink "beans" = ("milk", Sum 25)
addDrink "jerky" = ("whiskey", Sum 99)
addDrink _ = ("beer", Sum 30)</code></pre>
<p>We use strings to represent foods and an <code>Int</code> in a
<code>Sum</code> <code>newtype</code> wrapper to keep track of how many
cents something costs. Just a reminder, doing <code>mappend</code> with
<code>Sum</code> results in the wrapped values getting added
together:</p>
<pre class="haskell:hs"><code>ghci> Sum 3 `mappend` Sum 9
Sum {getSum = 12}</code></pre>
<p>The <code>addDrink</code> function is pretty simple. If we’re eating
beans, it returns <code>"milk"</code> along with <code>Sum 25</code>, so
25 cents wrapped in <code>Sum</code>. If we’re eating jerky we drink
whiskey and if we’re eating anything else we drink beer. Just normally
applying this function to a food wouldn’t be terribly interesting right
now, but using <code>applyLog</code> to feed a food that comes with a
price itself into this function is interesting:</p>
<pre class="haskell:hs"><code>ghci> ("beans", Sum 10) `applyLog` addDrink
("milk",Sum {getSum = 35})
ghci> ("jerky", Sum 25) `applyLog` addDrink
("whiskey",Sum {getSum = 124})
ghci> ("dogmeat", Sum 5) `applyLog` addDrink
("beer",Sum {getSum = 35})</code></pre>
<p>Milk costs <code>25</code> cents, but if we eat it with beans that
cost <code>10</code> cents, we’ll end up paying <code>35</code> cents.
Now it’s clear how the attached value doesn’t always have to be a log,
it can be any monoid value and how two such values are combined into one
depends on the monoid. When we were doing logs, they got appended, but
now, the numbers are being added up.</p>
<p>Because the value that <code>addDrink</code> returns is a tuple of
type <code>(Food,Price)</code>, we can feed that result to
<code>addDrink</code> again, so that it tells us what we should drink
along with our drink and how much that will cost us. Let’s give it a
shot:</p>
<pre class="haskell:hs"><code>ghci> ("dogmeat", Sum 5) `applyLog` addDrink `applyLog` addDrink
("beer",Sum {getSum = 65})</code></pre>
<p>Adding a drink to some dog meat results in a beer and an additional
<code>30</code> cents, so <code>("beer", Sum 35)</code>. And if we use
<code>applyLog</code> to feed that to <code>addDrink</code>, we get
another beer and the result is <code>("beer", Sum 65)</code>.</p>
<h3 id="the-writer-type">The Writer type</h3>
<p>Now that we’ve seen that a value with an attached monoid acts like a
monadic value, let’s examine the <code>Monad</code> instance for types
of such values. The <code>Control.Monad.Writer</code> module exports the
<code>Writer w a</code> type along with its <code>Monad</code> instance
and some useful functions for dealing with values of this type.</p>
<p>First, let’s examine the type itself. To attach a monoid to a value,
we just need to put them together in a tuple. The
<code>Writer w a</code> type is just a <code>newtype</code> wrapper for
this. Its definition is very simple:</p>
<pre class="haskell:hs"><code>newtype Writer w a = Writer { runWriter :: (a, w) }</code></pre>
<p>It’s wrapped in a <code>newtype</code> so that it can be made an
instance of <code>Monad</code> and that its type is separate from a
normal tuple. The <code>a</code> type parameter represents the type of
the value and the <code>w</code> type parameter the type of the attached
monoid value.</p>
<p>Its <code>Monad</code> instance is defined like so:</p>
<pre class="haskell:hs"><code>instance (Monoid w) => Monad (Writer w) where
return x = Writer (x, mempty)
(Writer (x,v)) >>= f = let (Writer (y, v')) = f x in Writer (y, v `mappend` v')</code></pre>
<p><img src="assets/images/for-a-few-monads-more/angeleyes.png"
class="right" width="383" height="248"
alt="when you have to poop, poop, don’t talk" /></p>
<p>First off, let’s examine <code>>>=</code>. Its implementation
is essentially the same as <code>applyLog</code>, only now that our
tuple is wrapped in the <code>Writer</code> <code>newtype</code>, we
have to unwrap it when pattern matching. We take the value
<code>x</code> and apply the function <code>f</code> to it. This gives
us a <code>Writer w a</code> value and we use a <code>let</code>
expression to pattern match on it. We present <code>y</code> as the new
result and use <code>mappend</code> to combine the old monoid value with
the new one. We pack that up with the result value in a tuple and then
wrap that with the <code>Writer</code> constructor so that our result is
a <code>Writer</code> value instead of just an unwrapped tuple.</p>
<p>So, what about <code>return</code>? It has to take a value and put it
in a default minimal context that still presents that value as the
result. So what would such a context be for <code>Writer</code> values?
If we want the accompanying monoid value to affect other monoid values
as little as possible, it makes sense to use <code>mempty</code>.
<code>mempty</code> is used to present identity monoid values, such as
<code>""</code> and <code>Sum 0</code> and empty bytestrings. Whenever
we use <code>mappend</code> between <code>mempty</code> and some other
monoid value, the result is that other monoid value. So if we use
<code>return</code> to make a <code>Writer</code> value and then use
<code>>>=</code> to feed that value to a function, the resulting
monoid value will be only what the function returns. Let’s use
<code>return</code> on the number <code>3</code> a bunch of times, only
we’ll pair it with a different monoid every time:</p>
<pre class="haskell:hs"><code>ghci> runWriter (return 3 :: Writer String Int)
(3,"")
ghci> runWriter (return 3 :: Writer (Sum Int) Int)
(3,Sum {getSum = 0})
ghci> runWriter (return 3 :: Writer (Product Int) Int)
(3,Product {getProduct = 1})</code></pre>
<p>Because <code>Writer</code> doesn’t have a <code>Show</code>
instance, we had to use <code>runWriter</code> to convert our
<code>Writer</code> values to normal tuples that can be shown. For
<code>String</code>, the monoid value is the empty string. With
<code>Sum</code>, it’s <code>0</code>, because if we add 0 to something,
that something stays the same. For <code>Product</code>, the identity is
<code>1</code>.</p>
<p>The <code>Writer</code> instance doesn’t feature an implementation
for <code>fail</code>, so if a pattern match fails in <code>do</code>
notation, <code>error</code> is called.</p>
<h3 id="using-do-notation-with-writer">Using do notation with
Writer</h3>
<p>Now that we have a <code>Monad</code> instance, we’re free to use
<code>do</code> notation for <code>Writer</code> values. It’s handy for
when we have a several <code>Writer</code> values and we want to do
stuff with them. Like with other monads, we can treat them as normal
values and the context gets taken for us. In this case, all the monoid
values that come attached get <code>mappend</code>ed and so are
reflected in the final result. Here’s a simple example of using
<code>do</code> notation with <code>Writer</code> to multiply two
numbers:</p>
<pre class="haskell:hs"><code>import Control.Monad.Writer
logNumber :: Int -> Writer [String] Int
logNumber x = Writer (x, ["Got number: " ++ show x])
multWithLog :: Writer [String] Int
multWithLog = do
a <- logNumber 3
b <- logNumber 5
return (a*b)</code></pre>
<p><code>logNumber</code> takes a number and makes a <code>Writer</code>
value out of it. For the monoid, we use a list of strings and we equip
the number with a singleton list that just says that we have that
number. <code>multWithLog</code> is a <code>Writer</code> value which
multiplies <code>3</code> and <code>5</code> and makes sure that their
attached logs get included in the final log. We use <code>return</code>
to present <code>a*b</code> as the result. Because <code>return</code>
just takes something and puts it in a minimal context, we can be sure
that it won’t add anything to the log. Here’s what we see if we run
this:</p>
<pre class="haskell:hs"><code>ghci> runWriter multWithLog
(15,["Got number: 3","Got number: 5"])</code></pre>
<p>Sometimes we just want some monoid value to be included at some
particular point. For this, the <code>tell</code> function is useful.
It’s part of the <code>MonadWriter</code> type class and in the case of
<code>Writer</code> it takes a monoid value, like
<code>["This is going on"]</code> and creates a <code>Writer</code>
value that presents the dummy value <code>()</code> as its result but
has our desired monoid value attached. When we have a monadic value that
has <code>()</code> as its result, we don’t bind it to a variable.
Here’s <code>multWithLog</code> but with some extra reporting
included:</p>
<pre class="haskell:hs"><code>multWithLog :: Writer [String] Int
multWithLog = do
a <- logNumber 3
b <- logNumber 5
tell ["Gonna multiply these two"]
return (a*b)</code></pre>
<p>It’s important that <code>return (a*b)</code> is the last line,
because the result of the last line in a <code>do</code> expression is
the result of the whole <code>do</code> expression. Had we put
<code>tell</code> as the last line, <code>()</code> would have been the
result of this <code>do</code> expression. We’d lose the result of the
multiplication. However, the log would be the same. Here is this in
action:</p>
<pre class="haskell:hs"><code>ghci> runWriter multWithLog
(15,["Got number: 3","Got number: 5","Gonna multiply these two"])</code></pre>
<h3 id="adding-logging-to-programs">Adding logging to programs</h3>
<p>Euclid’s algorithm is an algorithm that takes two numbers and
computes their greatest common divisor. That is, the biggest number that
still divides both of them. Haskell already features the
<code>gcd</code> function, which does exactly this, but let’s implement
our own and then equip it with logging capabilities. Here’s the normal
algorithm:</p>
<pre class="haskell:hs"><code>gcd' :: Int -> Int -> Int
gcd' a b
| b == 0 = a
| otherwise = gcd' b (a `mod` b)</code></pre>
<p>The algorithm is very simple. First, it checks if the second number
is 0. If it is, then the result is the first number. If it isn’t, then
the result is the greatest common divisor of the second number and the
remainder of dividing the first number with the second one. For
instance, if we want to know what the greatest common divisor of 8 and 3
is, we just follow the algorithm outlined. Because 3 isn’t 0, we have to
find the greatest common divisor of 3 and 2 (if we divide 8 by 3, the
remainder is 2). Next, we find the greatest common divisor of 3 and 2. 2
still isn’t 0, so now we have have 2 and 1. The second number isn’t 0,
so we run the algorithm again for 1 and 0, as dividing 2 by 1 gives us a
remainder of 0. And finally, because the second number is now 0, the
final result is 1. Let’s see if our code agrees:</p>
<pre class="haskell:hs"><code>ghci> gcd' 8 3
1</code></pre>
<p>It does. Very good! Now, we want to equip our result with a context,
and the context will be a monoid value that acts as a log. Like before,
we’ll use a list of strings as our monoid. So the type of our new
<code>gcd'</code> function should be:</p>
<pre class="haskell:hs"><code>gcd' :: Int -> Int -> Writer [String] Int</code></pre>
<p>All that’s left now is to equip our function with log values. Here’s
the code:</p>
<pre class="haskell:hs"><code>import Control.Monad.Writer
gcd' :: Int -> Int -> Writer [String] Int
gcd' a b
| b == 0 = do
tell ["Finished with " ++ show a]
return a
| otherwise = do
tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
gcd' b (a `mod` b)</code></pre>
<p>This function takes two normal <code>Int</code> values and returns a
<code>Writer [String] Int</code>, that is, an <code>Int</code> that has
a log context. In the case where <code>b</code> is <code>0</code>,
instead of just giving <code>a</code> as the result, we use a
<code>do</code> expression to put together a <code>Writer</code> value
as a result. First we use <code>tell</code> to report that we’re
finished and then we use <code>return</code> to present <code>a</code>
as the result of the <code>do</code> expression. Instead of this
<code>do</code> expression, we could have also written this:</p>
<pre class="haskell:hs"><code>Writer (a, ["Finished with " ++ show a])</code></pre>
<p>However, I think the <code>do</code> expression is easier to read.
Next, we have the case when <code>b</code> isn’t <code>0</code>. In this
case, we log that we’re using <code>mod</code> to figure out the
remainder of dividing <code>a</code> and <code>b</code>. Then, the
second line of the <code>do</code> expression just recursively calls
<code>gcd'</code>. Remember, <code>gcd'</code> now ultimately returns a
<code>Writer</code> value, so it’s perfectly valid that
<code>gcd' b (a `mod` b)</code> is a line in a <code>do</code>
expression.</p>
<p>While it may be kind of useful to trace the execution of this new
<code>gcd'</code> by hand to see how the logs get appended, I think it’s
more insightful to just look at the big picture and view these as values
with a context and from that gain insight as to what the final result
will be.</p>
<p>Let’s try our new <code>gcd'</code> out. Its result is a
<code>Writer [String] Int</code> value and if we unwrap that from its
<code>newtype</code>, we get a tuple. The first part of the tuple is the
result. Let’s see if it’s okay:</p>
<pre class="haskell:hs"><code>ghci> fst $ runWriter (gcd' 8 3)
1</code></pre>
<p>Good! Now what about the log? Because the log is a list of strings,
let’s use <code>mapM_ putStrLn</code> to print those strings to the
screen:</p>
<pre class="haskell:hs"><code>ghci> mapM_ putStrLn $ snd $ runWriter (gcd' 8 3)
8 mod 3 = 2
3 mod 2 = 1
2 mod 1 = 0
Finished with 1</code></pre>
<p>I think it’s awesome how we were able to change our ordinary
algorithm to one that reports what it does as it goes along just by
changing normal values to monadic values and letting the implementation
of <code>>>=</code> for <code>Writer</code> take care of the logs
for us. We can add a logging mechanism to pretty much any function. We
just replace normal values with <code>Writer</code> values where we want
and change normal function application to <code>>>=</code> (or
<code>do</code> expressions if it increases readability).</p>
<h3 id="inefficient-list-construction">Inefficient list
construction</h3>
<p>When using the <code>Writer</code> monad, you have to be careful
which monoid to use, because using lists can sometimes turn out to be
very slow. That’s because lists use <code>++</code> for
<code>mappend</code> and using <code>++</code> to add something to the
end of a list is slow if that list is really long.</p>
<p>In our <code>gcd'</code> function, the logging is fast because the
list appending ends up looking like this:</p>
<pre class="haskell:hs"><code>a ++ (b ++ (c ++ (d ++ (e ++ f))))</code></pre>
<p>Lists are a data structure that’s constructed from left to right, and
this is efficient because we first fully construct the left part of a
list and only then add a longer list on the right. But if we’re not
careful, using the <code>Writer</code> monad can produce list appending
that looks like this:</p>
<pre class="haskell:hs"><code>((((a ++ b) ++ c) ++ d) ++ e) ++ f</code></pre>
<p>This associates to the left instead of to the right. This is
inefficient because every time it wants to add the right part to the
left part, it has to construct the left part all the way from the
beginning!</p>
<p>The following function works like <code>gcd'</code>, only it logs
stuff in reverse. First it produces the log for the rest of the
procedure and then adds the current step to the end of the log.</p>
<pre class="haskell:hs"><code>import Control.Monad.Writer
gcdReverse :: Int -> Int -> Writer [String] Int
gcdReverse a b
| b == 0 = do
tell ["Finished with " ++ show a]
return a
| otherwise = do
result <- gcdReverse b (a `mod` b)
tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
return result</code></pre>
<p>It does the recursion first, and binds its result value to
<code>result</code>. Then it adds the current step to the log, but the
current step goes at the end of the log that was produced by the
recursion. Finally, it presents the result of the recursion as the final
result. Here it is in action:</p>
<pre class="haskell:hs"><code>ghci> mapM_ putStrLn $ snd $ runWriter (gcdReverse 8 3)
Finished with 1
2 mod 1 = 0
3 mod 2 = 1
8 mod 3 = 2</code></pre>
<p>It’s inefficient because it ends up associating the use of
<code>++</code> to the left instead of to the right.</p>
<h3 id="difference-lists">Difference lists</h3>
<p><img src="assets/images/for-a-few-monads-more/cactus.png"
class="left" width="147" height="300" alt="cactuses" /></p>
<p>Because lists can sometimes be inefficient when repeatedly appended
in this manner, it’s best to use a data structure that always supports
efficient appending. One such data structure is the difference list. A
difference list is similar to a list, only instead of being a normal
list, it’s a function that takes a list and prepends another list to it.
The difference list equivalent of a list like <code>[1,2,3]</code> would
be the function <code>\xs -> [1,2,3] ++ xs</code>. A normal empty
list is <code>[]</code>, whereas an empty difference list is the
function <code>\xs -> [] ++ xs</code>.</p>
<p>The cool thing about difference lists is that they support efficient
appending. When we append two normal lists with <code>++</code>, it has
to walk all the way to the end of the list on the left of
<code>++</code> and then stick the other one there. But what if we take
the difference list approach and represent our lists as functions? Well
then, appending two difference lists can be done like so:</p>
<pre class="haskell:hs"><code>f `append` g = \xs -> f (g xs)</code></pre>
<p>Remember, <code>f</code> and <code>g</code> are functions that take
lists and prepend something to them. So, for instance, if <code>f</code>
is the function <code>("dog"++)</code> (just another way of writing
<code>\xs -> "dog" ++ xs</code>) and <code>g</code> the function
<code>("meat"++)</code>, then <code>f `append` g</code> makes a new
function that’s equivalent to the following:</p>
<pre class="haskell:hs"><code>\xs -> "dog" ++ ("meat" ++ xs)</code></pre>
<p>We’ve appended two difference lists just by making a new function
that first applies one difference list some list and then the other.</p>
<p>Let’s make a <code>newtype</code> wrapper for difference lists so
that we can easily give them monoid instances:</p>
<pre class="haskell:hs"><code>newtype DiffList a = DiffList { getDiffList :: [a] -> [a] }</code></pre>
<p>The type that we wrap is <code>[a] -> [a]</code> because a
difference list is just a function that takes a list and returns
another. Converting normal lists to difference lists and vice versa is
easy:</p>
<pre class="haskell:hs"><code>toDiffList :: [a] -> DiffList a
toDiffList xs = DiffList (xs++)
fromDiffList :: DiffList a -> [a]
fromDiffList (DiffList f) = f []</code></pre>
<p>To make a normal list into a difference list we just do what we did
before and make it a function that prepends it to another list. Because
a difference list is a function that prepends something to another list,
if we just want that something, we apply the function to an empty
list!</p>
<p>Here’s the <code>Monoid</code> instance:</p>
<pre class="haskell:hs"><code>instance Monoid (DiffList a) where
mempty = DiffList (\xs -> [] ++ xs)
(DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))</code></pre>
<p>Notice how for lists, <code>mempty</code> is just the <code>id</code>
function and <code>mappend</code> is actually just function composition.
Let’s see if this works:</p>
<pre class="haskell:hs"><code>ghci> fromDiffList (toDiffList [1,2,3,4] `mappend` toDiffList [1,2,3])
[1,2,3,4,1,2,3]</code></pre>
<p>Tip top! Now we can increase the efficiency of our
<code>gcdReverse</code> function by making it use difference lists
instead of normal lists:</p>
<pre class="haskell:hs"><code>import Control.Monad.Writer
gcd' :: Int -> Int -> Writer (DiffList String) Int
gcd' a b
| b == 0 = do
tell (toDiffList ["Finished with " ++ show a])
return a
| otherwise = do
result <- gcd' b (a `mod` b)
tell (toDiffList [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)])
return result</code></pre>
<p>We only had to change the type of the monoid from
<code>[String]</code> to <code>DiffList String</code> and then when
using <code>tell</code>, convert our normal lists into difference lists
with <code>toDiffList</code>. Let’s see if the log gets assembled
properly:</p>
<pre class="haskell:hs"><code>ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ gcdReverse 110 34
Finished with 2
8 mod 2 = 0
34 mod 8 = 2
110 mod 34 = 8</code></pre>
<p>We do <code>gcdReverse 110 34</code>, then use <code>runWriter</code>
to unwrap it from the <code>newtype</code>, then apply <code>snd</code>
to that to just get the log, then apply <code>fromDiffList</code> to
convert it to a normal list and then finally print its entries to the
screen.</p>
<h3 id="comparing-performance">Comparing Performance</h3>
<p>To get a feel for just how much difference lists may improve your
performance, consider this function that just counts down from some
number to zero, but produces its log in reverse, like
<code>gcdReverse</code>, so that the numbers in the log will actually be
counted up:</p>
<pre class="haskell:hs"><code>finalCountDown :: Int -> Writer (DiffList String) ()
finalCountDown 0 = do
tell (toDiffList ["0"])
finalCountDown x = do
finalCountDown (x-1)
tell (toDiffList [show x])</code></pre>
<p>If we give it <code>0</code>, it just logs it. For any other number,
it first counts down its predecessor to <code>0</code> and then appends
that number to the log. So if we apply <code>finalCountDown</code> to
<code>100</code>, the string <code>"100"</code> will come last in the
log.</p>
<p>Anyway, if you load this function in GHCi and apply it to a big
number, like <code>500000</code>, you’ll see that it quickly starts
counting from <code>0</code> onwards:</p>
<pre class="haskell:hs"><code>ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ finalCountDown 500000
0
1
2
...</code></pre>
<p>However, if we change it to use normal lists instead of difference
lists, like so:</p>
<pre class="haskell:hs"><code>finalCountDown :: Int -> Writer [String] ()
finalCountDown 0 = do
tell ["0"]
finalCountDown x = do
finalCountDown (x-1)
tell [show x]</code></pre>
<p>And then tell GHCi to start counting:</p>
<pre class="haskell:hs"><code>ghci> mapM_ putStrLn . snd . runWriter $ finalCountDown 500000</code></pre>
<p>We’ll see that the counting is really slow.</p>
<p>Of course, this is not the proper and scientific way to test how fast
our programs are, but we were able to see that in this case, using
difference lists starts producing results right away whereas normal
lists take forever.</p>
<p>Oh, by the way, the song Final Countdown by Europe is now stuck in
your head. Enjoy!</p>
<h2 id="reader">Reader? Ugh, not this joke again.</h2>
<p><img src="assets/images/for-a-few-monads-more/revolver.png"
class="left" width="280" height="106" alt="bang youre dead" /></p>
<p>In the <a
href="functors-applicative-functors-and-monoids.html">chapter about
applicatives</a>, we saw that the function type, <code>(->) r</code>
is an instance of <code>Functor</code>. Mapping a function
<code>f</code> over a function <code>g</code> will make a function that
takes the same thing as <code>g</code>, applies <code>g</code> to it and
then applies <code>f</code> to that result. So basically, we’re making a
new function that’s like <code>g</code>, only before returning its
result, <code>f</code> gets applied to that result as well. For
instance:</p>
<pre class="haskell:hs"><code>ghci> let f = (*5)
ghci> let g = (+3)
ghci> (fmap f g) 8
55</code></pre>
<p>We’ve also seen that functions are applicative functors. They allow
us to operate on the eventual results of functions as if we already had
their results. Here’s an example:</p>
<pre class="haskell:hs"><code>ghci> let f = (+) <$> (*2) <*> (+10)
ghci> f 3
19</code></pre>
<p>The expression <code>(+) <$> (*2) <*> (+10)</code> makes
a function that takes a number, gives that number to <code>(*2)</code>
and <code>(+10)</code> and then adds together the results. For instance,
if we apply this function to <code>3</code>, it applies both
<code>(*2)</code> and <code>(+10)</code> to <code>3</code>, giving
<code>6</code> and <code>13</code>. Then, it calls <code>(+)</code> with
<code>6</code> and <code>13</code> and the result is
<code>19</code>.</p>
<p>Not only is the function type <code>(->) r</code> a functor and an
applicative functor, but it’s also a monad. Just like other monadic
values that we’ve met so far, a function can also be considered a value
with a context. The context for functions is that that value is not
present yet and that we have to apply that function to something in
order to get its result value.</p>
<p>Because we’re already acquainted with how functions work as functors
and applicative functors, let’s dive right in and see what their
<code>Monad</code> instance looks like. It’s located in
<code>Control.Monad.Instances</code> and it goes a little something like
this:</p>
<pre class="haskell:hs"><code>instance Monad ((->) r) where
return x = \_ -> x
h >>= f = \w -> f (h w) w</code></pre>
<p>We’ve already seen how <code>pure</code> is implemented for
functions, and <code>return</code> is pretty much the same thing as
<code>pure</code>. It takes a value and puts it in a minimal context
that always has that value as its result. And the only way to make a
function that always has a certain value as its result is to make it
completely ignore its parameter.</p>
<p>The implementation for <code>>>=</code> seems a bit cryptic,
but it’s really not all that. When we use <code>>>=</code> to feed
a monadic value to a function, the result is always a monadic value. So
in this case, when we feed a function to another function, the result is
a function as well. That’s why the result starts off as a lambda. All of
the implementations of <code>>>=</code> so far always somehow
isolated the result from the monadic value and then applied the function
<code>f</code> to that result. The same thing happens here. To get the
result from a function, we have to apply it to something, which is why
we do <code>(h w)</code> here to get the result from the function and
then we apply <code>f</code> to that. <code>f</code> returns a monadic
value, which is a function in our case, so we apply it to <code>w</code>
as well.</p>
<p>If you don’t understand how <code>>>=</code> works at this
point, don’t worry, because with examples we’ll see how this is a really
simple monad. Here’s a <code>do</code> expression that utilizes this
monad:</p>
<pre class="haskell:hs"><code>import Control.Monad.Instances
addStuff :: Int -> Int
addStuff = do
a <- (*2)
b <- (+10)
return (a+b)</code></pre>
<p>This is the same thing as the applicative expression that we wrote
earlier, only now it relies on functions being monads. A <code>do</code>
expression always results in a monadic value and this one is no
different. The result of this monadic value is a function. What happens
here is that it takes a number and then <code>(*2)</code> gets applied
to that number and the result becomes <code>a</code>. <code>(+10)</code>
is applied to the same number that <code>(*2)</code> got applied to and
the result becomes <code>b</code>. <code>return</code>, like in other
monads, doesn’t have any other effect but to make a monadic value that
presents some result. This presents <code>a+b</code> as the result of
this function. If we test it out, we get the same result as before:</p>
<pre class="haskell:hs"><code>ghci> addStuff 3
19</code></pre>
<p>Both <code>(*2)</code> and <code>(+10)</code> get applied to the
number <code>3</code> in this case. <code>return (a+b)</code> does as
well, but it ignores it and always presents <code>a+b</code> as the
result. For this reason, the function monad is also called the reader
monad. All the functions read from a common source. To illustrate this
even better, we can rewrite <code>addStuff</code> like so:</p>
<pre class="haskell:hs"><code>addStuff :: Int -> Int
addStuff x = let
a = (*2) x
b = (+10) x
in a+b</code></pre>
<p>We see that the reader monad allows us to treat functions as values
with a context. We can act as if we already know what the functions will
return. It does this by gluing functions together into one function and
then giving that function’s parameter to all of the functions that it
was glued from. So if we have a lot of functions that are all just
missing one parameter and they’d eventually be applied to the same
thing, we can use the reader monad to sort of extract their future
results and the <code>>>=</code> implementation will make sure
that it all works out.</p>
<h2 id="state">Tasteful stateful computations</h2>
<p><img src="assets/images/for-a-few-monads-more/texas.png" class="left"
width="244" height="230" alt="don’t jest with texas" /></p>
<p>Haskell is a pure language and because of that, our programs are made
of functions that can’t change any global state or variables, they can
only do some computations and return them results. This restriction
actually makes it easier to think about our programs, as it frees us
from worrying what every variable’s value is at some point in time.
However, some problems are inherently stateful in that they rely on some
state that changes over time. While such problems aren’t a problem for
Haskell, they can be a bit tedious to model sometimes. That’s why
Haskell features a thing called the state monad, which makes dealing
with stateful problems a breeze while still keeping everything nice and
pure.</p>
<p><a href="input-and-output.html#randomness">When we were dealing with
random numbers</a>, we dealt with functions that took a random generator
as a parameter and returned a random number and a new random generator.
If we wanted to generate several random numbers, we always had to use
the random generator that a previous function returned along with its
result. When making a function that takes a <code>StdGen</code> and
tosses a coin three times based on that generator, we had to do
this:</p>
<pre class="haskell:hs"><code>threeCoins :: StdGen -> (Bool, Bool, Bool)
threeCoins gen =
let (firstCoin, newGen) = random gen
(secondCoin, newGen') = random newGen
(thirdCoin, newGen'') = random newGen'
in (firstCoin, secondCoin, thirdCoin)</code></pre>
<p>It took a generator <code>gen</code> and then <code>random gen</code>
returned a <code>Bool</code> value along with a new generator. To throw
the second coin, we used the new generator, and so on. In most other
languages, we wouldn’t have to return a new generator along with a
random number. We could just modify the existing one! But since Haskell
is pure, we can’t do that, so we had to take some state, make a result
from it and a new state and then use that new state to generate new
results.</p>
<p>You’d think that to avoid manually dealing with stateful computations
in this way, we’d have to give up the purity of Haskell. Well, we don’t
have to, since there exist a special little monad called the state monad
which handles all this state business for us and without giving up any
of the purity that makes Haskell programming so cool.</p>
<p>So, to help us understand this concept of stateful computations
better, let’s go ahead and give them a type. We’ll say that a stateful
computation is a function that takes some state and returns a value
along with some new state. That function would have the following
type:</p>
<pre class="haskell:hs"><code>s -> (a,s)</code></pre>
<p><code>s</code> is the type of the state and <code>a</code> the result
of the stateful computations.</p>
<div class="hintbox">
<p>Assignment in most other languages could be thought of as a stateful
computation. For instance, when we do <code>x = 5</code> in an
imperative language, it will usually assign the value <code>5</code> to
the variable <code>x</code> and it will also have the value
<code>5</code> as an expression. If you look at that functionally, you
could look at it as a function that takes a state (that is, all the
variables that have been assigned previously) and returns a result (in
this case <code>5</code>) and a new state, which would be all the
previous variable mappings plus the newly assigned variable.</p>
</div>
<p>This stateful computation, a function that takes a state and returns
a result and a new state, can be thought of as a value with a context as
well. The actual value is the result, whereas the context is that we
have to provide some initial state to actually get that result and that
apart from getting a result we also get a new state.</p>
<h3 id="stacks-and-stones">Stacks and stones</h3>
<p>Say we want to model operating a stack. You have a stack of things
one on top of another and you can either push stuff on top of that stack
or you can take stuff off the top of the stack. When you’re putting an
item on top of the stack we say that you’re pushing it to the stack and
when you’re taking stuff off the top we say that you’re popping it. If
you want to something that’s at the bottom of the stack, you have to pop
everything that’s above it.</p>
<p>We’ll use a list to represent our stack and the head of the list will
be the top of the stack. To help us with our task, we’ll make two
functions: <code>pop</code> and <code>push</code>. <code>pop</code> will
take a stack, pop one item and return that item as the result and also
return a new stack, without that item. <code>push</code> will take an
item and a stack and then push that item onto the stack. It will return
<code>()</code> as its result, along with a new stack. Here goes:</p>
<pre class="haskell:hs"><code>type Stack = [Int]
pop :: Stack -> (Int,Stack)
pop (x:xs) = (x,xs)
push :: Int -> Stack -> ((),Stack)
push a xs = ((),a:xs)</code></pre>
<p>We used <code>()</code> as the result when pushing to the stack
because pushing an item onto the stack doesn’t have any important result
value, its main job is to change the stack. Notice how we just apply the
first parameter of <code>push</code>, we get a stateful computation.
<code>pop</code> is already a stateful computation because of its
type.</p>
<p>Let’s write a small piece of code to simulate a stack using these
functions. We’ll take a stack, push <code>3</code> to it and then pop
two items, just for kicks. Here it is:</p>
<pre class="haskell:hs"><code>stackManip :: Stack -> (Int, Stack)
stackManip stack = let
((),newStack1) = push 3 stack
(a ,newStack2) = pop newStack1
in pop newStack2</code></pre>
<p>We take a <code>stack</code> and then we do
<code>push 3 stack</code>, which results in a tuple. The first part of
the tuple is a <code>()</code> and the second is a new stack and we call
it <code>newStack1</code>. Then, we pop a number from
<code>newStack1</code>, which results in a number <code>a</code> (which
is the <code>3</code>) that we pushed and a new stack which we call
<code>newStack2</code>. Then, we pop a number off <code>newStack2</code>
and we get a number that’s <code>b</code> and a <code>newStack3</code>.
We return a tuple with that number and that stack. Let’s try it out:</p>
<pre class="haskell:hs"><code>ghci> stackManip [5,8,2,1]
(5,[8,2,1])</code></pre>
<p>Cool, the result is <code>5</code> and the new stack is
<code>[8,2,1]</code>. Notice how <code>stackManip</code> is itself a
stateful computation. We’ve taken a bunch of stateful computations and
we’ve sort of glued them together. Hmm, sounds familiar.</p>
<p>The above code for <code>stackManip</code> is kind of tedious since
we’re manually giving the state to every stateful computation and
storing it and then giving it to the next one. Wouldn’t it be cooler if,
instead of giving the stack manually to each function, we could write
something like this:</p>
<pre class="haskell:hs"><code>stackManip = do
push 3
a <- pop
pop</code></pre>
<p>Well, using the state monad will allow us to do exactly this. With
it, we will be able to take stateful computations like these and use
them without having to manage the state manually.</p>
<h3 id="the-state-monad">The State monad</h3>
<p>The <code>Control.Monad.State</code> module provides a
<code>newtype</code> that wraps stateful computations. Here’s its
definition:</p>
<pre class="haskell:hs"><code>newtype State s a = State { runState :: s -> (a,s) }</code></pre>
<p>A <code>State s a</code> is a stateful computation that manipulates a
state of type <code>s</code> and has a result of type
<code>a</code>.</p>
<p>Now that we’ve seen what stateful computations are about and how they
can even be thought of as values with contexts, let’s check out their
<code>Monad</code> instance:</p>
<pre class="haskell:hs"><code>instance Monad (State s) where
return x = State $ \s -> (x,s)
(State h) >>= f = State $ \s -> let (a, newState) = h s
(State g) = f a
in g newState</code></pre>
<p>Let’s take a gander at <code>return</code> first. Our aim with
<code>return</code> is to take a value and make a stateful computation
that always has that value as its result. That’s why we just make a
lambda <code>\s -> (x,s)</code>. We always present <code>x</code> as
the result of the stateful computation and the state is kept unchanged,
because <code>return</code> has to put a value in a minimal context. So
<code>return</code> will make a stateful computation that presents a
certain value as the result and keeps the state unchanged.</p>
<p><img src="assets/images/for-a-few-monads-more/badge.png"
class="right" width="182" height="160" alt="im a cop" /></p>
<p>What about <code>>>=</code>? Well, the result of feeding a
stateful computation to a function with <code>>>=</code> has to be
a stateful computation, right? So we start off with the
<code>State</code> <code>newtype</code> wrapper and then we type out a
lambda. This lambda will be our new stateful computation. But what goes
on in it? Well, we somehow have to extract the result value from the
first stateful computation. Because we’re in a stateful computation
right now, we can give the stateful computation <code>h</code> our
current state <code>s</code>, which results in a pair of result and a
new state: <code>(a, newState)</code>. Every time so far when we were
implementing <code>>>=</code>, once we had the extracted the
result from the monadic value, we applied the function <code>f</code> to
it to get the new monadic value. In <code>Writer</code>, after doing
that and getting the new monadic value, we still had to make sure that
the context was taken care of by <code>mappend</code>ing the old monoid
value with the new one. Here, we do <code>f a</code> and we get a new
stateful computation <code>g</code>. Now that we have a new stateful
computation and a new state (goes by the name of <code>newState</code>)
we just apply that stateful computation <code>g</code> to the
<code>newState</code>. The result is a tuple of final result and final
state!</p>
<p>So with <code>>>=</code>, we kind of glue two stateful
computations together, only the second one is hidden inside a function
that takes the previous one’s result. Because <code>pop</code> and
<code>push</code> are already stateful computations, it’s easy to wrap
them into a <code>State</code> wrapper. Watch:</p>
<pre class="haskell:hs"><code>import Control.Monad.State
pop :: State Stack Int
pop = State $ \(x:xs) -> (x,xs)
push :: Int -> State Stack ()
push a = State $ \xs -> ((),a:xs)</code></pre>
<p><code>pop</code> is already a stateful computation and
<code>push</code> takes an <code>Int</code> and returns a stateful
computation. Now we can rewrite our previous example of pushing
<code>3</code> onto the stack and then popping two numbers off like
this:</p>
<pre class="haskell:hs"><code>import Control.Monad.State
stackManip :: State Stack Int
stackManip = do
push 3
a <- pop
pop</code></pre>
<p>See how we’ve glued a push and two pops into one stateful
computation? When we unwrap it from its <code>newtype</code> wrapper we
get a function to which we can provide some initial state:</p>
<pre class="haskell:hs"><code>ghci> runState stackManip [5,8,2,1]
(5,[8,2,1])</code></pre>
<p>We didn’t have to bind the second <code>pop</code> to <code>a</code>
because we didn’t use that <code>a</code> at all. So we could have
written it like this:</p>
<pre class="haskell:hs"><code>stackManip :: State Stack Int
stackManip = do
push 3
pop
pop</code></pre>
<p>Pretty cool. But what if we want to do this: pop one number off the
stack and then if that number is <code>5</code> we just put it back onto
the stack and stop but if it isn’t <code>5</code>, we push
<code>3</code> and <code>8</code> back on? Well, here’s the code:</p>
<pre class="haskell:hs"><code>stackStuff :: State Stack ()
stackStuff = do
a <- pop
if a == 5
then push 5
else do
push 3
push 8</code></pre>
<p>This is quite straightforward. Let’s run it with an initial
stack.</p>
<pre class="haskell:hs"><code>ghci> runState stackStuff [9,0,2,1,0]
((),[8,3,0,2,1,0])</code></pre>
<p>Remember, <code>do</code> expressions result in monadic values and
with the <code>State</code> monad, a single <code>do</code> expression
is also a stateful function. Because <code>stackManip</code> and
<code>stackStuff</code> are ordinary stateful computations, we can glue
them together to produce further stateful computations.</p>
<pre class="haskell:hs"><code>moreStack :: State Stack ()
moreStack = do
a <- stackManip
if a == 100
then stackStuff
else return ()</code></pre>
<p>If the result of <code>stackManip</code> on the current stack is
<code>100</code>, we run <code>stackStuff</code>, otherwise we do
nothing. <code>return ()</code> just keeps the state as it is and does
nothing.</p>
<p>The <code>Control.Monad.State</code> module provides a type class
that’s called <code>MonadState</code> and it features two pretty useful
functions, namely <code>get</code> and <code>put</code>. For
<code>State</code>, the <code>get</code> function is implemented like
this:</p>
<pre class="haskell:hs"><code>get = State $ \s -> (s,s)</code></pre>
<p>So it just takes the current state and presents it as the result. The
<code>put</code> function takes some state and makes a stateful function
that replaces the current state with it:</p>
<pre class="haskell:hs"><code>put newState = State $ \s -> ((),newState)</code></pre>
<p>So with these, we can see what the current stack is or we can replace
it with a whole other stack. Like so:</p>
<pre class="haskell:hs"><code>stackyStack :: State Stack ()
stackyStack = do
stackNow <- get
if stackNow == [1,2,3]
then put [8,3,1]
else put [9,2,1]</code></pre>
<p>It’s worth examining what the type of <code>>>=</code> would be
if it only worked for <code>State</code> values:</p>
<pre class="haskell:hs"><code>(>>=) :: State s a -> (a -> State s b) -> State s b</code></pre>
<p>See how the type of the state <code>s</code> stays the same but the
type of the result can change from <code>a</code> to <code>b</code>?
This means that we can glue together several stateful computations whose
results are of different types but the type of the state has to stay the
same. Now why is that? Well, for instance, for <code>Maybe</code>,
<code>>>=</code> has this type:</p>
<pre class="haskell:hs"><code>(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b</code></pre>
<p>It makes sense that the monad itself, <code>Maybe</code>, doesn’t
change. It wouldn’t make sense to use <code>>>=</code> between two
different monads. Well, for the state monad, the monad is actually