-
Notifications
You must be signed in to change notification settings - Fork 68
Expand file tree
/
Copy patha-fistful-of-monads.html
More file actions
1341 lines (1337 loc) · 75.3 KB
/
a-fistful-of-monads.html
File metadata and controls
1341 lines (1337 loc) · 75.3 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 id="a-fistful-of-monads">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>
<p><img src="assets/images/a-fistful-of-monads/smugpig.png"
class="right" width="307" height="186" alt="more cool than u" /></p>
<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
<code>Functor</code> type class was introduced and it had us asking the
question: when we have a function of type <code>a -> b</code> and
some data type <code>f a</code>, how do we map that function over the
data type to end up with <code>f b</code>? We saw how to map something
over a <code>Maybe a</code>, a list <code>[a]</code>, an
<code>IO a</code> etc. We even saw how to map a function
<code>a -> b</code> over other functions of type
<code>r -> a</code> to get functions of type <code>r -> b</code>.
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 <code>fmap</code>:</p>
<pre class="haskell:hs"><code>fmap :: (Functor f) => (a -> b) -> f a -> f b</code></pre>
<p>And then make it work for our data type by writing the appropriate
<code>Functor</code> instance.</p>
<p>Then we saw a possible improvement of functors and said, hey, what if
that function <code>a -> b</code> is already wrapped inside a functor
value? Like, what if we have <code>Just (*3)</code>, how do we apply
that to <code>Just 5</code>? What if we don’t want to apply it to
<code>Just 5</code> but to a <code>Nothing</code> instead? Or if we have
<code>[(*2),(+4)]</code>, how would we apply that to
<code>[1,2,3]</code>? How would that work even? For this, the
<code>Applicative</code> type class was introduced, in which we wanted
the answer to the following type:</p>
<pre class="haskell:hs"><code>(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b</code></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 <code>1</code> and wrap it so that it
becomes a <code>Just 1</code>. Or we can make it into a
<code>[1]</code>. Or an I/O action that does nothing and just yields
<code>1</code>. The function that does this is called
<code>pure</code>.</p>
<p>Like we said, an applicative value can be seen as a value with an
added context. A <em>fancy</em> value, to put it in technical terms. For
instance, the character <code>'a'</code> is just a normal character,
whereas <code>Just 'a'</code> has some added context. Instead of a
<code>Char</code>, we have a <code>Maybe Char</code>, 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 <code>Applicative</code> type class
allowed us to use normal functions on these values with context and how
that context was preserved. Observe:</p>
<pre class="haskell:hs"><code>ghci> (*) <$> Just 2 <*> Just 8
Just 16
ghci> (++) <$> Just "klingon" <*> Nothing
Nothing
ghci> (-) <$> [3,4] <*> [1,2,3]
[2,1,0,3,2,1]</code></pre>
<p>Ah, cool, so now that we treat them as applicative values,
<code>Maybe a</code> values represent computations that might have
failed, <code>[a]</code> values represent computations that have several
results (non-deterministic computations), <code>IO a</code> 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,
<code>m a</code>, how do you apply to it a function that takes a normal
<code>a</code> and returns a value with a context? That is, how do you
apply a function of type <code>a -> m b</code> to a value of type
<code>m a</code>? So essentially, we will want this function:</p>
<pre class="haskell:hs"><code>(>>=) :: (Monad m) => m a -> (a -> m b) -> m b</code></pre>
<p><strong>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?</strong> This is the main question that we will concern
ourselves when dealing with monads. We write <code>m a</code> instead of
<code>f a</code> because the <code>m</code> stands for
<code>Monad</code>, but monads are just applicative functors that
support <code>>>=</code>. The <code>>>=</code> function is
pronounced as <em>bind</em>.</p>
<p>When we have a normal value <code>a</code> and a normal function
<code>a -> b</code> 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>
<h2 id="getting-our-feet-wet-with-maybe">Getting our feet wet with
Maybe</h2>
<p><img src="assets/images/a-fistful-of-monads/buddha.png" class="left"
width="302" height="387" alt="monads, grasshoppa" /></p>
<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, <code>Maybe</code> 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">
<p>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
<code>Applicative</code> instances work and what kind of computations
they represent, because monads are nothing more than taking our existing
applicative knowledge and upgrading it.</p>
</div>
<p>A value of type <code>Maybe a</code> represents a value of type
<code>a</code> with the context of possible failure attached. A value of
<code>Just "dharma"</code> means that the string <code>"dharma"</code>
is there whereas a value of <code>Nothing</code> 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 <code>Maybe</code> as a functor, we saw that if we
want to <code>fmap</code> a function over it, it gets mapped over the
insides if it’s a <code>Just</code> value, otherwise the
<code>Nothing</code> is kept because there’s nothing to map it over!</p>
<p>Like this:</p>
<pre class="haskell:hs"><code>ghci> fmap (++"!") (Just "wisdom")
Just "wisdom!"
ghci> fmap (++"!") Nothing
Nothing</code></pre>
<p>As an applicative functor, it functions similarly. However,
applicatives also have the function wrapped. <code>Maybe</code> is an
applicative functor in such a way that when we use
<code><*></code> to apply a function inside a <code>Maybe</code>
to a value that’s inside a <code>Maybe</code>, they both have to be
<code>Just</code> values for the result to be a <code>Just</code> value,
otherwise the result is <code>Nothing</code>. 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 class="haskell:hs"><code>ghci> Just (+3) <*> Just 3
Just 6
ghci> Nothing <*> Just "greed"
Nothing
ghci> Just ord <*> Nothing
Nothing</code></pre>
<p>When we use the applicative style to have normal functions act on
<code>Maybe</code> values, it’s similar. All the values have to be
<code>Just</code> values, otherwise it’s all for
<code>Nothing</code>!</p>
<pre class="haskell:hs"><code>ghci> max <$> Just 3 <*> Just 6
Just 6
ghci> max <$> Just 3 <*> Nothing
Nothing</code></pre>
<p>And now, let’s think about how we would do <code>>>=</code> for
<code>Maybe</code>. Like we said, <code>>>=</code> 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, <code>>>=</code> would take a
<code>Maybe a</code> value and a function of type
<code>a -> Maybe b</code> and somehow apply the function to the
<code>Maybe a</code>. To figure out how it does that, we can use the
intuition that we have from <code>Maybe</code> being an applicative
functor. Let’s say that we have a function
<code>\x -> Just (x+1)</code>. It takes a number, adds <code>1</code>
to it and wraps it in a <code>Just</code>:</p>
<pre class="haskell:hs"><code>ghci> (\x -> Just (x+1)) 1
Just 2
ghci> (\x -> Just (x+1)) 100
Just 101</code></pre>
<p>If we feed it <code>1</code>, it evaluates to <code>Just 2</code>. If
we give it the number <code>100</code>, the result is
<code>Just 101</code>. Very straightforward. Now here’s the kicker: how
do we feed a <code>Maybe</code> value to this function? If we think
about how <code>Maybe</code> acts as an applicative functor, answering
this is pretty easy. If we feed it a <code>Just</code> value, take
what’s inside the <code>Just</code> and apply the function to it. If
give it a <code>Nothing</code>, hmm, well, then we’re left with a
function but <code>Nothing</code> to apply it to. In that case, let’s
just do what we did before and say that the result is
<code>Nothing</code>.</p>
<p>Instead of calling it <code>>>=</code>, let’s call it
<code>applyMaybe</code> for now. It takes a <code>Maybe a</code> and a
function that returns a <code>Maybe b</code> and manages to apply that
function to the <code>Maybe a</code>. Here it is in code:</p>
<pre class="haskell:hs"><code>applyMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b
applyMaybe Nothing f = Nothing
applyMaybe (Just x) f = f x</code></pre>
<p>Okay, now let’s play with it for a bit. We’ll use it as an infix
function so that the <code>Maybe</code> value is on the left side and
the function on the right:</p>
<pre class="haskell:hs"><code>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</code></pre>
<p>In the above example, we see that when we used
<code>applyMaybe</code> with a <code>Just</code> value and a function,
the function simply got applied to the value inside the
<code>Just</code>. When we tried to use it with a <code>Nothing</code>,
the whole result was <code>Nothing</code>. What about if the function
returns a <code>Nothing</code>? Let’s see:</p>
<pre class="haskell:hs"><code>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</code></pre>
<p>Just what we expected. If the monadic value on the left is a
<code>Nothing</code>, the whole thing is <code>Nothing</code>. And if
the function on the right returns a <code>Nothing</code>, the result is
<code>Nothing</code> again. This is very similar to when we used
<code>Maybe</code> as an applicative and we got a <code>Nothing</code>
result if somewhere in there was a <code>Nothing</code>.</p>
<p>It looks like that for <code>Maybe</code>, 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
<code>Maybe</code> 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 <code>Maybe</code> in a minute, but first, let’s
check out the type class that belongs to monads.</p>
<h2 id="the-monad-type-class">The Monad type class</h2>
<p>Just like functors have the <code>Functor</code> type class and
applicative functors have the <code>Applicative</code> type class,
monads come with their own type class: <code>Monad</code>! Wow, who
would have thought? This is what the type class looks like:</p>
<pre class="haskell:hs"><code>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</code></pre>
<p><img src="assets/images/a-fistful-of-monads/kid.png" class="right"
width="363" height="451" alt="this is you on monads" /></p>
<p>Let’s start with the first line. It says
<code>class Applicative => Monad m where</code> 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 <code>Monad</code> type class defines is
<code>return</code>. It’s the same as <code>pure</code>, only with a
different name. Its type is <code>(Monad m) => a -> m a</code>. 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 <code>pure</code> function from the
<code>Applicative</code> type class, which means we’re already
acquainted with <code>return</code>. We already used <code>return</code>
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 <code>Maybe</code> it takes
a value and wraps it in a <code>Just</code>.</p>
<div class="hintbox">
<p>Just a reminder: <code>return</code> is nothing like the
<code>return</code> 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.</p>
</div>
<p><img src="assets/images/a-fistful-of-monads/tur2.png" class="left"
width="169" height="145" alt="hmmm yaes" /></p>
<p>The next function is <code>>>=</code>, 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 <code>>></code>. 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 <code>Monad</code>
instances.</p>
<p>Now that we know what the <code>Monad</code> type class looks like,
let’s take a look at how <code>Maybe</code> is an instance of
<code>Monad</code>!</p>
<pre class="haskell:hs"><code>instance Monad Maybe where
Nothing >>= f = Nothing
Just x >>= f = f x</code></pre>
<p>Both <code>return</code> and <code>(>>)</code> have <em>default
implementations</em>, so we omit them in instances. <code>return</code>
is the same as <code>pure</code>, it wraps a value in
<code>Just</code>.</p>
<p>The <code>>>=</code> function is the same as our
<code>applyMaybe</code>. When feeding the <code>Maybe a</code> to our
function, we keep in mind the context and return a <code>Nothing</code>
if the value on the left is <code>Nothing</code> because if there’s no
value then there’s no way to apply our function to it. If it’s a
<code>Just</code> we take what’s inside and apply <code>f</code> to
it.</p>
<p>We can play around with <code>Maybe</code> as a monad:</p>
<pre class="haskell:hs"><code>ghci> return "WHAT" :: Maybe String
Just "WHAT"
ghci> Just 9 >>= \x -> return (x*10)
Just 90
ghci> Nothing >>= \x -> return (x*10)
Nothing</code></pre>
<p>Nothing new or exciting on the first line since we already used
<code>pure</code> with <code>Maybe</code> and we know that
<code>return</code> is just <code>pure</code> with a different name. The
next two lines showcase <code>>>=</code> a bit more.</p>
<p>Notice how when we fed <code>Just 9</code> to the function
<code>\x -> return (x*10)</code>, the <code>x</code> took on the
value <code>9</code> inside the function. It seems as though we were
able to extract the value from a <code>Maybe</code> without
pattern-matching. And we still didn’t lose the context of our
<code>Maybe</code> value, because when it’s <code>Nothing</code>, the
result of using <code>>>=</code> will be <code>Nothing</code> as
well.</p>
<h2 id="walk-the-line">Walk the line</h2>
<p><img src="assets/images/a-fistful-of-monads/pierre.png" class="left"
width="374" height="405" alt="pierre" /></p>
<p>Now that we know how to feed a <code>Maybe a</code> value to a
function of type <code>a -> Maybe b</code> while taking into account
the context of possible failure, let’s see how we can use
<code>>>=</code> repeatedly to handle computations of several
<code>Maybe a</code> 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 class="haskell:hs"><code>type Birds = Int
type Pole = (Birds,Birds)</code></pre>
<p>First we made a type synonym for <code>Int</code>, called
<code>Birds</code>, because we’re using integers to represent how many
birds there are. And then we made a type synonym
<code>(Birds,Birds)</code> and we called it <code>Pole</code> (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 class="haskell:hs"><code>landLeft :: Birds -> Pole -> Pole
landLeft n (left,right) = (left + n,right)
landRight :: Birds -> Pole -> Pole
landRight n (left,right) = (left,right + n)</code></pre>
<p>Pretty straightforward stuff. Let’s try them out:</p>
<pre class="haskell:hs"><code>ghci> landLeft 2 (0,0)
(2,0)
ghci> landRight 1 (1,2)
(1,3)
ghci> landRight (-1) (1,2)
(1,1)</code></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 <code>Pole</code> returns a
<code>Pole</code>, we can chain applications of <code>landLeft</code>
and <code>landRight</code>:</p>
<pre class="haskell:hs"><code>ghci> landLeft 2 (landRight 1 (landLeft 1 (0,0)))
(3,1)</code></pre>
<p>When we apply the function <code>landLeft 1</code> to
<code>(0,0)</code> we get <code>(1,0)</code>. Then, we land a bird on
the right side, resulting in <code>(1,1)</code>. Finally two birds land
on the left side, resulting in <code>(3,1)</code>. 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 class="haskell:hs"><code>x -: f = f x</code></pre>
<p>We can apply functions by first writing the parameter and then the
function:</p>
<pre class="haskell:hs"><code>ghci> 100 -: (*3)
300
ghci> True -: not
False
ghci> (0,0) -: landLeft 2
(2,0)</code></pre>
<p>By using this, we can repeatedly land birds on the pole in a more
readable manner:</p>
<pre class="haskell:hs"><code>ghci> (0,0) -: landLeft 1 -: landRight 1 -: landLeft 2
(3,1)</code></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 <code>(0,0)</code> 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 class="haskell:hs"><code>ghci> landLeft 10 (0,3)
(10,3)</code></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 class="haskell:hs"><code>ghci> (0,0) -: landLeft 1 -: landRight 4 -: landLeft (-1) -: landRight (-2)
(0,2)</code></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 <code>landLeft</code> and <code>landRight</code> 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 <code>Maybe</code>! Let’s rework these
functions:</p>
<pre class="haskell:hs"><code>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</code></pre>
<p>Instead of returning a <code>Pole</code> these functions now return a
<code>Maybe Pole</code>. 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 <code>Just</code> and return that.
If it isn’t, we return a <code>Nothing</code>, indicating failure.</p>
<p>Let’s give these babies a go:</p>
<pre class="haskell:hs"><code>ghci> landLeft 2 (0,0)
Just (2,0)
ghci> landLeft 10 (0,3)
Nothing</code></pre>
<p>Nice! When we land birds without throwing Pierre off balance, we get
a new pole wrapped in a <code>Just</code>. But when many more birds end
up on one side of the pole, we get a <code>Nothing</code>. This is cool,
but we seem to have lost the ability to repeatedly land birds on the
pole. We can’t do <code>landLeft 1 (landRight 1 (0,0))</code> anymore
because when we apply <code>landRight 1</code> to <code>(0,0)</code>, we
don’t get a <code>Pole</code>, but a <code>Maybe Pole</code>.
<code>landLeft 1</code> takes a <code>Pole</code> and not a
<code>Maybe Pole</code>.</p>
<p>We need a way of taking a <code>Maybe Pole</code> and feeding it to a
function that takes a <code>Pole</code> and returns a
<code>Maybe Pole</code>. Luckily, we have <code>>>=</code>, which
does just that for <code>Maybe</code>. Let’s give it a go:</p>
<pre class="haskell:hs"><code>ghci> landRight 1 (0,0) >>= landLeft 2
Just (2,1)</code></pre>
<p>Remember, <code>landLeft 2</code> has a type of
<code>Pole -> Maybe Pole</code>. We couldn’t just feed it the
<code>Maybe Pole</code> that is the result of
<code>landRight 1 (0,0)</code>, so we use <code>>>=</code> to take
that value with a context and give it to <code>landLeft 2</code>.
<code>>>=</code> does indeed allow us to treat the
<code>Maybe</code> value as a value with context because if we feed a
<code>Nothing</code> into <code>landLeft 2</code>, the result is
<code>Nothing</code> and the failure is propagated:</p>
<pre class="haskell:hs"><code>ghci> Nothing >>= landLeft 2
Nothing</code></pre>
<p>With this, we can now chain landings that may fail because
<code>>>=</code> 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 class="haskell:hs"><code>ghci> return (0,0) >>= landRight 2 >>= landLeft 2 >>= landRight 2
Just (2,4)</code></pre>
<p>At the beginning, we used <code>return</code> to take a pole and wrap
it in a <code>Just</code>. We could have just applied
<code>landRight 2</code> to <code>(0,0)</code>, it would have been the
same, but this way we can be more consistent by using
<code>>>=</code> for every function. <code>Just (0,0)</code> gets
fed to <code>landRight 2</code>, resulting in <code>Just (0,2)</code>.
This, in turn, gets fed to <code>landLeft 2</code>, resulting in
<code>Just (2,2)</code>, and so on.</p>
<p>Remember this example from before we introduced failure into Pierre’s
routine:</p>
<pre class="haskell:hs"><code>ghci> (0,0) -: landLeft 1 -: landRight 4 -: landLeft (-1) -: landRight (-2)
(0,2)</code></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
(<code>>>=</code>) instead of normal application:</p>
<pre class="haskell:hs"><code>ghci> return (0,0) >>= landLeft 1 >>= landRight 4 >>= landLeft (-1) >>= landRight (-2)
Nothing</code></pre>
<p><img src="assets/images/a-fistful-of-monads/banana.png" class="right"
width="262" height="130" alt="iama banana" /></p>
<p>Awesome. The final result represents failure, which is what we
expected. Let’s see how this result was obtained. First,
<code>return</code> puts <code>(0,0)</code> into a default context,
making it a <code>Just (0,0)</code>. Then,
<code>Just (0,0) >>= landLeft 1</code> happens. Since the
<code>Just (0,0)</code> is a <code>Just</code> value,
<code>landLeft 1</code> gets applied to <code>(0,0)</code>, resulting in
a <code>Just (1,0)</code>, because the birds are still relatively
balanced. Next, <code>Just (1,0) >>= landRight 4</code> takes
place and the result is <code>Just (1,4)</code> as the balance of the
birds is still intact, although just barely. <code>Just (1,4)</code>
gets fed to <code>landLeft (-1)</code>. This means that
<code>landLeft (-1) (1,4)</code> takes place. Now because of how
<code>landLeft</code> works, this results in a <code>Nothing</code>,
because the resulting pole is off balance. Now that we have a
<code>Nothing</code>, it gets fed to <code>landRight (-2)</code>, but
because it’s a <code>Nothing</code>, the result is automatically
<code>Nothing</code>, as we have nothing to apply
<code>landRight (-2)</code> to.</p>
<p>We couldn’t have achieved this by just using <code>Maybe</code> 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 <code>banana</code>:</p>
<pre class="haskell:hs"><code>banana :: Pole -> Maybe Pole
banana _ = Nothing</code></pre>
<p>Now we can chain it together with our bird landings. It will always
cause our walker to fall, because it ignores whatever’s passed to it and
always returns a failure. Check it:</p>
<pre class="haskell:hs"><code>ghci> return (0,0) >>= landLeft 1 >>= banana >>= landRight 1
Nothing</code></pre>
<p>The value <code>Just (1,0)</code> gets fed to <code>banana</code>,
but it produces a <code>Nothing</code>, which causes everything to
result in a <code>Nothing</code>. How unfortunate!</p>
<p>Instead of making functions that ignore their input and just return a
predetermined monadic value, we can use the <code>>></code>
function, whose default implementation is this:</p>
<pre class="haskell:hs"><code>(>>) :: (Monad m) => m a -> m b -> m b
m >> n = m >>= \_ -> n</code></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 <code>>></code> acts with
<code>Maybe</code>:</p>
<pre class="haskell:hs"><code>ghci> Nothing >> Just 3
Nothing
ghci> Just 3 >> Just 4
Just 4
ghci> Just 3 >> Nothing
Nothing</code></pre>
<p>If you replace <code>>></code> with
<code>>>= \_ -></code>, it’s easy to see why it acts like it
does.</p>
<p>We can replace our <code>banana</code> function in the chain with a
<code>>></code> and then a <code>Nothing</code>:</p>
<pre class="haskell:hs"><code>ghci> return (0,0) >>= landLeft 1 >> Nothing >>= landRight 1
Nothing</code></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 <code>Maybe</code> 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 class="haskell:hs"><code>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</code></pre>
<p><img src="assets/images/a-fistful-of-monads/centaur.png"
class="right" width="297" height="331" alt="john joe glanton" /></p>
<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 <code>Nothing</code>. 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
<code>>>=</code> is a classic example of how the
<code>Maybe</code> 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 <code>Maybe</code> implementation of
<code>>>=</code> features exactly this logic of seeing if a value
is <code>Nothing</code> and if it is, returning a <code>Nothing</code>
right away and if it isn’t, going forward with what’s inside the
<code>Just</code>.</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 <code>Maybe</code> values and replacing normal
function application with <code>>>=</code>, we got a mechanism for
handling failure pretty much for free, because <code>>>=</code> 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>
<h2 id="do-notation">do notation</h2>
<p>Monads in Haskell are so useful that they got their own special
syntax called <code>do</code> notation. We’ve already encountered
<code>do</code> 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, <code>do</code> notation isn’t just for <code>IO</code>, 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
<code>do</code> notation works and why it’s useful.</p>
<p>Consider this familiar example of monadic application:</p>
<pre class="haskell:hs"><code>ghci> Just 3 >>= (\x -> Just (show x ++ "!"))
Just "3!"</code></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, <code>x</code>
becomes <code>3</code> 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 <code>>>=</code> inside that function? Check this
out:</p>
<pre class="haskell:hs"><code>ghci> Just 3 >>= (\x -> Just "!" >>= (\y -> Just (show x ++ y)))
Just "3!"</code></pre>
<p>Ah, a nested use of <code>>>=</code>! In the outermost lambda,
we feed <code>Just "!"</code> to the lambda
<code>\y -> Just (show x ++ y)</code>. Inside this lambda, the
<code>y</code> becomes <code>"!"</code>. <code>x</code> is still
<code>3</code> because we got it from the outer lambda. All this sort of
reminds me of the following expression:</p>
<pre class="haskell:hs"><code>ghci> let x = 3; y = "!" in show x ++ y
"3!"</code></pre>
<p>The main difference between these two is that the values in the
former example are monadic. They’re values with a failure context. We
can replace any of them with a failure:</p>
<pre class="haskell:hs"><code>ghci> Nothing >>= (\x -> Just "!" >>= (\y -> Just (show x ++ y)))
Nothing
ghci> Just 3 >>= (\x -> Nothing >>= (\y -> Just (show x ++ y)))
Nothing
ghci> Just 3 >>= (\x -> Just "!" >>= (\y -> Nothing))
Nothing</code></pre>
<p>In the first line, feeding a <code>Nothing</code> to a function
naturally results in a <code>Nothing</code>. In the second line, we feed
<code>Just 3</code> to a function and the <code>x</code> becomes
<code>3</code>, but then we feed a <code>Nothing</code> to the inner
lambda and the result of that is <code>Nothing</code>, which causes the
outer lambda to produce <code>Nothing</code> as well. So this is sort of
like assigning values to variables in <code>let</code> expressions, only
that the values in question are monadic values.</p>
<p>To further illustrate this point, let’s write this in a script and
have each <code>Maybe</code> value take up its own line:</p>
<pre class="haskell:hs"><code>foo :: Maybe String
foo = Just 3 >>= (\x ->
Just "!" >>= (\y ->
Just (show x ++ y)))</code></pre>
<p>To save us from writing all these annoying lambdas, Haskell gives us
<code>do</code> notation. It allows us to write the previous piece of
code like this:</p>
<pre class="haskell:hs"><code>foo :: Maybe String
foo = do
x <- Just 3
y <- Just "!"
Just (show x ++ y)</code></pre>
<p><img src="assets/images/a-fistful-of-monads/owld.png" class="right"
width="269" height="348" alt="90s owl" /></p>
<p>It would seem as though we’ve gained the ability to temporarily
extract things from <code>Maybe</code> values without having to check if
the <code>Maybe</code> values are <code>Just</code> values or
<code>Nothing</code> values at every step. How cool! If any of the
values that we try to extract from are <code>Nothing</code>, the whole
<code>do</code> expression will result in a <code>Nothing</code>. We’re
yanking out their (possibly existing) values and letting
<code>>>=</code> worry about the context that comes with those
values. It’s important to remember that <code>do</code> expressions are
just different syntax for chaining monadic values.</p>
<p>In a <code>do</code> expression, every line is a monadic value. To
inspect its result, we use <code><-</code>. If we have a
<code>Maybe String</code> and we bind it with <code><-</code> to a
variable, that variable will be a <code>String</code>, just like when we
used <code>>>=</code> to feed monadic values to lambdas. The last
monadic value in a <code>do</code> expression, like
<code>Just (show x ++ y)</code> here, can’t be used with
<code><-</code> to bind its result, because that wouldn’t make sense
if we translated the <code>do</code> expression back to a chain of
<code>>>=</code> applications. Rather, its result is the result of
the whole glued up monadic value, taking into account the possible
failure of any of the previous ones.</p>
<p>For instance, examine the following line:</p>
<pre class="haskell:hs"><code>ghci> Just 9 >>= (\x -> Just (x > 8))
Just True</code></pre>
<p>Because the left parameter of <code>>>=</code> is a
<code>Just</code> value, the lambda is applied to <code>9</code> and the
result is a <code>Just True</code>. If we rewrite this in
<code>do</code> notation, we get:</p>
<pre class="haskell:hs"><code>marySue :: Maybe Bool
marySue = do
x <- Just 9
Just (x > 8)</code></pre>
<p>If we compare these two, it’s easy to see why the result of the whole
monadic value is the result of the last monadic value in the
<code>do</code> expression with all the previous ones chained into
it.</p>
<p>Our tightwalker’s routine can also be expressed with <code>do</code>
notation. <code>landLeft</code> and <code>landRight</code> take a number
of birds and a pole and produce a pole wrapped in a <code>Just</code>,
unless the tightwalker slips, in which case a <code>Nothing</code> is
produced. We used <code>>>=</code> to chain successive steps
because each one relied on the previous one and each one had an added
context of possible failure. Here’s two birds landing on the left side,
then two birds landing on the right and then one bird landing on the
left:</p>
<pre class="haskell:hs"><code>routine :: Maybe Pole
routine = do
start <- return (0,0)
first <- landLeft 2 start
second <- landRight 2 first
landLeft 1 second</code></pre>
<p>Let’s see if he succeeds:</p>
<pre class="haskell:hs"><code>ghci> routine
Just (3,2)</code></pre>
<p>He does! Great. When we were doing these routines by explicitly
writing <code>>>=</code>, we usually said something like
<code>return (0,0) >>= landLeft 2</code>, because
<code>landLeft 2</code> is a function that returns a <code>Maybe</code>
value. With <code>do</code> expressions however, each line must feature
a monadic value. So we explicitly pass the previous <code>Pole</code> to
the <code>landLeft</code> <code>landRight</code> functions. If we
examined the variables to which we bound our <code>Maybe</code> values,
<code>start</code> would be <code>(0,0)</code>, <code>first</code> would
be <code>(2,0)</code> and so on.</p>
<p>Because <code>do</code> expressions are written line by line, they
may look like imperative code to some people. But the thing is, they’re
just sequential, as each value in each line relies on the result of the
previous ones, along with their contexts (in this case, whether they
succeeded or failed).</p>
<p>Again, let’s take a look at what this piece of code would look like
if we hadn’t used the monadic aspects of <code>Maybe</code>:</p>
<pre class="haskell:hs"><code>routine :: Maybe Pole
routine =
case Just (0,0) of
Nothing -> Nothing
Just start -> case landLeft 2 start of
Nothing -> Nothing
Just first -> case landRight 2 first of
Nothing -> Nothing
Just second -> landLeft 1 second</code></pre>
<p>See how in the case of success, the tuple inside
<code>Just (0,0)</code> becomes <code>start</code>, the result of
<code>landLeft 2 start</code> becomes <code>first</code>, etc.</p>
<p>If we want to throw the Pierre a banana peel in <code>do</code>
notation, we can do the following:</p>
<pre class="haskell:hs"><code>routine :: Maybe Pole
routine = do
start <- return (0,0)
first <- landLeft 2 start
Nothing
second <- landRight 2 first
landLeft 1 second</code></pre>
<p>When we write a line in <code>do</code> notation without binding the
monadic value with <code><-</code>, it’s just like putting
<code>>></code> after the monadic value whose result we want to
ignore. We sequence the monadic value but we ignore its result because
we don’t care what it is and it’s prettier than writing
<code>_ <- Nothing</code>, which is equivalent to the above.</p>
<p>When to use <code>do</code> notation and when to explicitly use
<code>>>=</code> is up to you. I think this example lends itself
to explicitly writing <code>>>=</code> because each step relies
specifically on the result of the previous one. With <code>do</code>
notation, we had to specifically write on which pole the birds are
landing, but every time we used that came directly before. But still, it
gave us some insight into <code>do</code> notation.</p>
<p>In <code>do</code> notation, when we bind monadic values to names, we
can utilize pattern matching, just like in <code>let</code> expressions
and function parameters. Here’s an example of pattern matching in a
<code>do</code> expression:</p>
<pre class="haskell:hs"><code>justH :: Maybe Char
justH = do
(x:xs) <- Just "hello"
return x</code></pre>
<p>We use pattern matching to get the first character of the string
<code>"hello"</code> and then we present it as the result. So
<code>justH</code> evaluates to <code>Just 'h'</code>.</p>
<p>What if this pattern matching were to fail? When matching on a
pattern in a function fails, the next pattern is matched. If the
matching falls through all the patterns for a given function, an error
is thrown and our program crashes. On the other hand, failed pattern
matching in <code>let</code> expressions results in an error being
produced right away, because the mechanism of falling through patterns
isn’t present in <code>let</code> expressions. When pattern matching
fails in a <code>do</code> expression, the <code>fail</code> function is
called. It’s part of the <code>MonadFail</code> type class and it
enables failed pattern matching to result in a failure in the context of
the current monad instead of making our program crash.</p>
<pre class="haskell:hs"><code>class Monad m => MonadFail m where
fail :: String -> m a</code></pre>
<p>Monads that incorporate a context of possible failure (like
<code>Maybe</code>) usually implement it. For <code>Maybe</code>, its
implemented like so:</p>
<pre class="haskell:hs"><code>instance MonadFail Maybe where
fail _ = Nothing</code></pre>
<p>It ignores the error message and makes a <code>Nothing</code>. So
when pattern matching fails in a <code>Maybe</code> value that’s written
in <code>do</code> notation, the whole value results in a
<code>Nothing</code>. This is preferable to having our program crash.
Here’s a <code>do</code> expression with a pattern that’s bound to
fail:</p>
<pre class="haskell:hs"><code>wopwop :: Maybe Char
wopwop = do
(x:xs) <- Just ""
return x</code></pre>
<p>The pattern matching fails, so the effect is the same as if the whole
line with the pattern was replaced with a <code>Nothing</code>. Let’s
try this out:</p>
<pre class="haskell:hs"><code>ghci> wopwop
Nothing</code></pre>
<p>The failed pattern matching has caused a failure within the context
of our monad instead of causing a program-wide failure, which is pretty
neat.</p>
<h2 id="the-list-monad">The list monad</h2>
<p><img src="assets/images/a-fistful-of-monads/deadcat.png" class="left"
width="235" height="230" alt="dead cat" /></p>
<p>So far, we’ve seen how <code>Maybe</code> values can be viewed as
values with a failure context and how we can incorporate failure
handling into our code by using <code>>>=</code> to feed them to
functions. In this section, we’re going to take a look at how to use the
monadic aspects of lists to bring non-determinism into our code in a
clear and readable manner.</p>
<p>We’ve already talked about how lists represent non-deterministic
values when they’re used as applicatives. A value like <code>5</code> is
deterministic. It has only one result and we know exactly what it is. On
the other hand, a value like <code>[3,8,9]</code> contains several
results, so we can view it as one value that is actually many values at
the same time. Using lists as applicative functors showcases this
non-determinism nicely:</p>
<pre class="haskell:hs"><code>ghci> (*) <$> [1,2,3] <*> [10,100,1000]
[10,100,1000,20,200,2000,30,300,3000]</code></pre>
<p>All the possible combinations of multiplying elements from the left
list with elements from the right list are included in the resulting
list. When dealing with non-determinism, there are many choices that we
can make, so we just try all of them, and so the result is a
non-deterministic value as well, only it has many more results.</p>
<p>This context of non-determinism translates to monads very nicely.
Let’s go ahead and see what the <code>Monad</code> instance for lists
looks like:</p>
<pre class="haskell:hs"><code>instance Monad [] where
xs >>= f = concat (map f xs)</code></pre>
<p><code>return</code> does the same thing as <code>pure</code>, so we
should already be familiar with <code>return</code> for lists. It takes
a value and puts it in a minimal default context that still yields that
value. In other words, it makes a list that has only that one value as
its result. This is useful for when we want to just wrap a normal value
into a list so that it can interact with non-deterministic values.</p>
<p>To understand how <code>>>=</code> works for lists, it’s best
if we take a look at it in action to gain some intuition first.
<code>>>=</code> is about taking a value with a context (a monadic
value) and feeding it to a function that takes a normal value and
returns one that has context. If that function just produced a normal
value instead of one with a context, <code>>>=</code> wouldn’t be
so useful because after one use, the context would be lost. Anyway,
let’s try feeding a non-deterministic value to a function:</p>
<pre class="haskell:hs"><code>ghci> [3,4,5] >>= \x -> [x,-x]
[3,-3,4,-4,5,-5]</code></pre>
<p>When we used <code>>>=</code> with <code>Maybe</code>, the
monadic value was fed into the function while taking care of possible
failures. Here, it takes care of non-determinism for us.
<code>[3,4,5]</code> is a non-deterministic value and we feed it into a
function that returns a non-deterministic value as well. The result is
also non-deterministic, and it features all the possible results of
taking elements from the list <code>[3,4,5]</code> and passing them to
the function <code>\x -> [x,-x]</code>. This function takes a number
and produces two results: one negated and one that’s unchanged. So when
we use <code>>>=</code> to feed this list to the function, every
number is negated and also kept unchanged. The <code>x</code> from the
lambda takes on every value from the list that’s fed to it.</p>
<p>To see how this is achieved, we can just follow the implementation.
First, we start off with the list <code>[3,4,5]</code>. Then, we map the
lambda over it and the result is the following:</p>
<pre class="haskell:hs"><code>[[3,-3],[4,-4],[5,-5]]</code></pre>
<p>The lambda is applied to every element and we get a list of lists.
Finally, we just flatten the list and voila! We’ve applied a
non-deterministic function to a non-deterministic value!</p>
<p>Non-determinism also includes support for failure. The empty list
<code>[]</code> is pretty much the equivalent of <code>Nothing</code>,
because it signifies the absence of a result. That’s why failing is just
defined as the empty list. The error message gets thrown away. Let’s
play around with lists that fail:</p>
<pre class="haskell:hs"><code>ghci> [] >>= \x -> ["bad","mad","rad"]
[]
ghci> [1,2,3] >>= \x -> []
[]</code></pre>
<p>In the first line, an empty list is fed into the lambda. Because the
list has no elements, none of them can be passed to the function and so
the result is an empty list. This is similar to feeding
<code>Nothing</code> to a function. In the second line, each element
gets passed to the function, but the element is ignored and the function
just returns an empty list. Because the function fails for every element
that goes in it, the result is a failure.</p>
<p>Just like with <code>Maybe</code> values, we can chain several lists
with <code>>>=</code>, propagating the non-determinism:</p>
<pre class="haskell:hs"><code>ghci> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]</code></pre>
<p><img src="assets/images/a-fistful-of-monads/concatmap.png"
class="left" width="399" height="340" alt="concatmap" /></p>
<p>The list <code>[1,2]</code> gets bound to <code>n</code> and
<code>['a','b']</code> gets bound to <code>ch</code>. Then, we do
<code>return (n,ch)</code> (or <code>[(n,ch)]</code>), which means
taking a pair of <code>(n,ch)</code> and putting it in a default minimal
context. In this case, it’s making the smallest possible list that still
presents <code>(n,ch)</code> as the result and features as little
non-determinism as possible. Its effect on the context is minimal. What
we’re saying here is this: for every element in <code>[1,2]</code>, go
over every element in <code>['a','b']</code> and produce a tuple of one
element from each list.</p>
<p>Generally speaking, because <code>return</code> takes a value and
wraps it in a minimal context, it doesn’t have any extra effect (like
failing in <code>Maybe</code> or resulting in more non-determinism for
lists) but it does present something as its result.</p>
<div class="hintbox">
<p>When you have non-deterministic values interacting, you can view
their computation as a tree where every possible result in a list
represents a separate branch.</p>
</div>
<p>Here’s the previous expression rewritten in <code>do</code>
notation:</p>
<pre class="haskell:hs"><code>listOfTuples :: [(Int,Char)]
listOfTuples = do
n <- [1,2]
ch <- ['a','b']
return (n,ch)</code></pre>
<p>This makes it a bit more obvious that <code>n</code> takes on every
value from <code>[1,2]</code> and <code>ch</code> takes on every value
from <code>['a','b']</code>. Just like with <code>Maybe</code>, we’re
extracting the elements from the monadic values and treating them like
normal values and <code>>>=</code> takes care of the context for
us. The context in this case is non-determinism.</p>
<p>Using lists with <code>do</code> notation really reminds me of
something we’ve seen before. Check out the following piece of code:</p>
<pre class="haskell:hs"><code>ghci> [ (n,ch) | n <- [1,2], ch <- ['a','b'] ]
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]</code></pre>
<p>Yes! List comprehensions! In our <code>do</code> notation example,
<code>n</code> became every result from <code>[1,2]</code> and for every
such result, <code>ch</code> was assigned a result from
<code>['a','b']</code> and then the final line put <code>(n,ch)</code>
into a default context (a singleton list) to present it as the result
without introducing any additional non-determinism. In this list
comprehension, the same thing happened, only we didn’t have to write
<code>return</code> at the end to present <code>(n,ch)</code> as the
result because the output part of a list comprehension did that for
us.</p>
<p>In fact, list comprehensions are just syntactic sugar for using lists
as monads. In the end, list comprehensions and lists in <code>do</code>
notation translate to using <code>>>=</code> to do computations
that feature non-determinism.</p>
<p>List comprehensions allow us to filter our output. For instance, we
can filter a list of numbers to search only for that numbers whose
digits contain a <code>7</code>:</p>
<pre class="haskell:hs"><code>ghci> [ x | x <- [1..50], '7' `elem` show x ]
[7,17,27,37,47]</code></pre>
<p>We apply <code>show</code> to <code>x</code> to turn our number into
a string and then we check if the character <code>'7'</code> is part of
that string. Pretty clever. To see how filtering in list comprehensions
translates to the list monad, we have to check out the
<code>guard</code> function and the <code>Alternative</code> type class.
The <code>Alternative</code> type class is for Applicatives that can
also act as monoids. Here’s its definition:</p>
<pre class="haskell:hs"><code>class Applicative f => Alternative f where
empty :: f a
(<|>) :: f a -> f a -> f a</code></pre>
<p><code>empty</code> is synonymous to <code>mempty</code> from the
<code>Monoid</code> type class and <code>(<|>)</code> corresponds
to <code>mappend</code>. Because lists are monoids as well as monads,
they can be made an instance of this type class:</p>
<pre class="haskell:hs"><code>instance Alternative [] where
empty = []
(<|>) = (++)</code></pre>
<p>For lists <code>empty</code> represents a non-deterministic
computation that has no results at all — a failed computation.
<code>(<|>)</code> joins two non-deterministic values into one.
The <code>guard</code> function is defined like this:</p>
<pre class="haskell:hs"><code>guard :: (Alternative m) => Bool -> m ()
guard True = pure ()
guard False = empty</code></pre>
<p>It takes a boolean value and if it’s <code>True</code>, takes a
<code>()</code> and puts it in a minimal default context that still
succeeds. Otherwise, it makes a failed monadic value. Here it is in
action:</p>
<pre class="haskell:hs"><code>ghci> guard (5 > 2) :: Maybe ()
Just ()
ghci> guard (1 > 2) :: Maybe ()
Nothing
ghci> guard (5 > 2) :: [()]
[()]