forked from learnyouahaskell/learnyouahaskell.github.io
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmodules.html
More file actions
941 lines (925 loc) · 73.3 KB
/
modules.html
File metadata and controls
941 lines (925 loc) · 73.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
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN"
"https://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>Modules - 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="higher-order-functions.html">
<link rel="next" href="making-our-own-types-and-typeclasses.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="higher-order-functions.html" class="prevlink">Higher Order Functions</a>
</li>
<li style="text-align:center">
<a href="chapters.html">Table of contents</a>
</li>
<li style="text-align:right">
<a href="making-our-own-types-and-typeclasses.html" class="nxtlink">Making Our Own Types and Typeclasses</a>
</li>
</ul>
</div>
<h1>Modules</h1>
<a name="loading-modules"></a><h2>Loading modules</h2>
<img src="assets/images/modules/modules.png" alt="modules" class="right" width="230" height="162">
<p>A Haskell module is a collection of related functions, types and typeclasses. A Haskell program is a collection of modules where the main module loads up the other modules and then uses the functions defined in them to do something. Having code split up into several modules has quite a lot of advantages. If a module is generic enough, the functions it exports can be used in a multitude of different programs. If your own code is separated into self-contained modules which don't rely on each other too much (we also say they are loosely coupled), you can reuse them later on. It makes the whole deal of writing code more manageable by having it split into several parts, each of which has some sort of purpose.</p>
<p>The Haskell standard library is split into modules, each of them contains functions and types that are somehow related and serve some common purpose. There's a module for manipulating lists, a module for concurrent programming, a module for dealing with complex numbers, etc. All the functions, types and typeclasses that we've dealt with so far were part of the <span class="fixed">Prelude</span> module, which is imported by default. In this chapter, we're going to examine a few useful modules and the functions that they have. But first, we're going to see how to import modules.</p>
<p>The syntax for importing modules in a Haskell script is <span class="fixed">import <module name></span>. This must be done before defining any functions, so imports are usually done at the top of the file. One script can, of course, import several modules. Just put each import statement into a separate line. Let's import the <span class="fixed">Data.List</span> module, which has a bunch of useful functions for working with lists and use a function that it exports to create a function that tells us how many unique elements a list has.</p>
<pre name="code" class="haskell:hs">
import Data.List
numUniques :: (Eq a) => [a] -> Int
numUniques = length . nub
</pre>
<p>When you do <span class="fixed">import Data.List</span>, all the functions that <span class="fixed">Data.List</span> exports become available in the global namespace, meaning that you can call them from wherever in the script. <span class="fixed">nub</span> is a function defined in <span class="fixed">Data.List</span> that takes a list and weeds out duplicate elements. Composing <span class="fixed">length</span> and <span class="fixed">nub</span> by doing <span class="fixed">length . nub</span> produces a function that's the equivalent of <span class="fixed">\xs -> length (nub xs)</span>.</p>
<p>You can also put the functions of modules into the global namespace when using GHCI. If you're in GHCI and you want to be able to call the functions exported by <span class="fixed">Data.List</span>, do this:</p>
<pre name="code" class="haskell:ghci">
ghci> :m + Data.List
</pre>
<p>If we want to load up the names from several modules inside GHCI, we don't have to do <span class="fixed">:m +</span> several times, we can just load up several modules at once.</p>
<pre name="code" class="haskell:ghci">
ghci> :m + Data.List Data.Map Data.Set
</pre>
<p>However, if you've loaded a script that already imports a module, you don't need to use <span class="fixed">:m +</span> to get access to it.</p>
<p>If you just need a couple of functions from a module, you can selectively import just those functions. If we wanted to import only the <span class="fixed">nub</span> and <span class="fixed">sort</span> functions from <span class="fixed">Data.List</span>, we'd do this:</p>
<pre name="code" class="haskell:hs">
import Data.List (nub, sort)
</pre>
<p>You can also choose to import all of the functions of a module except a few select ones. That's often useful when several modules export functions with the same name and you want to get rid of the offending ones. Say we already have our own function that's called <span class="fixed">nub</span> and we want to import all the functions from <span class="fixed">Data.List</span> except the <span class="fixed">nub</span> function:
<pre name="code" class="haskell:hs">
import Data.List hiding (nub)
</pre>
<p>Another way of dealing with name clashes is to do qualified imports. The <span class="fixed">Data.Map</span> module, which offers a data structure for looking up values by key, exports a bunch of functions with the same name as <span class="fixed">Prelude</span> functions, like <span class="fixed">filter</span> or <span class="fixed">null</span>. So when we import <span class="fixed">Data.Map</span> and then call <span class="fixed">filter</span>, Haskell won't know which function to use. Here's how we solve this:</p>
<pre name="code" class="haskell:hs">
import qualified Data.Map
</pre>
<p>This makes it so that if we want to reference <span class="fixed">Data.Map</span>'s <span class="fixed">filter</span> function, we have to do <span class="fixed">Data.Map.filter</span>, whereas just <span class="fixed">filter</span> still refers to the normal <span class="fixed">filter</span> we all know and love. But typing out <span class="fixed">Data.Map</span> in front of every function from that module is kind of tedious. That's why we can rename the qualified import to something shorter:</p>
<pre name="code" class="haskell:hs">
import qualified Data.Map as M
</pre>
<p>Now, to reference <span class="fixed">Data.Map</span>'s <span class="fixed">filter</span> function, we just use <span class="fixed">M.filter</span>.</p>
<p>Use <a href="https://downloads.haskell.org/~ghc/latest/docs/html/libraries/">this handy reference</a> to see which modules are in the standard library. A great way to pick up new Haskell knowledge is to just click through the standard library reference and explore the modules and their functions. You can also view the Haskell source code for each module. Reading the source code of some modules is a really good way to learn Haskell and get a solid feel for it.</p>
<p>To search for functions or to find out where they're located, use <a href="https://hoogle.haskell.org/">Hoogle</a>. It's a really awesome Haskell search engine, you can search by name, module name or even type signature.</p>
<a name="data-list"></a><h2>Data.List</h2>
<p>The <span class="fixed">Data.List</span> module is all about lists, obviously. It provides some very useful functions for dealing with them. We've already met some of its functions (like <span class="fixed">map</span> and <span class="fixed">filter</span>) because the <span class="fixed">Prelude</span> module exports some functions from <span class="fixed">Data.List</span> for convenience. You don't have to import <span class="fixed">Data.List</span> via a qualified import because it doesn't clash with any <span class="fixed">Prelude</span> names except for those that <span class="fixed">Prelude</span> already steals from <span class="fixed">Data.List</span>. Let's take a look at some of the functions that we haven't met before.</p>
<p><span class="label function">intersperse</span> takes an element and a list and then puts that element in between each pair of elements in the list. Here's a demonstration:</p>
<pre name="code" class="haskell:ghci">
ghci> intersperse '.' "MONKEY"
"M.O.N.K.E.Y"
ghci> intersperse 0 [1,2,3,4,5,6]
[1,0,2,0,3,0,4,0,5,0,6]
</pre>
<p><span class="label function">intercalate</span> takes a list and a list of lists. It then inserts that list in between all those lists and then flattens the result.</p>
<pre name="code" class="haskell:ghci">
ghci> intercalate " " ["hey","there","folks"]
"hey there folks"
ghci> intercalate [0,0,0] [[1,2,3],[4,5,6],[7,8,9]]
[1,2,3,0,0,0,4,5,6,0,0,0,7,8,9]
</pre>
<p><span class="label function">transpose</span> transposes a list of lists. If you look at a list of lists as a 2D matrix, the columns become the rows and vice versa.</p>
<pre name="code" class="haskell:ghci">
ghci> transpose [[1,2,3],[4,5,6],[7,8,9]]
[[1,4,7],[2,5,8],[3,6,9]]
ghci> transpose ["hey","there","folks"]
["htf","eho","yel","rk","es"]
</pre>
<p>Say we have the polynomials <i>3x<sup>2</sup> + 5x + 9</i>, <i>10x<sup>3</sup> + 9</i> and <i>8x<sup>3</sup> + 5x<sup>2</sup> + x - 1</i> and we want to add them together. We can use the lists <span class="fixed">[0,3,5,9]</span>, <span class="fixed">[10,0,0,9]</span> and <span class="fixed">[8,5,1,-1]</span> to represent them in Haskell. Now, to add them, all we have to do is this:</p>
<pre name="code" class="haskell:ghci">
ghci> map sum $ transpose [[0,3,5,9],[10,0,0,9],[8,5,1,-1]]
[18,8,6,17]
</pre>
<p>When we transpose these three lists, the third powers are then in the first row, the second powers in the second one and so on. Mapping <span class="fixed">sum</span> to that produces our desired result.</p>
<img src="assets/images/modules/legolists.png" alt="shopping lists" class="left" width="230" height="212">
<p><span class="label function">foldl'</span> and <span class="label function">foldl1'</span> are stricter versions of their respective lazy incarnations. When using lazy folds on really big lists, you might often get a stack overflow error. The culprit for that is that due to the lazy nature of the folds, the accumulator value isn't actually updated as the folding happens. What actually happens is that the accumulator kind of makes a promise that it will compute its value when asked to actually produce the result (also called a thunk). That happens for every intermediate accumulator and all those thunks overflow your stack. The strict folds aren't lazy buggers and actually compute the intermediate values as they go along instead of filling up your stack with thunks. So if you ever get stack overflow errors when doing lazy folds, try switching to their strict versions.</p>
<p><span class="label function">concat</span> flattens a list of lists into just a list of elements.</p>
<pre name="code" class="haskell:ghci">
ghci> concat ["foo","bar","car"]
"foobarcar"
ghci> concat [[3,4,5],[2,3,4],[2,1,1]]
[3,4,5,2,3,4,2,1,1]
</pre>
<p>It will just remove one level of nesting. So if you want to completely flatten <span class="fixed">[[[2,3],[3,4,5],[2]],[[2,3],[3,4]]]</span>, which is a list of lists of lists, you have to concatenate it twice.</p>
<p>Doing <span class="label function">concatMap</span> is the same as first mapping a function to a list and then concatenating the list with <span class="fixed">concat</span>.</p>
<pre name="code" class="haskell:ghci">
ghci> concatMap (replicate 4) [1..3]
[1,1,1,1,2,2,2,2,3,3,3,3]
</pre>
<p><span class="label function">and</span> takes a list of boolean values and returns <span class="fixed">True</span> only if all the values in the list are <span class="fixed">True</span>.</p>
<pre name="code" class="haskell:ghci">
ghci> and $ map (>4) [5,6,7,8]
True
ghci> and $ map (==4) [4,4,4,3,4]
False
</pre>
<p><span class="label function">or</span> is like <span class="fixed">and</span>, only it returns <span class="fixed">True</span> if any of the boolean values in a list is <span class="fixed">True</span>.</p>
<pre name="code" class="haskell:ghci">
ghci> or $ map (==4) [2,3,4,5,6,1]
True
ghci> or $ map (>4) [1,2,3]
False
</pre>
<p><span class="label function">any</span> and <span class="label function">all</span> take a predicate and then check if any or all the elements in a list satisfy the predicate, respectively. Usually we use these two functions instead of mapping over a list and then doing <span class="fixed">and</span> or <span class="fixed">or</span>.</p>
<pre name="code" class="haskell:ghci">
ghci> any (==4) [2,3,5,6,1,4]
True
ghci> all (>4) [6,9,10]
True
ghci> all (`elem` ['A'..'Z']) "HEYGUYSwhatsup"
False
ghci> any (`elem` ['A'..'Z']) "HEYGUYSwhatsup"
True
</pre>
<p><span class="label function">iterate</span> takes a function and a starting value. It applies the function to the starting value, then it applies that function to the result, then it applies the function to that result again, etc. It returns all the results in the form of an infinite list.</p>
<pre name="code" class="haskell:ghci">
ghci> take 10 $ iterate (*2) 1
[1,2,4,8,16,32,64,128,256,512]
ghci> take 3 $ iterate (++ "haha") "haha"
["haha","hahahaha","hahahahahaha"]
</pre>
<p><span class="label function">splitAt</span> takes a number and a list. It then splits the list at that many elements, returning the resulting two lists in a tuple.</p>
<pre name="code" class="haskell:ghci">
ghci> splitAt 3 "heyman"
("hey","man")
ghci> splitAt 100 "heyman"
("heyman","")
ghci> splitAt (-3) "heyman"
("","heyman")
ghci> let (a,b) = splitAt 3 "foobar" in b ++ a
"barfoo"
</pre>
<p><span class="label function">takeWhile</span> is a really useful little function. It takes elements from a list while the predicate holds and then when an element is encountered that doesn't satisfy the predicate, it's cut off. It turns out this is very useful.</p>
<pre name="code" class="haskell:ghci">
ghci> takeWhile (>3) [6,5,4,3,2,1,2,3,4,5,4,3,2,1]
[6,5,4]
ghci> takeWhile (/=' ') "This is a sentence"
"This"
</pre>
<p>Say we wanted to know the sum of all third powers that are under 10,000. We can't map <span class="fixed">(^3)</span> to <span class="fixed">[1..]</span>, apply a filter and then try to sum that up because filtering an infinite list never finishes. You may know that all the elements here are ascending but Haskell doesn't. That's why we can do this:</p>
<pre name="code" class="haskell:ghci">
ghci> sum $ takeWhile (<10000) $ map (^3) [1..]
53361
</pre>
<p>We apply <span class="fixed">(^3)</span> to an infinite list and then once an element that's over 10,000 is encountered, the list is cut off. Now we can sum it up easily.</p>
<p><span class="label function">dropWhile</span> is similar, only it drops all the elements while the predicate is true. Once predicate equates to <span class="fixed">False</span>, it returns the rest of the list. An extremely useful and lovely function!</p>
<pre name="code" class="haskell:ghci">
ghci> dropWhile (/=' ') "This is a sentence"
" is a sentence"
ghci> dropWhile (<3) [1,2,2,2,3,4,5,4,3,2,1]
[3,4,5,4,3,2,1]
</pre>
<p>We're given a list that represents the value of a stock by date. The list is made of tuples whose first component is the stock value, the second is the year, the third is the month and the fourth is the date. We want to know when the stock value first exceeded one thousand dollars!</p>
<pre name="code" class="haskell:ghci">
ghci> let stock = [(994.4,2008,9,1),(995.2,2008,9,2),(999.2,2008,9,3),(1001.4,2008,9,4),(998.3,2008,9,5)]
ghci> head (dropWhile (\(val,y,m,d) -> val < 1000) stock)
(1001.4,2008,9,4)
</pre>
<p><span class="label function">span</span> is kind of like <span class="fixed">takeWhile</span>, only it returns a pair of lists. The first list contains everything the resulting list from <span class="fixed">takeWhile</span> would contain if it were called with the same predicate and the same list. The second list contains the part of the list that would have been dropped.</p>
<pre name="code" class="haskell:ghci">
ghci> let (fw, rest) = span (/=' ') "This is a sentence" in "First word:" ++ fw ++ ", the rest:" ++ rest
"First word: This, the rest: is a sentence"
</pre>
<p>Whereas <span class="fixed">span</span> spans the list while the predicate is true, <span class="label function">break</span> breaks it when the predicate is first true. Doing <span class="fixed">break p</span> is the equivalent of doing <span class="fixed">span (not . p)</span>. </p>
<pre name="code" class="haskell:ghci">
ghci> break (==4) [1,2,3,4,5,6,7]
([1,2,3],[4,5,6,7])
ghci> span (/=4) [1,2,3,4,5,6,7]
([1,2,3],[4,5,6,7])
</pre>
<p>When using <span class="fixed">break</span>, the second list in the result will start with the first element that satisfies the predicate.</p>
<p><span class="label function">sort</span> simply sorts a list. The type of the elements in the list has to be part of the <span class="fixed">Ord</span> typeclass, because if the elements of a list can't be put in some kind of order, then the list can't be sorted.</p>
<pre name="code" class="haskell:ghci">
ghci> sort [8,5,3,2,1,6,4,2]
[1,2,2,3,4,5,6,8]
ghci> sort "This will be sorted soon"
" Tbdeehiillnooorssstw"
</pre>
<p><span class="label function">group</span> takes a list and groups adjacent elements into sublists if they are equal.</p>
<pre name="code" class="haskell:ghci">
ghci> group [1,1,1,1,2,2,2,2,3,3,2,2,2,5,6,7]
[[1,1,1,1],[2,2,2,2],[3,3],[2,2,2],[5],[6],[7]]
</pre>
<p>If we sort a list before grouping it, we can find out how many times each element appears in the list.</p>
<pre name="code" class="haskell:ghci">
ghci> map (\l@(x:xs) -> (x,length l)) . group . sort $ [1,1,1,1,2,2,2,2,3,3,2,2,2,5,6,7]
[(1,4),(2,7),(3,2),(5,1),(6,1),(7,1)]
</pre>
<p><span class="label function">inits</span> and <span class="label function">tails</span> are like <span class="fixed">init</span> and <span class="fixed">tail</span>, only they recursively apply that to a list until there's nothing left. Observe.</p>
<pre name="code" class="haskell:ghci">
ghci> inits "w00t"
["","w","w0","w00","w00t"]
ghci> tails "w00t"
["w00t","00t","0t","t",""]
ghci> let w = "w00t" in zip (inits w) (tails w)
[("","w00t"),("w","00t"),("w0","0t"),("w00","t"),("w00t","")]
</pre>
<p>Let's use a fold to implement searching a list for a sublist.</p>
<pre name="code" class="haskell:hs">
search :: (Eq a) => [a] -> [a] -> Bool
search needle haystack =
let nlen = length needle
in foldl (\acc x -> if take nlen x == needle then True else acc) False (tails haystack)
</pre>
<p>First we call <span class="fixed">tails</span> with the list in which we're searching. Then we go over each tail and see if it starts with what we're looking for.</p>
<p>With that, we actually just made a function that behaves like <span class="label function">isInfixOf</span>. <span class="fixed">isInfixOf</span> searches for a sublist within a list and returns <span class="fixed">True</span> if the sublist we're looking for is somewhere inside the target list.</p>
<pre name="code" class="haskell:ghci">
ghci> "cat" `isInfixOf` "im a cat burglar"
True
ghci> "Cat" `isInfixOf` "im a cat burglar"
False
ghci> "cats" `isInfixOf` "im a cat burglar"
False
</pre>
<p><span class="label function">isPrefixOf</span> and <span class="label function">isSuffixOf</span> search for a sublist at the beginning and at the end of a list, respectively.</p>
<pre name="code" class="haskell:ghci">
ghci> "hey" `isPrefixOf` "hey there!"
True
ghci> "hey" `isPrefixOf` "oh hey there!"
False
ghci> "there!" `isSuffixOf` "oh hey there!"
True
ghci> "there!" `isSuffixOf` "oh hey there"
False
</pre>
<p><span class="label function">elem</span> and <span class="label function">notElem</span> check if an element is or isn't inside a list. </p>
<p><span class="label function">partition</span> takes a list and a predicate and returns a pair of lists. The first list in the result contains all the elements that satisfy the predicate, the second contains all the ones that don't.</p>
<pre name="code" class="haskell:ghci">
ghci> partition (`elem` ['A'..'Z']) "BOBsidneyMORGANeddy"
("BOBMORGAN","sidneyeddy")
ghci> partition (>3) [1,3,5,6,3,2,1,0,3,7]
([5,6,7],[1,3,3,2,1,0,3])
</pre>
<p>It's important to understand how this is different from <span class="fixed">span</span> and <span class="fixed">break</span>:</p>
<pre name="code" class="haskell:ghci">
ghci> span (`elem` ['A'..'Z']) "BOBsidneyMORGANeddy"
("BOB","sidneyMORGANeddy")
</pre>
<p>While <span class="fixed">span</span> and <span class="fixed">break</span> are done once they encounter the first element that doesn't and does satisfy the predicate, <span class="fixed">partition</span> goes through the whole list and splits it up according to the predicate.</p>
<p><span class="label function">find</span> takes a list and a predicate and returns the first element that satisfies the predicate. But it returns that element wrapped in a <span class="fixed">Maybe</span> value. We'll be covering algebraic data types more in depth in the next chapter but for now, this is what you need to know: a <span class="fixed">Maybe</span> value can either be <span class="fixed">Just something</span> or <span class="fixed">Nothing</span>. Much like a list can be either an empty list or a list with some elements, a <span class="fixed">Maybe</span> value can be either no elements or a single element. And like the type of a list of, say, integers is <span class="fixed">[Int]</span>, the type of maybe having an integer is <span class="fixed">Maybe Int</span>. Anyway, let's take our <span class="fixed">find</span> function for a spin.</p>
<pre name="code" class="haskell:ghci">
ghci> find (>4) [1,2,3,4,5,6]
Just 5
ghci> find (>9) [1,2,3,4,5,6]
Nothing
ghci> :t find
find :: (a -> Bool) -> [a] -> Maybe a
</pre>
<p>Notice the type of <span class="fixed">find</span>. Its result is <span class="fixed">Maybe a</span>. That's kind of like having the type of <span class="fixed">[a]</span>, only a value of the type <span class="fixed">Maybe</span> can contain either no elements or one element, whereas a list can contain no elements, one element or several elements.</p>
<p>Remember when we were searching for the first time our stock went over $1000. We did <span class="fixed">head (dropWhile (\(val,y,m,d) -> val < 1000) stock)</span>. Remember that <span class="fixed">head</span> is not really safe. What would happen if our stock never went over $1000? Our application of <span class="fixed">dropWhile</span> would return an empty list and getting the head of an empty list would result in an error. However, if we rewrote that as <span class="fixed">find (\(val,y,m,d) -> val > 1000) stock</span>, we'd be much safer. If our stock never went over $1000 (so if no element satisfied the predicate), we'd get back a <span class="fixed">Nothing</span>. But if there was a valid answer in that list, we'd get, say, <span class="fixed">Just (1001.4,2008,9,4)</span>.
<p><span class="label function">elemIndex</span> is kind of like <span class="fixed">elem</span>, only it doesn't return a boolean value. It maybe returns the index of the element we're looking for. If that element isn't in our list, it returns a <span class="fixed">Nothing</span>. </p>
<pre name="code" class="haskell:ghci">
ghci> :t elemIndex
elemIndex :: (Eq a) => a -> [a] -> Maybe Int
ghci> 4 `elemIndex` [1,2,3,4,5,6]
Just 3
ghci> 10 `elemIndex` [1,2,3,4,5,6]
Nothing
</pre>
<p><span class="label function">elemIndices</span> is like <span class="fixed">elemIndex</span>, only it returns a list of indices, in case the element we're looking for crops up in our list several times. Because we're using a list to represent the indices, we don't need a <span class="fixed">Maybe</span> type, because failure can be represented as the empty list, which is very much synonymous to <span class="fixed">Nothing</span>. </p>
<pre name="code" class="haskell:ghci">
ghci> ' ' `elemIndices` "Where are the spaces?"
[5,9,13]
</pre>
<p><span class="label function">findIndex</span> is like find, but it maybe returns the index of the first element that satisfies the predicate. <span class="label function">findIndices</span> returns the indices of all elements that satisfy the predicate in the form of a list.</p>
<pre name="code" class="haskell:ghci">
ghci> findIndex (==4) [5,3,2,1,6,4]
Just 5
ghci> findIndex (==7) [5,3,2,1,6,4]
Nothing
ghci> findIndices (`elem` ['A'..'Z']) "Where Are The Caps?"
[0,6,10,14]
</pre>
<p>We already covered <span class="fixed">zip</span> and <span class="fixed">zipWith</span>. We noted that they zip together two lists, either in a tuple or with a binary function (meaning such a function that takes two parameters). But what if we want to zip together three lists? Or zip three lists with a function that takes three parameters? Well, for that, we have <span class="label function">zip3</span>, <span class="label function">zip4</span>, etc. and <span class="label function">zipWith3</span>, <span class="label function">zipWith4</span>, etc. These variants go up to 7. While this may look like a hack, it works out pretty fine, because there aren't many times when you want to zip 8 lists together. There's also a very clever way for zipping infinite numbers of lists, but we're not advanced enough to cover that just yet.</p>
<pre name="code" class="haskell:ghci">
ghci> zipWith3 (\x y z -> x + y + z) [1,2,3] [4,5,2,2] [2,2,3]
[7,9,8]
ghci> zip4 [2,3,3] [2,2,2] [5,5,3] [2,2,2]
[(2,2,5,2),(3,2,5,2),(3,2,3,2)]
</pre>
<p>Just like with normal zipping, lists that are longer than the shortest list that's being zipped are cut down to size.</p>
<p><span class="label function">lines</span> is a useful function when dealing with files or input from somewhere. It takes a string and returns every line of that string as separate element of a list.</p>
<pre name="code" class="haskell:ghci">
ghci> lines "first line\nsecond line\nthird line"
["first line","second line","third line"]
</pre>
<p><span class="fixed">'\n'</span> is the character for a unix newline. Backslashes have special meaning in Haskell strings and characters.</p>
<p><span class="label function">unlines</span> is the inverse function of <span class="fixed">lines</span>. It takes a list of strings and joins them together using a <span class="fixed">'\n'</span>.</p>
<pre name="code" class="haskell:ghci">
ghci> unlines ["first line", "second line", "third line"]
"first line\nsecond line\nthird line\n"
</pre>
<p><span class="label function">words</span> and <span class="label function">unwords</span> are for splitting a line of text into words or joining a list of words into a text. Very useful.</p>
<pre name="code" class="haskell:ghci">
ghci> words "hey these are the words in this sentence"
["hey","these","are","the","words","in","this","sentence"]
ghci> words "hey these are the words in this\nsentence"
["hey","these","are","the","words","in","this","sentence"]
ghci> unwords ["hey","there","mate"]
"hey there mate"
</pre>
<p>We've already mentioned <span class="label function">nub</span>. It takes a list and weeds out the duplicate elements, returning a list whose every element is a unique snowflake! The function does have a kind of strange name. It turns out that "nub" means a small lump or essential part of something. In my opinion, they should use real words for function names instead of old-people words.</p>
<pre name="code" class="haskell:ghci">
ghci> nub [1,2,3,4,3,2,1,2,3,4,3,2,1]
[1,2,3,4]
ghci> nub "Lots of words and stuff"
"Lots fwrdanu"
</pre>
<p><span class="label function">delete</span> takes an element and a list and deletes the first occurrence of that element in the list.</p>
<pre name="code" class="haskell:ghci">
ghci> delete 'h' "hey there ghang!"
"ey there ghang!"
ghci> delete 'h' . delete 'h' $ "hey there ghang!"
"ey tere ghang!"
ghci> delete 'h' . delete 'h' . delete 'h' $ "hey there ghang!"
"ey tere gang!"
</pre>
<p><span class="label function">\\</span> is the list difference function. It acts like a set difference, basically. For every element in the right-hand list, it removes a matching element in the left one.</p>
<pre name="code" class="haskell:ghci">
ghci> [1..10] \\ [2,5,9]
[1,3,4,6,7,8,10]
ghci> "Im a big baby" \\ "big"
"Im a baby"
</pre>
<p>Doing <span class="fixed">[1..10] \\ [2,5,9]</span> is like doing <span class="fixed">delete 2 . delete 5 . delete 9 $ [1..10]</span>.</p>
<p><span class="label function">union</span> also acts like a function on sets. It returns the union of two lists. It pretty much goes over every element in the second list and appends it to the first one if it isn't already in yet. Watch out though, duplicates are removed from the second list!</p>
<pre name="code" class="haskell:ghci">
ghci> "hey man" `union` "man what's up"
"hey manwt'sup"
ghci> [1..7] `union` [5..10]
[1,2,3,4,5,6,7,8,9,10]
</pre>
<p><span class="label function">intersect</span> works like set intersection. It returns only the elements that are found in both lists.</p>
<pre name="code" class="haskell:ghci">
ghci> [1..7] `intersect` [5..10]
[5,6,7]
</pre>
<p><span class="label function">insert</span> takes an element and a list of elements that can be sorted and inserts it into the last position where it's still less than or equal to the next element. In other words, <span class="fixed">insert</span> will start at the beginning of the list and then keep going until it finds an element that's equal to or greater than the element that we're inserting and it will insert it just before the element.</p>
<pre name="code" class="haskell:ghci">
ghci> insert 4 [3,5,1,2,8,2]
[3,4,5,1,2,8,2]
ghci> insert 4 [1,3,4,4,1]
[1,3,4,4,4,1]
</pre>
<p>The <span class="fixed">4</span> is inserted right after the <span class="fixed">3</span> and before the <span class="fixed">5</span> in the first example and in between the <span class="fixed">3</span> and <span class="fixed">4</span> in the second example.</p>
If we use <span class="fixed">insert</span> to insert into a sorted list, the resulting list will be kept sorted.</p>
<pre name="code" class="haskell:ghci">
ghci> insert 4 [1,2,3,5,6,7]
[1,2,3,4,5,6,7]
ghci> insert 'g' $ ['a'..'f'] ++ ['h'..'z']
"abcdefghijklmnopqrstuvwxyz"
ghci> insert 3 [1,2,4,3,2,1]
[1,2,3,4,3,2,1]
</pre>
<p>What <span class="fixed">length</span>, <span class="fixed">take</span>, <span class="fixed">drop</span>, <span class="fixed">splitAt</span>, <span class="fixed">!!</span> and <span class="fixed">replicate</span> have in common is that they take an <span class="fixed">Int</span> as one of their parameters (or return an <span class="fixed">Int</span>), even though they could be more generic and usable if they just took any type that's part of the <span class="fixed">Integral</span> or <span class="fixed">Num</span> typeclasses (depending on the functions). They do that for historical reasons. However, fixing that would probably break a lot of existing code. That's why <span class="fixed">Data.List</span> has their more generic equivalents, named <span class="label function">genericLength</span>, <span class="label function">genericTake</span>, <span class="label function">genericDrop</span>, <span class="label function">genericSplitAt</span>, <span class="label function">genericIndex</span> and <span class="label function">genericReplicate</span>. For instance, <span class="fixed">length</span> has a type signature of <span class="fixed">length :: [a] -> Int</span>. If we try to get the average of a list of numbers by doing <span class="fixed">let xs = [1..6] in sum xs / length xs</span>, we get a type error, because you can't use <span class="fixed">/</span> with an <span class="fixed">Int</span>. <span class="fixed">genericLength</span>, on the other hand, has a type signature of <span class="fixed">genericLength :: (Num a) => [b] -> a</span>. Because a <span class="fixed">Num</span> can act like a floating point number, getting the average by doing <span class="fixed">let xs = [1..6] in sum xs / genericLength xs</span> works out just fine.</p>
<p>The <span class="fixed">nub</span>, <span class="fixed">delete</span>, <span class="fixed">union</span>, <span class="fixed">intersect</span> and <span class="fixed">group</span> functions all have their more general counterparts called <span class="label function">nubBy</span>, <span class="label function">deleteBy</span>, <span class="label function">unionBy</span>, <span class="label function">intersectBy</span> and <span class="label function">groupBy</span>. The difference between them is that the first set of functions use <span class="fixed">==</span> to test for equality, whereas the <i>By</i> ones also take an equality function and then compare them by using that equality function. <span class="fixed">group</span> is the same as <span class="fixed">groupBy (==)</span>. </p>
<p>For instance, say we have a list that describes the value of a function for every second. We want to segment it into sublists based on when the value was below zero and when it went above. If we just did a normal <span class="fixed">group</span>, it would just group the equal adjacent values together. But what we want is to group them by whether they are negative or not. That's where <span class="fixed">groupBy</span> comes in! The equality function supplied to the <i>By</i> functions should take two elements of the same type and return <span class="fixed">True</span> if it considers them equal by its standards.</p>
<pre name="code" class="haskell:ghci">
ghci> let values = [-4.3, -2.4, -1.2, 0.4, 2.3, 5.9, 10.5, 29.1, 5.3, -2.4, -14.5, 2.9, 2.3]
ghci> groupBy (\x y -> (x > 0) == (y > 0)) values
[[-4.3,-2.4,-1.2],[0.4,2.3,5.9,10.5,29.1,5.3],[-2.4,-14.5],[2.9,2.3]]
</pre>
<p>From this, we clearly see which sections are positive and which are negative. The equality function supplied takes two elements and then returns <span class="fixed">True</span> only if they're both negative or if they're both positive. This equality function can also be written as <span class="fixed">\x y -> (x > 0) && (y > 0) || (x <= 0) && (y <= 0)</span>, although I think the first way is more readable. An even clearer way to write equality functions for the <i>By</i> functions is if you import the <span class="label function">on</span> function from <span class="fixed">Data.Function</span>. <span class="fixed">on</span> is defined like this:
<pre name="code" class="haskell:ghci">
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
f `on` g = \x y -> f (g x) (g y)
</pre>
<p>So doing <span class="fixed">(==) `on` (> 0)</span> returns an equality function that looks like <span class="fixed">\x y -> (x > 0) == (y > 0)</span>. <span class="fixed">on</span> is used a lot with the <i>By</i> functions because with it, we can do:
<pre name="code" class="haskell:ghci">
ghci> groupBy ((==) `on` (> 0)) values
[[-4.3,-2.4,-1.2],[0.4,2.3,5.9,10.5,29.1,5.3],[-2.4,-14.5],[2.9,2.3]]
</pre>
<p>Very readable indeed! You can read it out loud: Group this by equality on whether the elements are greater than zero.</p>
<p>Similarly, the <span class="fixed">sort</span>, <span class="fixed">insert</span>, <span class="fixed">maximum</span> and <span class="fixed">minimum</span> also have their more general equivalents. Functions like <span class="fixed">groupBy</span> take a function that determines when two elements are equal. <span class="label function">sortBy</span>, <span class="label function">insertBy</span>, <span class="label function">maximumBy</span> and <span class="label function">minimumBy</span> take a function that determine if one element is greater, smaller or equal to the other. The type signature of <span class="fixed">sortBy</span> is <span class="fixed">sortBy :: (a -> a -> Ordering) -> [a] -> [a]</span>. If you remember from before, the <span class="fixed">Ordering</span> type can have a value of <span class="fixed">LT</span>, <span class="fixed">EQ</span> or <span class="fixed">GT</span>. <span class="fixed">sort</span> is the equivalent of <span class="fixed">sortBy compare</span>, because compare just takes two elements whose type is in the <span class="fixed">Ord</span> typeclass and returns their ordering relationship.</p>
<p>Lists can be compared, but when they are, they are compared lexicographically. What if we have a list of lists and we want to sort it not based on the inner lists' contents but on their lengths? Well, as you've probably guessed, we'll use the <span class="fixed">sortBy</span> function.</p>
<pre name="code" class="haskell:ghci">
ghci> let xs = [[5,4,5,4,4],[1,2,3],[3,5,4,3],[],[2],[2,2]]
ghci> sortBy (compare `on` length) xs
[[],[2],[2,2],[1,2,3],[3,5,4,3],[5,4,5,4,4]]
</pre>
<p>Awesome! <span class="fixed">compare `on` length</span> ... man, that reads almost like real English! If you're not sure how exactly the <span class="fixed">on</span> works here, <span class="fixed">compare `on` length</span> is the equivalent of <span class="fixed">\x y -> length x `compare` length y</span>. When you're dealing with <i>By</i> functions that take an equality function, you usually do <span class="fixed">(==) `on` something</span> and when you're dealing with <i>By</i> functions that take an ordering function, you usually do <span class="fixed">compare `on` something</span>.</p>
<a name="data-char"></a><h2>Data.Char</h2>
<img src="assets/images/modules/legochar.png" alt="lego char" class="right" width="230" height="323">
<p>The <span class="fixed">Data.Char</span> module does what its name suggests. It exports functions that deal with characters. It's also helpful when filtering and mapping over strings because they're just lists of characters.</p>
<p><span class="fixed">Data.Char</span> exports a bunch of predicates over characters. That is, functions that take a character and tell us whether some assumption about it is true or false. Here's what they are:</p>
<p><span class="label function">isControl</span> checks whether a character is a control character.</p>
<p><span class="label function">isSpace</span> checks whether a character is a white-space characters. That includes spaces, tab characters, newlines, etc.</p>
<p><span class="label function">isLower</span> checks whether a character is lower-cased. </p>
<p><span class="label function">isUpper</span> checks whether a character is upper-cased.</p>
<p><span class="label function">isAlpha</span> checks whether a character is a letter.</p>
<p><span class="label function">isAlphaNum</span> checks whether a character is a letter or a number.</p>
<p><span class="label function">isPrint</span> checks whether a character is printable. Control characters, for instance, are not printable.</p>
<p><span class="label function">isDigit</span> checks whether a character is a digit.</p>
<p><span class="label function">isOctDigit</span> checks whether a character is an octal digit.</p>
<p><span class="label function">isHexDigit</span> checks whether a character is a hex digit.</p>
<p><span class="label function">isLetter</span> checks whether a character is a letter.</p>
<p><span class="label function">isMark</span> checks for Unicode mark characters. Those are characters that combine with preceding letters to form letters with accents. Use this if you are French.</p>
<p><span class="label function">isNumber</span> checks whether a character is numeric.</p>
<p><span class="label function">isPunctuation</span> checks whether a character is punctuation.</p>
<p><span class="label function">isSymbol</span> checks whether a character is a fancy mathematical or currency symbol.</p>
<p><span class="label function">isSeparator</span> checks for Unicode spaces and separators.</p>
<p><span class="label function">isAscii</span> checks whether a character falls into the first 128 characters of the Unicode character set.</p>
<p><span class="label function">isLatin1</span> checks whether a character falls into the first 256 characters of Unicode.</p>
<p><span class="label function">isAsciiUpper</span> checks whether a character is ASCII and upper-case.</p>
<p><span class="label function">isAsciiLower</span> checks whether a character is ASCII and lower-case.</p>
<p>All these predicates have a type signature of <span class="fixed">Char -> Bool</span>. Most of the time you'll use this to filter out strings or something like that. For instance, let's say we're making a program that takes a username and the username can only be comprised of alphanumeric characters. We can use the <span class="fixed">Data.List</span> function <span class="fixed">all</span> in combination with the <span class="fixed">Data.Char</span> predicates to determine if the username is alright.</p>
<pre name="code" class="haskell:ghci">
ghci> all isAlphaNum "bobby283"
True
ghci> all isAlphaNum "eddy the fish!"
False
</pre>
<p>Kewl. In case you don't remember, <span class="fixed">all</span> takes a predicate and a list and returns <span class="fixed">True</span> only if that predicate holds for every element in the list.</p>
<p>We can also use <span class="fixed">isSpace</span> to simulate the <span class="fixed">Data.List</span> function <span class="fixed">words</span>.
<pre name="code" class="haskell:ghci">
ghci> words "hey folks its me"
["hey","folks","its","me"]
ghci> groupBy ((==) `on` isSpace) "hey folks its me"
["hey"," ","folks"," ","its"," ","me"]
ghci>
</pre>
<p>Hmmm, well, it kind of does what <span class="fixed">words</span> does but we're left with elements of only spaces. Hmm, whatever shall we do? I know, let's filter that sucker.</p>
<pre name="code" class="haskell:ghci">
ghci> filter (not . any isSpace) . groupBy ((==) `on` isSpace) $ "hey folks its me"
["hey","folks","its","me"]
</pre>
<p>Ah.</p>
<p>The <span class="fixed">Data.Char</span> also exports a datatype that's kind of like <span class="fixed">Ordering</span>. The <span class="fixed">Ordering</span> type can have a value of <span class="fixed">LT</span>, <span class="fixed">EQ</span> or <span class="fixed">GT</span>. It's a sort of enumeration. It describes a few possible results that can arise from comparing two elements. The <span class="fixed">GeneralCategory</span> type is also an enumeration. It presents us with a few possible categories that a character can fall into. The main function for getting the general category of a character is <span class="fixed">generalCategory</span>. It has a type of <span class="fixed">generalCategory :: Char -> GeneralCategory</span>. There are about 31 categories so we won't list them all here, but let's play around with the function.</p>
<pre name="code" class="haskell:ghci">
ghci> generalCategory ' '
Space
ghci> generalCategory 'A'
UppercaseLetter
ghci> generalCategory 'a'
LowercaseLetter
ghci> generalCategory '.'
OtherPunctuation
ghci> generalCategory '9'
DecimalNumber
ghci> map generalCategory " \t\nA9?|"
[Space,Control,Control,UppercaseLetter,DecimalNumber,OtherPunctuation,MathSymbol]
</pre>
<p>Since the <span class="fixed">GeneralCategory</span> type is part of the <span class="fixed">Eq</span> typeclass, we can also test for stuff like <span class="fixed">generalCategory c == Space</span>.</p>
<p><span class="label function">toUpper</span> converts a character to upper-case. Spaces, numbers, and the like remain unchanged.</p>
<p><span class="label function">toLower</span> converts a character to lower-case.</p>
<p><span class="label function">toTitle</span> converts a character to title-case. For most characters, title-case is the same as upper-case.</p>
<p><span class="label function">digitToInt</span> converts a character to an <span class="fixed">Int</span>. To succeed, the character must be in the ranges <span class="fixed">'0'..'9'</span>, <span class="fixed">'a'..'f'</span> or <span class="fixed">'A'..'F'</span>.</p>
<pre name="code" class="haskell:ghci">
ghci> map digitToInt "34538"
[3,4,5,3,8]
ghci> map digitToInt "FF85AB"
[15,15,8,5,10,11]
</pre>
<p><span class="label function">intToDigit</span> is the inverse function of <span class="fixed">digitToInt</span>. It takes an <span class="fixed">Int</span> in the range of <span class="fixed">0..15</span> and converts it to a lower-case character.</p>
<pre name="code" class="haskell:ghci">
ghci> intToDigit 15
'f'
ghci> intToDigit 5
'5'
</pre>
<p>The <span class="label function">ord</span> and <span class="fixed">chr</span> functions convert characters to their corresponding numbers and vice versa:</p>
<pre name="code" class="haskell:ghci">
ghci> ord 'a'
97
ghci> chr 97
'a'
ghci> map ord "abcdefgh"
[97,98,99,100,101,102,103,104]
</pre>
<p>The difference between the <span class="fixed">ord</span> values of two characters is equal to how far apart they are in the Unicode table.</p><p>The Caesar cipher is a primitive method of encoding messages by shifting each character in them by a fixed number of positions in the alphabet. We can easily create a sort of Caesar cipher of our own, only we won't constrict ourselves to the alphabet.</p>
<pre name="code" class="haskell:hs">
encode :: Int -> String -> String
encode shift msg =
let ords = map ord msg
shifted = map (+ shift) ords
in map chr shifted
</pre>
<p>Here, we first convert the string to a list of numbers. Then we add the shift amount to each number before converting the list of numbers back to characters. If you're a composition cowboy, you could write the body of this function as <span class="fixed">map (chr . (+ shift) . ord) msg</span>. Let's try encoding a few messages.</p>
<pre name="code" class="haskell:ghci">
ghci> encode 3 "Heeeeey"
"Khhhhh|"
ghci> encode 4 "Heeeeey"
"Liiiii}"
ghci> encode 1 "abcd"
"bcde"
ghci> encode 5 "Marry Christmas! Ho ho ho!"
"Rfww~%Hmwnxyrfx&%Mt%mt%mt&"
</pre>
<p>That's encoded alright. Decoding a message is basically just shifting it back by the number of places it was shifted by in the first place.</p>
<pre name="code" class="haskell:hs">
decode :: Int -> String -> String
decode shift msg = encode (negate shift) msg
</pre>
<pre name="code" class="haskell:ghci">
ghci> encode 3 "Im a little teapot"
"Lp#d#olwwoh#whdsrw"
ghci> decode 3 "Lp#d#olwwoh#whdsrw"
"Im a little teapot"
ghci> decode 5 . encode 5 $ "This is a sentence"
"This is a sentence"
</pre>
<a name="data-map"></a><h2>Data.Map</h2>
<p>Association lists (also called dictionaries) are lists that are used to store key-value pairs where ordering doesn't matter. For instance, we might use an association list to store phone numbers, where phone numbers would be the values and people's names would be the keys. We don't care in which order they're stored, we just want to get the right phone number for the right person.</p>
<p>The most obvious way to represent association lists in Haskell would be by having a list of pairs. The first component in the pair would be the key, the second component the value. Here's an example of an association list with phone numbers:</p>
<pre name="code" class="haskell:hs">
phoneBook =
[("amelia","555-2938")
,("freya","452-2928")
,("isabella","493-2928")
,("neil","205-2928")
,("roald","939-8282")
,("tenzing","853-2492")
]
</pre>
<p>Despite this seemingly odd indentation, this is just a list of pairs of strings. The most common task when dealing with association lists is looking up some value by key. Let's make a function that looks up some value given a key.</p>
<pre name="code" class="haskell:hs">
findKey :: (Eq k) => k -> [(k,v)] -> v
findKey key xs = snd . head . filter (\(k,v) -> key == k) $ xs
</pre>
<p>Pretty simple. The function that takes a key and a list, filters the list so that only matching keys remain, gets the first key-value that matches and returns the value. But what happens if the key we're looking for isn't in the association list? Hmm. Here, if a key isn't in the association list, we'll end up trying to get the head of an empty list, which throws a runtime error. However, we should avoid making our programs so easy to crash, so let's use the <span class="fixed">Maybe</span> data type. If we don't find the key, we'll return a <span class="fixed">Nothing</span>. If we find it, we'll return <span class="fixed">Just something</span>, where something is the value corresponding to that key.</p>
<pre name="code" class="haskell:hs">
findKey :: (Eq k) => k -> [(k,v)] -> Maybe v
findKey key [] = Nothing
findKey key ((k,v):xs) = if key == k
then Just v
else findKey key xs
</pre>
<p>Look at the type declaration. It takes a key that can be equated, an association list and then it maybe produces a value. Sounds about right.</p>
<p>This is a textbook recursive function that operates on a list. Edge case, splitting a list into a head and a tail, recursive calls, they're all there. This is the classic fold pattern, so let's see how this would be implemented as a fold.</p>
<pre name="code" class="haskell:hs">
findKey :: (Eq k) => k -> [(k,v)] -> Maybe v
findKey key = foldr (\(k,v) acc -> if key == k then Just v else acc) Nothing
</pre>
<div class="hintbox"><em>Note:</em> It's usually better to use folds for this standard list recursion pattern instead of explicitly writing the recursion because they're easier to read and identify. Everyone knows it's a fold when they see the <span class="fixed">foldr</span> call, but it takes some more thinking to read explicit recursion.</div>
<pre name="code" class="haskell:ghci">
ghci> findKey "tenzing" phoneBook
Just "853-2492"
ghci> findKey "amelia" phoneBook
Just "555-2938"
ghci> findKey "christopher" phoneBook
Nothing
</pre>
<img src="assets/images/modules/legomap.png" alt="legomap" class="left" width="214" height="240">
<p>Works like a charm! If we have the friend's phone number, we <span class="fixed">Just</span> get the number, otherwise we get <span class="fixed">Nothing</span>.</p>
<p>We just implemented the <span class="fixed">lookup</span> function from <span class="fixed">Data.List</span>. If we want to find the corresponding value to a key, we have to traverse all the elements of the list until we find it. The <span class="fixed">Data.Map</span> module offers association lists that are much faster (because they're internally implemented with trees) and also it provides a lot of utility functions. From now on, we'll say we're working with maps instead of association lists.</p>
<p>Because <span class="fixed">Data.Map</span> exports functions that clash with the <span class="fixed">Prelude</span> and <span class="fixed">Data.List</span> ones, we'll do a qualified import.
<pre name="code" class="haskell:hs">
import qualified Data.Map as Map
</pre>
<p>Put this import statement into a script and then load the script via GHCI.</p>
<p>Let's go ahead and see what <span class="fixed">Data.Map</span> has in store for us! Here's the basic rundown of its functions.</p>
<p>The <span class="label function">fromList</span> function takes an association list (in the form of a list) and returns a map with the same associations.</p>
<pre name="code" class="haskell:ghci">
ghci> Map.fromList [("amelia","555-2938"),("freya","452-2928"),("neil","205-2928")]
fromList [("amelia","555-2938"),("freya","452-2928"),("neil","205-2928")]
ghci> Map.fromList [(1,2),(3,4),(3,2),(5,5)]
fromList [(1,2),(3,2),(5,5)]
</pre>
<p>If there are duplicate keys in the original association list, the duplicates are just discarded. This is the type signature of <span class="fixed">fromList</span></p>
<pre name="code" class="haskell:hs">
Map.fromList :: (Ord k) => [(k, v)] -> Map.Map k v
</pre>
<p>It says that it takes a list of pairs of type <span class="fixed">k</span> and <span class="fixed">v</span> and returns a map that maps from keys of type <span class="fixed">k</span> to type <span class="fixed">v</span>. Notice that when we were doing association lists with normal lists, the keys only had to be equatable (their type belonging to the <span class="fixed">Eq</span> typeclass) but now they have to be orderable. That's an essential constraint in the <span class="fixed">Data.Map</span> module. It needs the keys to be orderable so it can arrange them in a tree.</p>
<p>You should always use <span class="fixed">Data.Map</span> for key-value associations unless you have keys that aren't part of the <span class="fixed">Ord</span> typeclass.</p>
<p><span class="label function">empty</span> represents an empty map. It takes no arguments, it just returns an empty map.</p>
<pre name="code" class="haskell:ghci">
ghci> Map.empty
fromList []
</pre>
<p><span class="label function">insert</span> takes a key, a value and a map and returns a new map that's just like the old one, only with the key and value inserted.</p>
<pre name="code" class="haskell:ghci">
ghci> Map.empty
fromList []
ghci> Map.insert 3 100 Map.empty
fromList [(3,100)]
ghci> Map.insert 5 600 (Map.insert 4 200 ( Map.insert 3 100 Map.empty))
fromList [(3,100),(4,200),(5,600)]
ghci> Map.insert 5 600 . Map.insert 4 200 . Map.insert 3 100 $ Map.empty
fromList [(3,100),(4,200),(5,600)]
</pre>
<p>We can implement our own <span class="fixed">fromList</span> by using the empty map, <span class="fixed">insert</span> and a fold. Watch:</p>
<pre name="code" class="haskell:ghci">
fromList' :: (Ord k) => [(k,v)] -> Map.Map k v
fromList' = foldr (\(k,v) acc -> Map.insert k v acc) Map.empty
</pre>
<p>It's a pretty straightforward fold. We start of with an empty map and we fold it up from the right, inserting the key value pairs into the accumulator as we go along.</p>
<p><span class="label function">null</span> checks if a map is empty.</p>
<pre name="code" class="haskell:ghci">
ghci> Map.null Map.empty
True
ghci> Map.null $ Map.fromList [(2,3),(5,5)]
False
</pre>
<p><span class="label function">size</span> reports the size of a map.</p>
<pre name="code" class="haskell:ghci">
ghci> Map.size Map.empty
0
ghci> Map.size $ Map.fromList [(2,4),(3,3),(4,2),(5,4),(6,4)]
5
</pre>
<p><span class="label function">singleton</span> takes a key and a value and creates a map that has exactly one mapping.</p>
<pre name="code" class="haskell:ghci">
ghci> Map.singleton 3 9
fromList [(3,9)]
ghci> Map.insert 5 9 $ Map.singleton 3 9
fromList [(3,9),(5,9)]
</pre>
<p><span class="label function">lookup</span> works like the <span class="fixed">Data.List</span> <span class="fixed">lookup</span>, only it operates on maps. It returns <span class="fixed">Just something</span> if it finds something for the key and <span class="fixed">Nothing</span> if it doesn't.</p>
<p><span class="label function">member</span> is a predicate that takes a key and a map and reports whether the key is in the map or not.</p>
<pre name="code" class="haskell:ghci">
ghci> Map.member 3 $ Map.fromList [(3,6),(4,3),(6,9)]
True
ghci> Map.member 3 $ Map.fromList [(2,5),(4,5)]
False
</pre>
<p><span class="label function">map</span> and <span class="label function">filter</span> work much like their list equivalents.</p>
<pre name="code" class="haskell:ghci">
ghci> Map.map (*100) $ Map.fromList [(1,1),(2,4),(3,9)]
fromList [(1,100),(2,400),(3,900)]
ghci> Map.filter isUpper $ Map.fromList [(1,'a'),(2,'A'),(3,'b'),(4,'B')]
fromList [(2,'A'),(4,'B')]
</pre>
<p><span class="label function">toList</span> is the inverse of <span class="fixed">fromList</span>.</p>
<pre name="code" class="haskell:ghci">
ghci> Map.toList . Map.insert 9 2 $ Map.singleton 4 3
[(4,3),(9,2)]
</pre>
<p><span class="label function">keys</span> and <span class="label function">elems</span> return lists of keys and values respectively. <span class="fixed">keys</span> is the equivalent of <span class="fixed">map fst . Map.toList</span> and <span class="fixed">elems</span> is the equivalent of <span class="fixed">map snd . Map.toList</span>.</p>
<p><span class="label function">fromListWith</span> is a cool little function. It acts like <span class="fixed">fromList</span>, only it doesn't discard duplicate keys but it uses a function supplied to it to decide what to do with them. Let's say that a friend can have several numbers and we have an association list set up like this.</p>
<pre name="code" class="haskell:hs">
phoneBook =
[("amelia","555-2938")
,("amelia","342-2492")
,("freya","452-2928")
,("isabella","493-2928")
,("isabella","943-2929")
,("isabella","827-9162")
,("neil","205-2928")
,("roald","939-8282")
,("tenzing","853-2492")
,("tenzing","555-2111")
]
</pre>
<p>Now if we just use <span class="fixed">fromList</span> to put that into a map, we'll lose a few numbers! So here's what we'll do:</p>
<pre name="code" class="haskell:hs">
phoneBookToMap :: (Ord k) => [(k, String)] -> Map.Map k String
phoneBookToMap xs = Map.fromListWith (\number1 number2 -> number1 ++ ", " ++ number2) xs
</pre>
<pre name="code" class="haskell:hs">
ghci> Map.lookup "isabella" $ phoneBookToMap phoneBook
"827-9162, 943-2929, 493-2928"
ghci> Map.lookup "roald" $ phoneBookToMap phoneBook
"939-8282"
ghci> Map.lookup "amelia" $ phoneBookToMap phoneBook
"342-2492, 555-2938"
</pre>
<p>If a duplicate key is found, the function we pass is used to combine the values of those keys into some other value. We could also first make all the values in the association list singleton lists and then we can use <span class="fixed">++</span> to combine the numbers.</p>
<pre name="code" class="haskell:hs">
phoneBookToMap :: (Ord k) => [(k, a)] -> Map.Map k [a]
phoneBookToMap xs = Map.fromListWith (++) $ map (\(k,v) -> (k,[v])) xs
</pre>
<pre name="code" class="haskell:ghci">
ghci> Map.lookup "isabella" $ phoneBookToMap phoneBook
["827-9162","943-2929","493-2928"]
</pre>
<p>Pretty neat! Another use case is if we're making a map from an association list of numbers and when a duplicate key is found, we want the biggest value for the key to be kept.</p>
<pre name="code" class="haskell:ghci">
ghci> Map.fromListWith max [(2,3),(2,5),(2,100),(3,29),(3,22),(3,11),(4,22),(4,15)]
fromList [(2,100),(3,29),(4,22)]
</pre>
<p>Or we could choose to add together values on the same keys.</p>
<pre name="code" class="haskell:ghci">
ghci> Map.fromListWith (+) [(2,3),(2,5),(2,100),(3,29),(3,22),(3,11),(4,22),(4,15)]
fromList [(2,108),(3,62),(4,37)]
</pre>
<p><span class="label function">insertWith</span> is to <span class="fixed">insert</span> what <span class="fixed">fromListWith</span> is to <span class="fixed">fromList</span>. It inserts a key-value pair into a map, but if that map already contains the key, it uses the function passed to it to determine what to do.</p>
<pre name="code" class="haskell:ghci">
ghci> Map.insertWith (+) 3 100 $ Map.fromList [(3,4),(5,103),(6,339)]
fromList [(3,104),(5,103),(6,339)]
</pre>
<p>These were just a few functions from <span class="fixed">Data.Map</span>. You can see a complete list of functions in the <a href="https://hackage.haskell.org/package/containers/docs/Data-Map.html">documentation</a>.</p>
<a name="data-set"></a><h2>Data.Set</h2>
<img src="assets/images/modules/legosets.png" alt="legosets" class="right" width="150" height="236">
<p>The <span class="fixed">Data.Set</span> module offers us, well, sets. Like sets from mathematics. Sets are kind of like a cross between lists and maps. All the elements in a set are unique. And because they're internally implemented with trees (much like maps in <span class="fixed">Data.Map</span>), they're ordered. Checking for membership, inserting, deleting, etc. is much faster than doing the same thing with lists. The most common operation when dealing with sets are inserting into a set, checking for membership and converting a set to a list.</p>
<p>Because the names in <span class="fixed">Data.Set</span> clash with a lot of <span class="fixed">Prelude</span> and <span class="fixed">Data.List</span> names, we do a qualified import.</p>
<p>Put this import statement in a script:</p>
<pre name="code" class="haskell:ghci">
import qualified Data.Set as Set
</pre>
<p>And then load the script via GHCI.</p>
<p>Let's say we have two pieces of text. We want to find out which characters were used in both of them.</p>
<pre name="code" class="haskell:ghci">
text1 = "I just had an anime dream. Anime... Reality... Are they so different?"
text2 = "The old man left his garbage can out and now his trash is all over my lawn!"
</pre>
<p>
The <span class="label function">fromList</span> function works much like you would expect. It takes a list and converts it into a set.</p>
<pre name="code" class="haskell:ghci">
ghci> let set1 = Set.fromList text1
ghci> let set2 = Set.fromList text2
ghci> set1
fromList " .?AIRadefhijlmnorstuy"
ghci> set2
fromList " !Tabcdefghilmnorstuvwy"
</pre>
<p>As you can see, the items are ordered and each element is unique. Now let's use the <span class="label function">intersection</span> function to see which elements they both share.</p>
<pre name="code" class="haskell:ghci">
ghci> Set.intersection set1 set2
fromList " adefhilmnorstuy"
</pre>
<p>We can use the <span class="label function">difference</span> function to see which letters are in the first set but aren't in the second one and vice versa.</p>
<pre name="code" class="haskell:ghci">
ghci> Set.difference set1 set2
fromList ".?AIRj"
ghci> Set.difference set2 set1
fromList "!Tbcgvw"
</pre>
<p>Or we can see all the unique letters used in both sentences by using <span class="label function">union</span>.</p>
<pre name="code" class="haskell:ghci">
ghci> Set.union set1 set2
fromList " !.?AIRTabcdefghijlmnorstuvwy"
</pre>
<p>The <span class="label function">null</span>, <span class="label function">size</span>, <span class="label function">member</span>, <span class="label function">empty</span>, <span class="label function">singleton</span>, <span class="label function">insert</span> and <span class="label function">delete</span> functions all work like you'd expect them to.</p>
<pre name="code" class="haskell:ghci">
ghci> Set.null Set.empty
True
ghci> Set.null $ Set.fromList [3,4,5,5,4,3]
False
ghci> Set.size $ Set.fromList [3,4,5,3,4,5]
3
ghci> Set.singleton 9
fromList [9]
ghci> Set.insert 4 $ Set.fromList [9,3,8,1]
fromList [1,3,4,8,9]
ghci> Set.insert 8 $ Set.fromList [5..10]
fromList [5,6,7,8,9,10]
ghci> Set.delete 4 $ Set.fromList [3,4,5,4,3,4,5]
fromList [3,5]
</pre>
<p>We can also check for subsets or proper subset. Set A is a subset of set B if B contains all the elements that A does. Set A is a proper subset of set B if B contains all the elements that A does but has more elements.</p>
<pre name="code" class="haskell:ghci">
ghci> Set.fromList [2,3,4] `Set.isSubsetOf` Set.fromList [1,2,3,4,5]
True
ghci> Set.fromList [1,2,3,4,5] `Set.isSubsetOf` Set.fromList [1,2,3,4,5]
True
ghci> Set.fromList [1,2,3,4,5] `Set.isProperSubsetOf` Set.fromList [1,2,3,4,5]
False
ghci> Set.fromList [2,3,4,8] `Set.isSubsetOf` Set.fromList [1,2,3,4,5]
False
</pre>
<p>We can also <span class="label function">map</span> over sets and <span class="label function">filter</span> them.</p>
<pre name="code" class="haskell:ghci">
ghci> Set.filter odd $ Set.fromList [3,4,5,6,7,2,3,4]
fromList [3,5,7]
ghci> Set.map (+1) $ Set.fromList [3,4,5,6,7,2,3,4]
fromList [3,4,5,6,7,8]
</pre>
<p>Sets are often used to weed a list of duplicates from a list by first making it into a set with <span class="fixed">fromList</span> and then converting it back to a list with <span class="label function">toList</span>. The <span class="fixed">Data.List</span> function <span class="fixed">nub</span> already does that, but weeding out duplicates for large lists is much faster if you cram them into a set and then convert them back to a list than using <span class="fixed">nub</span>. But using <span class="fixed">nub</span> only requires the type of the list's elements to be part of the <span class="fixed">Eq</span> typeclass, whereas if you want to cram elements into a set, the type of the list has to be in <span class="fixed">Ord</span>.</p>
<pre name="code" class="haskell:ghci">
ghci> let setNub xs = Set.toList $ Set.fromList xs
ghci> setNub "HEY WHATS CRACKALACKIN"
" ACEHIKLNRSTWY"
ghci> nub "HEY WHATS CRACKALACKIN"
"HEY WATSCRKLIN"
</pre>
<p><span class="fixed">setNub</span> is generally faster than <span class="fixed">nub</span> on big lists but as you can see, <span class="fixed">nub</span> preserves the ordering of the list's elements, while <span class="fixed">setNub</span> does not.</p>
<a name="making-our-own-modules"></a><h2>Making our own modules</h2>
<img src="assets/images/modules/making_modules.png" alt="making modules" class="right" width="345" height="224">
<p>We've looked at some cool modules so far, but how do we make our own module? Almost every programming language enables you to split your code up into several files and Haskell is no different. When making programs, it's good practice to take functions and types that work towards a similar purpose and put them in a module. That way, you can easily reuse those functions in other programs by just importing your module.</p>
<p>Let's see how we can make our own modules by making a little module that provides some functions for calculating the volume and area of a few geometrical objects. We'll start by creating a file called <span class="fixed">Geometry.hs</span>.</p>
<p>We say that a module <i>exports</i> functions. What that means is that when I import a module, I can use the functions that it exports. It can define functions that its functions call internally, but we can only see and use the ones that it exports.</p>
<p>At the beginning of a module, we specify the module name. If we have a file called <span class="fixed">Geometry.hs</span>, then we should name our module <span class="fixed">Geometry</span>. Then, we specify the functions that it exports and after that, we can start writing the functions. So we'll start with this.</p>
<pre name="code" class="haskell:ghci">
module Geometry
( sphereVolume
, sphereArea
, cubeVolume
, cubeArea
, cuboidArea
, cuboidVolume
) where
</pre>
<p>As you can see, we'll be doing areas and volumes for spheres, cubes and cuboids. Let's go ahead and define our functions then:</p>
<pre name="code" class="haskell:ghci">
module Geometry
( sphereVolume
, sphereArea
, cubeVolume
, cubeArea
, cuboidArea
, cuboidVolume
) where
sphereVolume :: Float -> Float
sphereVolume radius = (4.0 / 3.0) * pi * (radius ^ 3)
sphereArea :: Float -> Float
sphereArea radius = 4 * pi * (radius ^ 2)
cubeVolume :: Float -> Float
cubeVolume side = cuboidVolume side side side
cubeArea :: Float -> Float
cubeArea side = cuboidArea side side side
cuboidVolume :: Float -> Float -> Float -> Float
cuboidVolume a b c = rectangleArea a b * c
cuboidArea :: Float -> Float -> Float -> Float
cuboidArea a b c = rectangleArea a b * 2 + rectangleArea a c * 2 + rectangleArea c b * 2
rectangleArea :: Float -> Float -> Float
rectangleArea a b = a * b
</pre>
<p>Pretty standard geometry right here. There are a few things to take note of though. Because a cube is only a special case of a cuboid, we defined its area and volume by treating it as a cuboid whose sides are all of the same length. We also defined a helper function called <span class="fixed">rectangleArea</span>, which calculates a rectangle's area based on the lenghts of its sides. It's rather trivial because it's just multiplication. Notice that we used it in our functions in the module (namely <span class="fixed">cuboidArea</span> and <span class="fixed">cuboidVolume</span>) but we didn't export it! Because we want our module to just present functions for dealing with three-dimensional objects, we used <span class="fixed">rectangleArea</span> but we didn't export it.</p>
<p>When making a module, we usually export only those functions that act as a sort of interface to our module so that the implementation is hidden. If someone is using our <span class="fixed">Geometry</span> module, they don't have to concern themselves with functions that we don't export. We can decide to change those functions completely or delete them in a newer version (we could delete <span class="fixed">rectangleArea</span> and just use <span class="fixed">*</span> instead) and no one will mind because we weren't exporting them in the first place.</p>
<p>To use our module, we just do:</p>
<pre name="code" class="haskell:ghci">
import Geometry
</pre>
<p><span class="fixed">Geometry.hs</span> has to be in the same folder that the program that's importing it is in, though.</p>
<p>Modules can also have a hierarchical structure. Each module can have a number of submodules and they can have submodules of their own. Let's section these functions off so that <span class="fixed">Geometry</span> is a module that has three submodules, one for each type of object.</p>
<p>First, we'll make a folder called <span class="fixed">Geometry</span>. Mind the capital G. In it, we'll place three files: <span class="fixed">Sphere.hs</span>, <span class="fixed">Cuboid.hs</span>, and <span class="fixed">Cube.hs</span>. Here's what the files will contain:</p>
<p><span class="fixed">Sphere.hs</span></p>
<pre name="code" class="haskell:ghci">
module Geometry.Sphere
( volume
, area
) where
volume :: Float -> Float
volume radius = (4.0 / 3.0) * pi * (radius ^ 3)
area :: Float -> Float
area radius = 4 * pi * (radius ^ 2)
</pre>
<p><span class="fixed">Cuboid.hs</span></p>
<pre name="code" class="haskell:ghci">
module Geometry.Cuboid
( volume
, area
) where
volume :: Float -> Float -> Float -> Float
volume a b c = rectangleArea a b * c
area :: Float -> Float -> Float -> Float
area a b c = rectangleArea a b * 2 + rectangleArea a c * 2 + rectangleArea c b * 2
rectangleArea :: Float -> Float -> Float
rectangleArea a b = a * b
</pre>
<p><span class="fixed">Cube.hs</span></p>
<pre name="code" class="haskell:ghci">
module Geometry.Cube
( volume
, area
) where
import qualified Geometry.Cuboid as Cuboid
volume :: Float -> Float
volume side = Cuboid.volume side side side
area :: Float -> Float
area side = Cuboid.area side side side
</pre>
<p>Alright! So first is <span class="fixed">Geometry.Sphere</span>. Notice how we placed it in a folder called <span class="fixed">Geometry</span> and then defined the module name as <span class="fixed">Geometry.Sphere</span>. We did the same for the cuboid. Also notice how in all three submodules, we defined functions with the same names. We can do this because they're separate modules. We want to use functions from <span class="fixed">Geometry.Cuboid</span> in <span class="fixed">Geometry.Cube</span> but we can't just straight up do <span class="fixed">import Geometry.Cuboid</span> because it exports functions with the same names as <span class="fixed">Geometry.Cube</span>. That's why we do a qualified import and all is well.</p>
<p>So now if we're in a file that's on the same level as the <span class="fixed">Geometry</span> folder, we can do, say:</p>
<pre name="code" class="haskell:ghci">
import Geometry.Sphere
</pre>
<p>And then we can call <span class="fixed">area</span> and <span class="fixed">volume</span> and they'll give us the area and volume for a sphere. And if we want to juggle two or more of these modules, we have to do qualified imports because they export functions with the same names. So we just do something like:</p>
<pre name="code" class="haskell:ghci">
import qualified Geometry.Sphere as Sphere
import qualified Geometry.Cuboid as Cuboid
import qualified Geometry.Cube as Cube
</pre>
<p>And then we can call <span class="fixed">Sphere.area</span>, <span class="fixed">Sphere.volume</span>, <span class="fixed">Cuboid.area</span>, etc. and each will calculate the area or volume for their corresponding object.</p>
<p>The next time you find yourself writing a file that's really big and has a lot of functions, try to see which functions serve some common purpose and then see if you can put them in their own module. You'll be able to just import your module the next time you're writing a program that requires some of the same functionality.</p>
<div class="footdiv">
<ul>
<li style="text-align:left">
<a href="higher-order-functions.html" class="prevlink">Higher Order Functions</a>
</li>
<li style="text-align:center">
<a href="chapters.html">Table of contents</a>
</li>
<li style="text-align:right">
<a href="making-our-own-types-and-typeclasses.html" class="nxtlink">Making Our Own Types and Typeclasses</a>
</li>
</ul>
</div>
</div>
<script type="text/javascript" src="sh/Scripts/shCore.js"></script>
<script type="text/javascript" src="shBrushHaskell.js"></script>
<script type="text/javascript" src="shBrushPlain.js"></script>
<script type="text/javascript">
dp.SyntaxHighlighter.ClipboardSwf = '/sh/Scripts/clipboard.swf';
dp.SyntaxHighlighter.HighlightAll('code', false, false, false, 1, false);
</script>
</div>
<script type="text/javascript">
var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
</script>
<script type="text/javascript">
var pageTracker = _gat._getTracker("UA-4461592-3");
pageTracker._trackPageview();
</script>
</body>
</html>