-
Notifications
You must be signed in to change notification settings - Fork 68
Expand file tree
/
Copy patha-fistful-of-monads.html
More file actions
2149 lines (1851 loc) · 82.5 KB
/
a-fistful-of-monads.html
File metadata and controls
2149 lines (1851 loc) · 82.5 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>A Fistful of Monads - 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="functors-applicative-functors-and-monoids.html">
<link rel="next" href="for-a-few-monads-more.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="functors-applicative-functors-and-monoids.html" class="prevlink">Functors, Applicative Functors and Monoids</a>
</li>
<li style="text-align:center">
<a href="chapters.html">Table of contents</a>
</li>
<li style="text-align:right">
<a href="for-a-few-monads-more.html" class="nxtlink">For a Few Monads More</a>
</li>
</ul>
</div>
<h1>A Fistful of Monads</h1>
<p>
When we first talked about functors, we saw that they were a useful concept for
values that can be mapped over. Then, we took that concept one step further by
introducing applicative functors, which allow us to view values of certain data
types as values with contexts and use normal functions on those values while
preserving the meaning of those contexts.
</p>
<p>
In this chapter, we'll learn about
monads, which are just beefed up applicative functors, much like
applicative functors are only beefed up functors.
</p>
<img src="assets/images/a-fistful-of-monads/smugpig.png" alt="more cool than u" class="right" width="307" height="186">
<p>
When we started off with functors, we saw that it's possible to map functions
over various data types. We saw that for this purpose, the <span class="fixed">Functor</span>
type class was introduced and it had us asking the question: when we have a
function of type <span class="fixed">a -> b</span> and some data type
<span class="fixed">f a</span>, how do we map that function over the data type
to end up with <span class="fixed">f b</span>? We saw how to map something over
a <span class="fixed">Maybe a</span>, a list <span class="fixed">[a]</span>, an <span class="fixed">IO
a</span> etc. We even saw how to map a function <span class="fixed">a -> b</span>
over other functions of type <span class="fixed">r -> a</span> to get
functions of type <span class="fixed">r -> b</span>. To answer this question
of how to map a function over some data type, all we had to do was look at the type
of <span class="fixed">fmap</span>:
</p>
<pre name="code" class="haskell:hs">
fmap :: (Functor f) => (a -> b) -> f a -> f b
</pre>
<p>
And then make it work for our data type by writing the appropriate <span
class="fixed">Functor</span> instance.
</p>
<p>
Then we saw a possible improvement of functors and said, hey, what if that
function <span class="fixed">a -> b</span> is already wrapped inside a
functor value? Like, what if we have <span class="fixed">Just (*3)</span>, how
do we apply that to <span class="fixed">Just 5</span>? What if we don't want to
apply it to <span class="fixed">Just 5</span> but to a <span
class="fixed">Nothing</span> instead? Or if we have <span class="fixed">[(*2),(+4)]</span>,
how would we apply that to <span class="fixed">[1,2,3]</span>? How would that
work even? For this, the <span class="fixed">Applicative</span> type class was
introduced, in which we wanted the answer to the following type:
</p>
<pre name="code" class="haskell:hs">
(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b
</pre>
<p>
We also saw that we can take a normal value and wrap it inside a data type. For
instance, we can take a
<span class="fixed">1</span> and wrap it so that it becomes a
<span class="fixed">Just 1</span>. Or we can make it into a <span
class="fixed">[1]</span>. Or an I/O action that does nothing and just yields
<span class="fixed">1</span>. The function that does this is called <span
class="fixed">pure</span>.
</p>
<p>
Like we said, an applicative value can be seen as a value with an added context.
A <i>fancy</i> value, to put it in technical terms. For instance, the character <span
class="fixed">'a'</span> is just a normal character, whereas <span
class="fixed">Just 'a'</span> has some added context. Instead of a <span
class="fixed">Char</span>, we have a <span class="fixed">Maybe Char</span>,
which tells us that its value might be a character, but it could also be an
absence of a character.
</p>
<p>
It was neat to see how the <span class="fixed">Applicative</span> type class
allowed us to use normal functions on these values with context and how that
context was preserved. Observe:
</p>
<pre name="code" class="haskell:hs">
ghci> (*) <$> Just 2 <*> Just 8
Just 16
ghci> (++) <$> Just "klingon" <*> Nothing
Nothing
ghci> (-) <$> [3,4] <*> [1,2,3]
[2,1,0,3,2,1]
</pre>
<p>
Ah, cool, so now that we treat them as applicative values, <span
class="fixed">Maybe a</span> values represent computations that might have
failed, <span class="fixed">[a]</span> values represent computations that have
several results (non-deterministic computations), <span class="fixed">IO
a</span> values represent values that have side-effects, etc.
</p>
<p>
Monads are a natural extension of applicative functors and with them we're
concerned with this: if you have a value with a context, <span class="fixed">m
a</span>, how do you apply to it a function that takes a normal <span
class="fixed">a</span> and returns a value with a context? That is, how do you
apply a function of type <span class="fixed">a -> m b</span> to a value of
type <span class="fixed">m a</span>? So essentially, we will want this function:
</p>
<pre name="code" class="haskell:hs">
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
</pre>
<p>
<b>If we have a fancy value and a function that takes a normal value but
returns a fancy value, how do we feed that fancy value into the function?</b> This
is the main question that we will concern ourselves when dealing with monads. We write
<span class="fixed">m a</span> instead of <span class="fixed">f a</span> because
the <span class="fixed">m</span> stands for <span class="fixed">Monad</span>, but monads are just
applicative functors that support <span class="fixed">>>=</span>. The
<span class="fixed">>>=</span> function is pronounced as <i>bind</i>.
</p>
<p>
When we have a normal value <span class="fixed">a</span> and a normal function
<span class="fixed">a -> b</span> it's really easy to feed the value to the
function — you just apply the function to the value normally and that's
it. But when we're dealing with values that come with certain contexts, it takes
a bit of thinking to see how these fancy values are fed to functions and how to
take into account their behavior, but you'll see that it's easy as one two
three.
</p>
<a name="getting-our-feet-wet-with-maybe"></a>
<h2>Getting our feet wet with Maybe</h2>
<img src="assets/images/a-fistful-of-monads/buddha.png" alt="monads, grasshoppa" class="left" width="302" height="387">
<p>
Now that we have a vague idea of what monads are about, let's see if we can make
that idea a bit less vague.
</p>
<p>
Much to no one's surprise, <span class="fixed">Maybe</span> is a monad, so let's
explore it a bit more and see if we can combine it with what we know about
monads.
</p>
<div class="hintbox">
Make sure you understand <a href="functors-applicative-functors-and-monoids.html#applicative-functors">applicatives</a> at this point. It's good if you have a
feel for how the various <span class="fixed">Applicative</span> instances work
and what kind of computations they represent, because monads are nothing more
than taking our existing applicative knowledge and upgrading it.
</div>
<p>
A value of type <span class="fixed">Maybe a</span> represents a value of type
<span class="fixed">a</span> with the context of possible failure attached. A
value of <span class="fixed">Just "dharma"</span> means that the string <span
class="fixed">"dharma"</span> is there whereas a value of
<span class="fixed">Nothing</span> represents its absence, or if you look at the
string as the result of a computation, it means that the computation has failed.
</p>
<p>
When we looked at <span class="fixed">Maybe</span> as a functor, we saw that if
we want to <span class="fixed">fmap</span> a function over it, it gets mapped
over the insides if it's a <span class="fixed">Just</span> value, otherwise the
<span class="fixed">Nothing</span> is kept because there's nothing to map it
over!
</p>
<p>
Like this:
</p>
<pre name="code" class="haskell:hs">
ghci> fmap (++"!") (Just "wisdom")
Just "wisdom!"
ghci> fmap (++"!") Nothing
Nothing
</pre>
<p>
As an applicative functor, it functions similarly. However, applicatives also
have the function wrapped. <span class="fixed">Maybe</span> is an applicative
functor in such a way that when we use <span class="fixed"><*></span> to
apply a function inside a <span class="fixed">Maybe</span> to a value that's
inside a <span class="fixed">Maybe</span>, they both have to be <span
class="fixed">Just</span> values for the result to be a <span
class="fixed">Just</span> value, otherwise the result is <span
class="fixed">Nothing</span>. It makes sense because if you're missing either
the function or the thing you're applying it to, you can't make something up out
of thin air, so you have to propagate the failure:
</p>
<pre name="code" class="haskell:hs">
ghci> Just (+3) <*> Just 3
Just 6
ghci> Nothing <*> Just "greed"
Nothing
ghci> Just ord <*> Nothing
Nothing
</pre>
<p>
When we use the applicative style to have normal functions act on <span
class="fixed">Maybe</span> values, it's similar. All the values have to be <span
class="fixed">Just</span> values, otherwise it's all for <span
class="fixed">Nothing</span>!
</p>
<pre name="code" class="haskell:hs">
ghci> max <$> Just 3 <*> Just 6
Just 6
ghci> max <$> Just 3 <*> Nothing
Nothing
</pre>
<p>
And now, let's think about how we would do <span class="fixed">>>=</span>
for <span class="fixed">Maybe</span>. Like we said, <span class="fixed">>>=</span>
takes a monadic value, and a function that takes a normal value and returns a
monadic value and manages to apply that function to the monadic value. How does
it do that, if the function takes a normal value? Well, to do that, it has to
take into account the context of that monadic value.
</p>
<p>
In this case, <span class="fixed">>>=</span> would take a <span
class="fixed">Maybe a</span> value and a function of type <span class="fixed">a -> Maybe b</span>
and somehow apply the function to the <span class="fixed">Maybe a</span>. To
figure out how it does that, we can use the intuition that we have from <span
class="fixed">Maybe</span> being an applicative functor. Let's say that we have
a function <span class="fixed">\x -> Just (x+1)</span>. It takes a number,
adds <span class="fixed">1</span> to it and wraps it in a <span
class="fixed">Just</span>:
</p>
<pre name="code" class="haskell:hs">
ghci> (\x -> Just (x+1)) 1
Just 2
ghci> (\x -> Just (x+1)) 100
Just 101
</pre>
<p>
If we feed it <span class="fixed">1</span>, it evaluates to <span
class="fixed">Just 2</span>. If we give it the number <span
class="fixed">100</span>, the result is <span class="fixed">Just 101</span>.
Very straightforward. Now here's the kicker: how do we feed a
<span class="fixed">Maybe</span> value to this function? If we think about how
<span class="fixed">Maybe</span> acts as an applicative functor, answering this
is pretty easy. If we feed it a <span class="fixed">Just</span> value, take what's inside
the <span class="fixed">Just</span> and apply the function to it. If give it
a <span class="fixed">Nothing</span>, hmm, well, then we're left with a
function but <span class="fixed">Nothing</span> to apply it to. In that case,
let's just do what we did before and say that the result is <span
class="fixed">Nothing</span>.
</p>
<p>
Instead of calling it <span class="fixed">>>=</span>, let's call it
<span class="fixed">applyMaybe</span> for now. It takes a <span
class="fixed">Maybe a</span> and a function that returns a <span
class="fixed">Maybe b</span> and manages to apply that function to the <span
class="fixed">Maybe a</span>. Here it is in code:
</p>
<pre name="code" class="haskell:hs">
applyMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b
applyMaybe Nothing f = Nothing
applyMaybe (Just x) f = f x
</pre>
<p>
Okay, now let's play with it for a bit. We'll use it as an infix function so that
the <span class="fixed">Maybe</span> value is on the left side and the function on
the right:
</p>
<pre name="code" class="haskell:hs">
ghci> Just 3 `applyMaybe` \x -> Just (x+1)
Just 4
ghci> Just "smile" `applyMaybe` \x -> Just (x ++ " :)")
Just "smile :)"
ghci> Nothing `applyMaybe` \x -> Just (x+1)
Nothing
ghci> Nothing `applyMaybe` \x -> Just (x ++ " :)")
Nothing
</pre>
<p>
In the above example, we see that when we used <span class="fixed">applyMaybe</span> with a <span class="fixed">Just</span> value and a function, the function simply got applied to the value inside the <span class="fixed">Just</span>. When we tried to use it with a <span class="fixed">Nothing</span>, the whole result was <span class="fixed">Nothing</span>.
What about if the function returns a <span class="fixed">Nothing</span>? Let's
see:
</p>
<pre name="code" class="haskell:hs">
ghci> Just 3 `applyMaybe` \x -> if x > 2 then Just x else Nothing
Just 3
ghci> Just 1 `applyMaybe` \x -> if x > 2 then Just x else Nothing
Nothing
</pre>
<p>
Just what we expected. If the monadic value on the left is a <span
class="fixed">Nothing</span>, the whole thing is <span class="fixed">Nothing</span>.
And if the function on the right returns a <span class="fixed">Nothing</span>,
the result is <span class="fixed">Nothing</span> again. This is very similar to when
we used <span class="fixed">Maybe</span> as an applicative and we got a <span
class="fixed">Nothing</span> result if somewhere in there was a <span
class="fixed">Nothing</span>.
</p>
<p>
It looks like that for <span class="fixed">Maybe</span>, we've figured out how
to take a fancy value and feed it to a function that takes a normal value and
returns a fancy one. We did this by keeping in mind that a <span
class="fixed">Maybe</span> value represents a computation that might have
failed.
</p>
<p>
You might be asking yourself, how is this useful? It may seem like applicative
functors are stronger than monads, since applicative functors allow us to take a
normal function and make it operate on values with contexts. We'll see that
monads can do that as well because they're an upgrade of applicative functors,
and that they can also do some cool stuff that applicative functors can't.
</p>
<p>
We'll come back to <span class="fixed">Maybe</span> in a minute, but first,
let's check out the type class that belongs to monads.
</p>
<a name="the-monad-type-class"></a>
<h2>The Monad type class</h2>
<p>
Just like functors have the <span class="fixed">Functor</span> type class and applicative
functors have the <span class="fixed">Applicative</span> type class,
monads come with their own type class: <span class="fixed">Monad</span>! Wow,
who would have thought? This is what the type class looks like:
</p>
<pre name="code" class="haskell:hs">
class Applicative m => Monad m where
return :: a -> m a
return = pure
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
x >> y = x >>= \_ -> y
</pre>
<img src="assets/images/a-fistful-of-monads/kid.png" alt="this is you on monads" class="right" width="363" height="451">
<p>
Let's start with the first line. It says
<span class="fixed">class (Applicative m) = > Monad m where</span> which means
that if we want to create an instance of Monad for some type, we must have an
instance of Applicative for that type.
</p>
<p>
The first function that the <span class="fixed">Monad</span> type class defines
is <span class="fixed">return</span>. It's the same as <span
class="fixed">pure</span>, only with a different name. Its type is <span
class="fixed">(Monad m) => a -> m a</span>. It takes a value and puts it
in a minimal default context that still holds that value. In other words, it
takes something and wraps it in a monad. It always does the same thing as the
<span class="fixed">pure</span> function from the <span
class="fixed">Applicative</span> type class, which means we're already
acquainted with <span class="fixed">return</span>. We already used <span
class="fixed">return</span> when doing I/O. We used it to take a value and make
a bogus I/O action that does nothing but yield that value. For <span
class="fixed">Maybe</span> it takes a value and wraps it in a <span
class="fixed">Just</span>.
</p>
<div class="hintbox">
Just a reminder: <span class="fixed">return</span> is nothing like the
<span class="fixed">return</span> that's in most other languages. It doesn't end
function execution or anything, it just takes a normal value and puts it in a
context.
</div>
<img src="assets/images/a-fistful-of-monads/tur2.png" alt="hmmm yaes" class="left" width="169" height="145">
<p>
The next function is <span class="fixed">>>=</span>, or bind. It's like
function application, only instead of taking a normal value and feeding it to a
normal function, it takes a monadic value (that is, a value with a context) and
feeds it to a function that takes a normal value but returns a monadic value.
</p>
<p>
Next up, we have <span class="fixed">>></span>. We won't pay too much
attention to it for now because it comes with a default implementation and we
pretty much never implement it when making <span class="fixed">Monad</span>
instances.
</p>
<p>
Now that we know what the <span class="fixed">Monad</span> type class looks
like, let's take a look at how <span class="fixed">Maybe</span> is an instance
of <span class="fixed">Monad</span>!
</p>
<pre name="code" class="haskell:hs">
instance Monad Maybe where
Nothing >>= f = Nothing
Just x >>= f = f x
</pre>
<p>
Both <span class="fixed">return</span> and <span class="fixed">(>>)</span> have <em>default
implementations</em>, so we omit them in instances. <span class="fixed">return</span>
is the same as <span class="fixed">pure</span>, it wraps a value in
<span class="fixed">Just</span>.
</p>
<p>
The <span class="fixed">>>=</span> function is the same as our
<span class="fixed">applyMaybe</span>. When feeding the <span
class="fixed">Maybe a</span> to our function, we keep in mind the context and
return a <span class="fixed">Nothing</span> if the value on the left is <span
class="fixed">Nothing</span> because if there's no value then there's no way to
apply our function to it. If it's a <span class="fixed">Just</span> we take
what's inside and apply <span class="fixed">f</span> to it.
</p>
<p>
We can play around with <span class="fixed">Maybe</span> as a monad:
</p>
<pre name="code" class="haskell:hs">
ghci> return "WHAT" :: Maybe String
Just "WHAT"
ghci> Just 9 >>= \x -> return (x*10)
Just 90
ghci> Nothing >>= \x -> return (x*10)
Nothing
</pre>
<p>
Nothing new or exciting on the first line since we already used <span
class="fixed">pure</span> with <span class="fixed">Maybe</span> and we know that <span
class="fixed">return</span> is just <span class="fixed">pure</span> with a
different name. The next two lines showcase <span class="fixed">>>=</span>
a bit more.
</p>
<p>
Notice how when we fed <span class="fixed">Just 9</span> to the function <span
class="fixed">\x -> return (x*10)</span>, the <span class="fixed">x</span>
took on the value <span class="fixed">9</span> inside the function. It seems as
though we were able to extract the value from a <span class="fixed">Maybe</span>
without pattern-matching. And we still didn't lose the context of our <span
class="fixed">Maybe</span> value, because when it's <span class="fixed">Nothing</span>,
the result of using <span class="fixed">>>=</span> will be <span class="fixed">Nothing</span> as well.
</p>
<a name="walk-the-line"></a>
<h2>Walk the line</h2>
<img src="assets/images/a-fistful-of-monads/pierre.png" alt="pierre" class="left" width="374" height="405">
<p>
Now that we know how to feed a <span class="fixed">Maybe a</span> value to a
function of type
<span class="fixed">a -> Maybe b</span> while taking into account the context
of possible failure, let's see how we can use <span
class="fixed">>>=</span> repeatedly to handle computations of several
<span class="fixed">Maybe a</span> values.
</p>
<p>
Pierre has decided to take a break from his job at the fish farm and try
tightrope walking. He's not that bad at it, but he does have one problem: birds
keep landing on his balancing pole! They come and they take a short rest, chat
with their avian friends and then take off in search of breadcrumbs. This
wouldn't bother him so much if the number of birds on the left side of the pole
was always equal to the number of birds on the right side. But sometimes, all
the birds decide that they like one side better and so they throw him off
balance, which results in an embarrassing tumble for Pierre (he's using a safety
net).
</p>
<p>
Let's say that he keeps his balance if the number of birds on the left side of
the pole and on the right side of the pole is within three. So if there's
one bird on the right side and four birds on the left side, he's okay. But if a
fifth bird lands on the left side, then he loses his balance and takes a dive.
</p>
<p>
We're going to simulate birds landing on and flying away from the pole and see
if Pierre is still at it after a certain number of birdy arrivals and
departures. For instance, we want to see what happens to Pierre if first one
bird arrives on the left side, then four birds occupy the right side and then
the bird that was on the left side decides to fly away.
</p>
<p>
We can represent the pole with a simple pair of integers. The first component
will signify the number of birds on the left side and the second component the
number of birds on the right side:
</p>
<pre name="code" class="haskell:hs">
type Birds = Int
type Pole = (Birds,Birds)
</pre>
<p>
First we made a type synonym for <span class="fixed">Int</span>, called
<span class="fixed">Birds</span>, because we're using integers to represent
how many birds there are. And then we made a type synonym <span class="fixed">(Birds,Birds)</span> and we called it <span class="fixed">Pole</span> (not to be
confused with a person of Polish descent).
</p>
<p>
Next up, how about we make a function that takes a number of birds and lands
them on one side of the pole. Here are the functions:
</p>
<pre name="code" class="haskell:hs">
landLeft :: Birds -> Pole -> Pole
landLeft n (left,right) = (left + n,right)
landRight :: Birds -> Pole -> Pole
landRight n (left,right) = (left,right + n)
</pre>
<p>
Pretty straightforward stuff. Let's try them out:
</p>
<pre name="code" class="haskell:hs">
ghci> landLeft 2 (0,0)
(2,0)
ghci> landRight 1 (1,2)
(1,3)
ghci> landRight (-1) (1,2)
(1,1)
</pre>
<p>
To make birds fly away we just had a negative number of birds land on one side. Because
landing a bird on the <span class="fixed">Pole</span> returns a <span
class="fixed">Pole</span>, we can chain applications of <span
class="fixed">landLeft</span> and <span class="fixed">landRight</span>:
</p>
<pre name="code" class="haskell:hs">
ghci> landLeft 2 (landRight 1 (landLeft 1 (0,0)))
(3,1)
</pre>
<p>
When we apply the function <span class="fixed">landLeft 1</span> to <span
class="fixed">(0,0)</span> we get <span
class="fixed">(1,0)</span>. Then, we land a bird on the right side, resulting
in <span class="fixed">(1,1)</span>. Finally two birds land on the left
side, resulting in <span class="fixed">(3,1)</span>. We apply a function to
something by first writing the function and then writing its parameter, but here
it would be better if the pole went first and then the landing function. If we
make a function like this:
</p>
<pre name="code" class="haskell:hs">
x -: f = f x
</pre>
<p>
We can apply functions by first writing the parameter and then the function:
</p>
<pre name="code" class="haskell:hs">
ghci> 100 -: (*3)
300
ghci> True -: not
False
ghci> (0,0) -: landLeft 2
(2,0)
</pre>
<p>
By using this, we can repeatedly land birds on the pole in a more readable
manner:
</p>
<pre name="code" class="haskell:hs">
ghci> (0,0) -: landLeft 1 -: landRight 1 -: landLeft 2
(3,1)
</pre>
<p>
Pretty cool! This example is equivalent to the one before where we repeatedly
landed birds on the pole, only it looks neater. Here, it's more obvious that we
start off with <span class="fixed">(0,0)</span> and then land one bird one the
left, then one on the right and finally two on the left.
</p>
<p>So far so good, but
what happens if 10 birds land on one side?
</p>
<pre name="code" class="haskell:hs">
ghci> landLeft 10 (0,3)
(10,3)
</pre>
<p>
10 birds on the left side and only 3 on the right? That's sure to send poor
Pierre falling through the air! This is pretty obvious here but what if we had a
sequence of landings like this:
</p>
<pre name="code" class="haskell:hs">
ghci> (0,0) -: landLeft 1 -: landRight 4 -: landLeft (-1) -: landRight (-2)
(0,2)
</pre>
<p>
It might seem like everything is okay but if you follow the steps here, you'll
see that at one time there are 4 birds on the right side and no birds on the
left! To fix this, we have to take another look at our <span
class="fixed">landLeft</span> and <span class="fixed">landRight</span>
functions. From what we've seen, we want these functions to be able to fail.
That is, we want them to return a new pole if the balance is okay but fail if
the birds land in a lopsided manner. And what better way to add a context of
failure to value than by using <span class="fixed">Maybe</span>! Let's rework
these functions:
</p>
<pre name="code" class="haskell:hs">
landLeft :: Birds -> Pole -> Maybe Pole
landLeft n (left,right)
| abs ((left + n) - right) < 4 = Just (left + n, right)
| otherwise = Nothing
landRight :: Birds -> Pole -> Maybe Pole
landRight n (left,right)
| abs (left - (right + n)) < 4 = Just (left, right + n)
| otherwise = Nothing
</pre>
<p>
Instead of returning a <span class="fixed">Pole</span> these functions now
return a <span class="fixed">Maybe Pole</span>. They still take the number of
birds and the old pole as before, but then they check if landing that many birds
on the pole would throw Pierre off balance. We use guards to check if the
difference between the number of birds on the new pole is less than 4. If it is,
we wrap the new pole in a <span class="fixed">Just</span> and return that. If it
isn't, we return a <span class="fixed">Nothing</span>, indicating failure.
</p>
<p>
Let's give these babies a go:
</p>
<pre name="code" class="haskell:hs">
ghci> landLeft 2 (0,0)
Just (2,0)
ghci> landLeft 10 (0,3)
Nothing
</pre>
<p>
Nice! When we land birds without throwing Pierre off balance, we get a new pole
wrapped in a <span class="fixed">Just</span>. But when many more birds end up on
one side of the pole, we get a <span class="fixed">Nothing</span>. This is cool,
but we seem to have lost the ability to repeatedly land birds on the pole. We
can't do <span class="fixed">landLeft 1 (landRight 1 (0,0))</span> any more
because when we apply <span class="fixed">landRight 1</span> to <span
class="fixed">(0,0)</span>, we don't get a <span class="fixed">Pole</span>, but
a <span class="fixed">Maybe Pole</span>. <span class="fixed">landLeft 1</span>
takes a <span class="fixed">Pole</span> and not a <span class="fixed">Maybe
Pole</span>.
</p>
<p>
We need a way of taking a <span class="fixed">Maybe Pole</span> and feeding it
to a function that takes a <span class="fixed">Pole</span> and returns a <span
class="fixed">Maybe Pole</span>. Luckily, we have <span class="fixed">>>=</span>,
which does just that for <span class="fixed">Maybe</span>. Let's give it a go:
</p>
<pre name="code" class="haskell:hs">
ghci> landRight 1 (0,0) >>= landLeft 2
Just (2,1)
</pre>
<p>
Remember, <span class="fixed">landLeft 2</span> has a type of <span
class="fixed">Pole -> Maybe Pole</span>. We couldn't just feed it the <span
class="fixed">Maybe Pole</span> that is the result of <span
class="fixed">landRight 1 (0,0)</span>, so we use <span class="fixed">>>=</span> to take that value with a context and give
it to <span class="fixed">landLeft 2</span>. <span
class="fixed">>>=</span> does indeed allow us to treat the <span
class="fixed">Maybe</span> value as a value with context because if we feed a
<span class="fixed">Nothing</span> into <span class="fixed">landLeft 2</span>,
the result is <span class="fixed">Nothing</span> and the failure is propagated:
</p>
<pre name="code" class="haskell:hs">
ghci> Nothing >>= landLeft 2
Nothing
</pre>
<p>
With this, we can now chain landings that may fail because <span
class="fixed">>>=</span> allows us to feed a
monadic value to a function that takes a normal one.
</p>
<p>
Here's a sequence of birdy landings:
</p>
<pre name="code" class="haskell:hs">
ghci> return (0,0) >>= landRight 2 >>= landLeft 2 >>= landRight 2
Just (2,4)
</pre>
<p>
At the beginning, we used <span class="fixed">return</span> to take a pole and
wrap it in a <span class="fixed">Just</span>. We could have just applied <span
class="fixed">landRight 2</span> to <span class="fixed">(0,0)</span>, it would
have been the same, but this way we can be more consistent by using <span class="fixed">>>=</span>
for every function.
<span class="fixed">Just (0,0)</span> gets fed to <span class="fixed">landRight
2</span>, resulting in <span class="fixed">Just (0,2)</span>. This, in turn,
gets fed to <span class="fixed">landLeft 2</span>, resulting in <span
class="fixed">Just (2,2)</span>, and so on.
</p>
<p>
Remember this example from before we introduced failure into Pierre's routine:
</p>
<pre name="code" class="haskell:hs">
ghci> (0,0) -: landLeft 1 -: landRight 4 -: landLeft (-1) -: landRight (-2)
(0,2)
</pre>
<p>
It didn't simulate his interaction with birds very well because in the middle
there his balance was off but the result didn't reflect that. But let's give
that a go now by using monadic application (<span class="fixed">>>=</span>)
instead of normal application:
</p>
<pre name="code" class="haskell:hs">
ghci> return (0,0) >>= landLeft 1 >>= landRight 4 >>= landLeft (-1) >>= landRight (-2)
Nothing
</pre>
<img src="assets/images/a-fistful-of-monads/banana.png" alt="iama banana" class="right" width="262" height="130">
<p>
Awesome. The final result represents failure, which is what we expected. Let's
see how this result was obtained. First, <span class="fixed">return</span> puts
<span class="fixed">(0,0)</span> into a default context, making it a <span
class="fixed">Just (0,0)</span>. Then, <span class="fixed">Just (0,0) >>=
landLeft 1</span> happens. Since the <span class="fixed">Just (0,0)</span> is a <span
class="fixed">Just</span> value, <span class="fixed">landLeft 1</span> gets applied
to <span class="fixed">(0,0)</span>, resulting in a <span class="fixed">Just
(1,0)</span>, because the birds are still relatively balanced. Next, <span
class="fixed">Just (1,0) >>= landRight 4</span> takes place and the
result is <span class="fixed">Just (1,4)</span> as the balance of the birds is
still intact, although just barely. <span class="fixed">Just (1,4)</span> gets
fed to <span class="fixed">landLeft (-1)</span>. This means that <span
class="fixed">landLeft (-1) (1,4)</span> takes place. Now because of how <span
class="fixed">landLeft</span> works, this results in a <span
class="fixed">Nothing</span>, because the resulting pole is off balance. Now
that we have a <span class="fixed">Nothing</span>, it gets fed to <span
class="fixed">landRight (-2)</span>, but because it's a <span
class="fixed">Nothing</span>, the result is automatically <span
class="fixed">Nothing</span>, as we have nothing to apply <span
class="fixed">landRight (-2)</span> to.
</p>
<p>
We couldn't have achieved this by just using <span class="fixed">Maybe</span>
as an applicative. If you try it, you'll get stuck, because applicative functors
don't allow for the applicative values to interact with each other very much.
They can, at best, be used as parameters to a function by using the applicative
style. The applicative operators will fetch their results and feed them to the
function in a manner appropriate for each applicative and then put the final
applicative value together, but there isn't that much interaction going on
between them. Here, however, each step relies on the previous one's result. On
every landing, the possible result from the previous one is examined and the
pole is checked for balance. This determines whether the landing will succeed or
fail.
</p>
<p>
We may also devise a function that ignores the current number of birds on the
balancing pole and just makes Pierre slip and fall. We can call it <span
class="fixed">banana</span>:
</p>
<pre name="code" class="haskell:hs">
banana :: Pole -> Maybe Pole
banana _ = Nothing
</pre>
<p>
Now we can chain it together with our bird landings. It will always cause our walker
to fall, because it ignores whatever is passed to it and always returns a
failure. Check it:
</p>
<pre name="code" class="haskell:hs">
ghci> return (0,0) >>= landLeft 1 >>= banana >>= landRight 1
Nothing
</pre>
<p>
The value <span class="fixed">Just (1,0)</span> gets fed to <span
class="fixed">banana</span>, but it produces a <span class="fixed">Nothing</span>, which
causes everything to result in a <span class="fixed">Nothing</span>. How
unfortunate!
</p>
<p>
Instead of making functions that ignore their input and just return a
predetermined monadic value, we can use the <span class="fixed">>></span>
function, whose default implementation is this:
</p>
<pre name="code" class="haskell:hs">
(>>) :: (Monad m) => m a -> m b -> m b
m >> n = m >>= \_ -> n
</pre>
<p>
Normally, passing some value to a function that ignores its parameter and always
just returns some predetermined value would always result in that predetermined value. With
monads however, their context and meaning has to be considered as well. Here's
how <span class="fixed">>></span> acts with <span class="fixed">Maybe</span>:
</p>
<pre name="code" class="haskell:hs">
ghci> Nothing >> Just 3
Nothing
ghci> Just 3 >> Just 4
Just 4
ghci> Just 3 >> Nothing
Nothing
</pre>
<p>
If you replace <span class="fixed">>></span> with <span class="fixed">>>=
\_ -></span>, it's easy to see why it acts like it does.
</p>
<p>
We can replace our <span class="fixed">banana</span> function in the chain with a <span class="fixed">>></span> and then a <span class="fixed">Nothing</span>:
</p>
<pre name="code" class="haskell:hs">
ghci> return (0,0) >>= landLeft 1 >> Nothing >>= landRight 1
Nothing
</pre>
<p>
There we go, guaranteed and obvious failure!
</p>
<p>
It's also worth taking a look at what this would look like if we hadn't made the
clever choice of treating <span class="fixed">Maybe</span> values as values with
a failure context and feeding them to functions like we did. Here's how a
series of bird landings would look like:
</p>
<pre name="code" class="haskell:hs">
routine :: Maybe Pole
routine = case landLeft 1 (0,0) of
Nothing -> Nothing
Just pole1 -> case landRight 4 pole1 of
Nothing -> Nothing
Just pole2 -> case landLeft 2 pole2 of
Nothing -> Nothing
Just pole3 -> landLeft 1 pole3
</pre>
<img src="assets/images/a-fistful-of-monads/centaur.png" alt="john joe glanton" class="right" width="297" height="331">
<p>
We land a bird on the left and then we examine the possibility of failure and
the possibility of success. In the case of failure, we return a <span
class="fixed">Nothing</span>. In the case of success, we land birds on the
right and then do the same thing all over again. Converting this monstrosity
into a neat chain of monadic applications with <span class="fixed">>>=</span>
is a classic example of how the <span class="fixed">Maybe</span> monad saves us
a lot of time when we have to successively do computations that are based on
computations that might have failed.
</p>
<p>
Notice how the <span class="fixed">Maybe</span> implementation of <span
class="fixed">>>=</span> features exactly this logic of seeing if a value
is <span class="fixed">Nothing</span> and if it is, returning a <span
class="fixed">Nothing</span> right away and if it isn't, going forward with what's
inside the <span class="fixed">Just</span>.
</p>
<p>
In this section, we took some functions that we had and saw that they would work
better if the values that they returned supported failure. By turning those
values into <span class="fixed">Maybe</span> values and replacing normal
function application with <span class="fixed">>>=</span>, we got a
mechanism for handling failure pretty much for free, because <span
class="fixed">>>=</span> is supposed to preserve the context of the value
to which it applies functions. In this case, the context was that our values
were values with failure and so when we applied functions to such values, the
possibility of failure was always taken into account.
</p>
<a name="do-notation"></a>
<h2>do notation</h2>
<p>
Monads in Haskell are so useful that they got their own special syntax called
<span class="fixed">do</span> notation. We've already encountered <span
class="fixed">do</span> notation when we were doing I/O and there we said that
it was for gluing together several I/O actions into one. Well, as it turns out,
<span class="fixed">do</span> notation isn't just for <span class="fixed">IO</span>, but can be used
for any monad. Its principle is still the same: gluing together monadic
values in sequence. We're going to take a look at how <span
class="fixed">do</span> notation works and why it's useful.
</p>
<p>
Consider this familiar example of monadic application:
</p>
<pre name="code" class="haskell:hs">
ghci> Just 3 >>= (\x -> Just (show x ++ "!"))
Just "3!"
</pre>
<p>
Been there, done that. Feeding a monadic value to a function that returns one,
no big deal. Notice how when we do this, <span class="fixed">x</span> becomes
<span class="fixed">3</span> inside the lambda. Once we're inside that lambda,
it's just a normal value rather than a monadic value. Now, what if we had another
<span class="fixed">>>=</span>
inside that function? Check this out:
</p>
<pre name="code" class="haskell:hs">
ghci> Just 3 >>= (\x -> Just "!" >>= (\y -> Just (show x ++ y)))
Just "3!"
</pre>
<p>
Ah, a nested use of <span class="fixed">>>=</span>! In the outermost