forked from learnyouahaskell/learnyouahaskell.github.io
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmaking-our-own-types-and-typeclasses.html
More file actions
1906 lines (1893 loc) · 108 KB
/
making-our-own-types-and-typeclasses.html
File metadata and controls
1906 lines (1893 loc) · 108 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>Making Our Own Types and Typeclasses - 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="modules.html">
<link rel="next" href="input-and-output.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="modules.html" class="prevlink">Modules</a>
</li>
<li style="text-align:center">
<a href="chapters.html">Table of contents</a>
</li>
<li style="text-align:right">
<a href="input-and-output.html" class="nxtlink">Input and Output</a>
</li>
</ul>
</div>
<h1 id="making-our-own-types-and-typeclasses">Making Our Own Types and
Typeclasses</h1>
<p>In the previous chapters, we covered some existing Haskell types and
typeclasses. In this chapter, we’ll learn how to make our own and how to
put them to work!</p>
<h2 id="algebraic-data-types">Algebraic data types intro</h2>
<p>So far, we’ve run into a lot of data types. <code>Bool</code>,
<code>Int</code>, <code>Char</code>, <code>Maybe</code>, etc. But how do
we make our own? Well, one way is to use the <strong>data</strong>
keyword to define a type. Let’s see how the <code>Bool</code> type is
defined in the standard library.</p>
<pre class="haskell:hs"><code>data Bool = False | True</code></pre>
<p><code>data</code> means that we’re defining a new data type. The part
before the <code>=</code> denotes the type, which is <code>Bool</code>.
The parts after the <code>=</code> are <strong>value
constructors</strong>. They specify the different values that this type
can have. The <code>|</code> is read as <em>or</em>. So we can read this
as: the <code>Bool</code> type can have a value of <code>True</code> or
<code>False</code>. Both the type name and the value constructors have
to be capital cased.</p>
<p>In a similar fashion, we can think of the <code>Int</code> type as
being defined like this:</p>
<pre class="haskell:hs"><code>data Int = -2147483648 | -2147483647 | ... | -1 | 0 | 1 | 2 | ... | 2147483647</code></pre>
<p><img
src="assets/images/making-our-own-types-and-typeclasses/caveman.png"
class="left" width="220" height="215" alt="caveman" /></p>
<p>The first and last value constructors are the minimum and maximum
possible values of <code>Int</code>. It’s not actually defined like
this, the ellipses are here because we omitted a heapload of numbers, so
this is just for illustrative purposes.</p>
<p>Now, let’s think about how we would represent a shape in Haskell. One
way would be to use tuples. A circle could be denoted as
<code>(43.1, 55.0, 10.4)</code> where the first and second fields are
the coordinates of the circle’s center and the third field is the
radius. Sounds OK, but those could also represent a 3D vector or
anything else. A better solution would be to make our own type to
represent a shape. Let’s say that a shape can be a circle or a
rectangle. Here it is:</p>
<pre class="haskell:hs"><code>data Shape = Circle Float Float Float | Rectangle Float Float Float Float</code></pre>
<p>Now what’s this? Think of it like this. The <code>Circle</code> value
constructor has three fields, which take floats. So when we write a
value constructor, we can optionally add some types after it and those
types define the values it will contain. Here, the first two fields are
the coordinates of its center, the third one its radius. The
<code>Rectangle</code> value constructor has four fields which accept
floats. The first two are the coordinates to its upper left corner and
the second two are coordinates to its lower right one.</p>
<p>Now when I say fields, I actually mean parameters. Value constructors
are actually functions that ultimately return a value of a data type.
Let’s take a look at the type signatures for these two value
constructors.</p>
<pre class="haskell:hs"><code>ghci> :t Circle
Circle :: Float -> Float -> Float -> Shape
ghci> :t Rectangle
Rectangle :: Float -> Float -> Float -> Float -> Shape</code></pre>
<p>Cool, so value constructors are functions like everything else. Who
would have thought? Let’s make a function that takes a shape and returns
its surface.</p>
<pre class="haskell:hs"><code>surface :: Shape -> Float
surface (Circle _ _ r) = pi * r ^ 2
surface (Rectangle x1 y1 x2 y2) = (abs $ x2 - x1) * (abs $ y2 - y1)</code></pre>
<p>The first notable thing here is the type declaration. It says that
the function takes a shape and returns a float. We couldn’t write a type
declaration of <code>Circle -> Float</code> because
<code>Circle</code> is not a type, <code>Shape</code> is. Just like we
can’t write a function with a type declaration of
<code>True -> Int</code>. The next thing we notice here is that we
can pattern match against constructors. We pattern matched against
constructors before (all the time actually) when we pattern matched
against values like <code>[]</code> or <code>False</code> or
<code>5</code>, only those values didn’t have any fields. We just write
a constructor and then bind its fields to names. Because we’re
interested in the radius, we don’t actually care about the first two
fields, which tell us where the circle is.</p>
<pre class="haskell:hs"><code>ghci> surface $ Circle 10 20 10
314.15927
ghci> surface $ Rectangle 0 0 100 100
10000.0</code></pre>
<p>Yay, it works! But if we try to just print out
<code>Circle 10 20 5</code> in the prompt, we’ll get an error. That’s
because Haskell doesn’t know how to display our data type as a string
(yet). Remember, when we try to print a value out in the prompt, Haskell
first runs the <code>show</code> function to get the string
representation of our value and then it prints that out to the terminal.
To make our <code>Shape</code> type part of the <code>Show</code>
typeclass, we modify it like this:</p>
<pre class="haskell:hs"><code>data Shape = Circle Float Float Float | Rectangle Float Float Float Float deriving (Show)</code></pre>
<p>We won’t concern ourselves with deriving too much for now. Let’s just
say that if we add <code>deriving (Show)</code> at the end of a
<em>data</em> declaration, Haskell automagically makes that type part of
the <code>Show</code> typeclass. So now, we can do this:</p>
<pre class="haskell:hs"><code>ghci> Circle 10 20 5
Circle 10.0 20.0 5.0
ghci> Rectangle 50 230 60 90
Rectangle 50.0 230.0 60.0 90.0</code></pre>
<p>Value constructors are functions, so we can map them and partially
apply them and everything. If we want a list of concentric circles with
different radii, we can do this.</p>
<pre class="haskell:hs"><code>ghci> map (Circle 10 20) [4,5,6,6]
[Circle 10.0 20.0 4.0,Circle 10.0 20.0 5.0,Circle 10.0 20.0 6.0,Circle 10.0 20.0 6.0]</code></pre>
<p>Our data type is good, although it could be better. Let’s make an
intermediate data type that defines a point in two-dimensional space.
Then we can use that to make our shapes more understandable.</p>
<pre class="haskell:hs"><code>data Point = Point Float Float deriving (Show)
data Shape = Circle Point Float | Rectangle Point Point deriving (Show)</code></pre>
<p>Notice that when defining a point, we used the same name for the data
type and the value constructor. This has no special meaning, although
it’s common to use the same name as the type if there’s only one value
constructor. So now the <code>Circle</code> has two fields, one is of
type <code>Point</code> and the other of type <code>Float</code>. This
makes it easier to understand what’s what. Same goes for the rectangle.
We have to adjust our <code>surface</code> function to reflect these
changes.</p>
<pre class="haskell:hs"><code>surface :: Shape -> Float
surface (Circle _ r) = pi * r ^ 2
surface (Rectangle (Point x1 y1) (Point x2 y2)) = (abs $ x2 - x1) * (abs $ y2 - y1)</code></pre>
<p>The only thing we had to change were the patterns. We disregarded the
whole point in the circle pattern. In the rectangle pattern, we just
used a nested pattern matching to get the fields of the points. If we
wanted to reference the points themselves for some reason, we could have
used as-patterns.</p>
<pre class="haskell:hs"><code>ghci> surface (Rectangle (Point 0 0) (Point 100 100))
10000.0
ghci> surface (Circle (Point 0 0) 24)
1809.5574</code></pre>
<p>How about a function that nudges a shape? It takes a shape, the
amount to move it on the x axis and the amount to move it on the y axis
and then returns a new shape that has the same dimensions, only it’s
located somewhere else.</p>
<pre class="haskell:hs"><code>nudge :: Shape -> Float -> Float -> Shape
nudge (Circle (Point x y) r) a b = Circle (Point (x+a) (y+b)) r
nudge (Rectangle (Point x1 y1) (Point x2 y2)) a b = Rectangle (Point (x1+a) (y1+b)) (Point (x2+a) (y2+b))</code></pre>
<p>Pretty straightforward. We add the nudge amounts to the points that
denote the position of the shape.</p>
<pre class="haskell:hs"><code>ghci> nudge (Circle (Point 34 34) 10) 5 10
Circle (Point 39.0 44.0) 10.0</code></pre>
<p>If we don’t want to deal directly with points, we can make some
auxiliary functions that create shapes of some size at the zero
coordinates and then nudge those.</p>
<pre class="haskell:hs"><code>baseCircle :: Float -> Shape
baseCircle r = Circle (Point 0 0) r
baseRect :: Float -> Float -> Shape
baseRect width height = Rectangle (Point 0 0) (Point width height)</code></pre>
<pre class="haskell:hs"><code>ghci> nudge (baseRect 40 100) 60 23
Rectangle (Point 60.0 23.0) (Point 100.0 123.0)</code></pre>
<p>You can, of course, export your data types in your modules. To do
that, just write your type along with the functions you are exporting
and then add some parentheses and in them specify the value constructors
that you want to export for it, separated by commas. If you want to
export all the value constructors for a given type, just write
<code>..</code>.</p>
<p>If we wanted to export the functions and types that we defined here
in a module, we could start it off like this:</p>
<pre class="haskell:hs"><code>module Shapes
( Point(..)
, Shape(..)
, surface
, nudge
, baseCircle
, baseRect
) where</code></pre>
<p>By doing <code>Shape(..)</code>, we exported all the value
constructors for <code>Shape</code>, so that means that whoever imports
our module can make shapes by using the <code>Rectangle</code> and
<code>Circle</code> value constructors. It’s the same as writing
<code>Shape (Rectangle, Circle)</code>.</p>
<p>We could also opt not to export any value constructors for
<code>Shape</code> by just writing <code>Shape</code> in the export
statement. That way, someone importing our module could only make shapes
by using the auxiliary functions <code>baseCircle</code> and
<code>baseRect</code>. <code>Data.Map</code> uses that approach. You
can’t create a map by doing <code>Map.Map [(1,2),(3,4)]</code> because
it doesn’t export that value constructor. However, you can make a
mapping by using one of the auxiliary functions like
<code>Map.fromList</code>. Remember, value constructors are just
functions that take the fields as parameters and return a value of some
type (like <code>Shape</code>) as a result. So when we choose not to
export them, we just prevent the person importing our module from using
those functions, but if some other functions that are exported return a
type, we can use them to make values of our custom data types.</p>
<p>Not exporting the value constructors of a data types makes them more
abstract in such a way that we hide their implementation. Also, whoever
uses our module can’t pattern match against the value constructors.</p>
<h2 id="record-syntax">Record syntax</h2>
<p><img
src="assets/images/making-our-own-types-and-typeclasses/record.png"
class="right" width="208" height="97" alt="record" /></p>
<p>OK, we’ve been tasked with creating a data type that describes a
person. The info that we want to store about that person is: first name,
last name, age, height, phone number, and favorite ice-cream flavor. I
don’t know about you, but that’s all I ever want to know about a person.
Let’s give it a go!</p>
<pre class="haskell:hs"><code>data Person = Person String String Int Float String String deriving (Show)</code></pre>
<p>O-kay. The first field is the first name, the second is the last
name, the third is the age and so on. Let’s make a person.</p>
<pre class="haskell:hs"><code>ghci> let guy = Person "Buddy" "Finklestein" 43 184.2 "526-2928" "Chocolate"
ghci> guy
Person "Buddy" "Finklestein" 43 184.2 "526-2928" "Chocolate"</code></pre>
<p>That’s kind of cool, although slightly unreadable. What if we want to
create a function to get separate info from a person? A function that
gets some person’s first name, a function that gets some person’s last
name, etc. Well, we’d have to define them kind of like this.</p>
<pre class="haskell:hs"><code>firstName :: Person -> String
firstName (Person firstname _ _ _ _ _) = firstname
lastName :: Person -> String
lastName (Person _ lastname _ _ _ _) = lastname
age :: Person -> Int
age (Person _ _ age _ _ _) = age
height :: Person -> Float
height (Person _ _ _ height _ _) = height
phoneNumber :: Person -> String
phoneNumber (Person _ _ _ _ number _) = number
flavor :: Person -> String
flavor (Person _ _ _ _ _ flavor) = flavor</code></pre>
<p>Whew! I certainly did not enjoy writing that! Despite being very
cumbersome and BORING to write, this method works.</p>
<pre class="haskell:hs"><code>ghci> let guy = Person "Buddy" "Finklestein" 43 184.2 "526-2928" "Chocolate"
ghci> firstName guy
"Buddy"
ghci> height guy
184.2
ghci> flavor guy
"Chocolate"</code></pre>
<p>There must be a better way, you say! Well no, there isn’t, sorry.</p>
<p>Just kidding, there is. Hahaha! The makers of Haskell were very smart
and anticipated this scenario. They included an alternative way to write
data types. Here’s how we could achieve the above functionality with
record syntax.</p>
<pre class="haskell:hs"><code>data Person = Person { firstName :: String
, lastName :: String
, age :: Int
, height :: Float
, phoneNumber :: String
, flavor :: String
} deriving (Show)</code></pre>
<p>So instead of just naming the field types one after another and
separating them with spaces, we use curly brackets. First we write the
name of the field, for instance, <code>firstName</code> and then we
write a double colon <code>::</code> (also called Paamayim Nekudotayim,
haha) and then we specify the type. The resulting data type is exactly
the same. The main benefit of this is that it creates functions that
lookup fields in the data type. By using record syntax to create this
data type, Haskell automatically made these functions:
<code>firstName</code>, <code>lastName</code>, <code>age</code>,
<code>height</code>, <code>phoneNumber</code> and
<code>flavor</code>.</p>
<pre class="haskell:hs"><code>ghci> :t flavor
flavor :: Person -> String
ghci> :t firstName
firstName :: Person -> String</code></pre>
<p>There’s another benefit to using record syntax. When we derive
<code>Show</code> for the type, it displays it differently if we use
record syntax to define and instantiate the type. Say we have a type
that represents a car. We want to keep track of the company that made
it, the model name and its year of production. Watch.</p>
<pre class="haskell:hs"><code>data Car = Car String String Int deriving (Show)</code></pre>
<pre class="haskell:hs"><code>ghci> Car "Ford" "Mustang" 1967
Car "Ford" "Mustang" 1967</code></pre>
<p>If we define it using record syntax, we can make a new car like
this.</p>
<pre class="haskell:hs"><code>data Car = Car {company :: String, model :: String, year :: Int} deriving (Show)</code></pre>
<pre class="haskell:hs"><code>ghci> Car {company="Ford", model="Mustang", year=1967}
Car {company = "Ford", model = "Mustang", year = 1967}</code></pre>
<p>When making a new car, we don’t have to necessarily put the fields in
the proper order, as long as we list all of them. But if we don’t use
record syntax, we have to specify them in order.</p>
<p>Use record syntax when a constructor has several fields and it’s not
obvious which field is which. If we make a 3D vector data type by doing
<code>data Vector = Vector Int Int Int</code>, it’s pretty obvious that
the fields are the components of a vector. However, in our
<code>Person</code> and <code>Car</code> types, it wasn’t so obvious and
we greatly benefited from using record syntax.</p>
<h2 id="type-parameters">Type parameters</h2>
<p>A value constructor can take some values parameters and then produce
a new value. For instance, the <code>Car</code> constructor takes three
values and produces a car value. In a similar manner, <strong>type
constructors</strong> can take types as parameters to produce new types.
This might sound a bit too meta at first, but it’s not that complicated.
If you’re familiar with templates in C++, you’ll see some parallels. To
get a clear picture of what type parameters work like in action, let’s
take a look at how a type we’ve already met is implemented.</p>
<pre class="haskell:hs"><code>data Maybe a = Nothing | Just a</code></pre>
<p><img
src="assets/images/making-our-own-types-and-typeclasses/yeti.png"
class="left" width="209" height="260" alt="yeti" /></p>
<p>The <code>a</code> here is the type parameter. And because there’s a
type parameter involved, we call <code>Maybe</code> a type constructor.
Depending on what we want this data type to hold when it’s not
<code>Nothing</code>, this type constructor can end up producing a type
of <code>Maybe Int</code>, <code>Maybe Car</code>,
<code>Maybe String</code>, etc. No value can have a type of just
<code>Maybe</code>, because that’s not a type per se, it’s a type
constructor. In order for this to be a real type that a value can be
part of, it has to have all its type parameters filled up.</p>
<p>So if we pass <code>Char</code> as the type parameter to
<code>Maybe</code>, we get a type of <code>Maybe Char</code>. The value
<code>Just 'a'</code> has a type of <code>Maybe Char</code>, for
example.</p>
<p>You might not know it, but we used a type that has a type parameter
before we used <code>Maybe</code>. That type is the list type. Although
there’s some syntactic sugar in play, the list type takes a parameter to
produce a concrete type. Values can have an <code>[Int]</code> type, a
<code>[Char]</code> type, a <code>[[String]]</code> type, but you can’t
have a value that just has a type of <code>[]</code>.</p>
<p>Let’s play around with the <code>Maybe</code> type.</p>
<pre class="haskell:hs"><code>ghci> Just "Haha"
Just "Haha"
ghci> Just 84
Just 84
ghci> :t Just "Haha"
Just "Haha" :: Maybe [Char]
ghci> :t Just 84
Just 84 :: (Num t) => Maybe t
ghci> :t Nothing
Nothing :: Maybe a
ghci> Just 10 :: Maybe Double
Just 10.0</code></pre>
<p>Type parameters are useful because we can make different types with
them depending on what kind of types we want contained in our data type.
When we do <code>:t Just "Haha"</code>, the type inference engine
figures it out to be of the type <code>Maybe [Char]</code>, because if
the <code>a</code> in the <code>Just a</code> is a string, then the
<code>a</code> in <code>Maybe a</code> must also be a string.</p>
<p>Notice that the type of <code>Nothing</code> is <code>Maybe a</code>.
Its type is polymorphic. If some function requires a
<code>Maybe Int</code> as a parameter, we can give it a
<code>Nothing</code>, because a <code>Nothing</code> doesn’t contain a
value anyway and so it doesn’t matter. The <code>Maybe a</code> type can
act like a <code>Maybe Int</code> if it has to, just like <code>5</code>
can act like an <code>Int</code> or a <code>Double</code>. Similarly,
the type of the empty list is <code>[a]</code>. An empty list can act
like a list of anything. That’s why we can do <code>[1,2,3] ++ []</code>
and <code>["ha","ha","ha"] ++ []</code>.</p>
<p>Using type parameters is very beneficial, but only when using them
makes sense. Usually we use them when our data type would work
regardless of the type of the value it then holds inside it, like with
our <code>Maybe a</code> type. If our type acts as some kind of box,
it’s good to use them. We could change our <code>Car</code> data type
from this:</p>
<pre class="haskell:hs"><code>data Car = Car { company :: String
, model :: String
, year :: Int
} deriving (Show)</code></pre>
<p>To this:</p>
<pre class="haskell:hs"><code>data Car a b c = Car { company :: a
, model :: b
, year :: c
} deriving (Show)</code></pre>
<p>But would we really benefit? The answer is: probably no, because we’d
just end up defining functions that only work on the
<code>Car String String Int</code> type. For instance, given our first
definition of <code>Car</code>, we could make a function that displays
the car’s properties in a nice little text.</p>
<pre class="haskell:hs"><code>tellCar :: Car -> String
tellCar (Car {company = c, model = m, year = y}) = "This " ++ c ++ " " ++ m ++ " was made in " ++ show y</code></pre>
<pre class="haskell:hs"><code>ghci> let stang = Car {company="Ford", model="Mustang", year=1967}
ghci> tellCar stang
"This Ford Mustang was made in 1967"</code></pre>
<p>A cute little function! The type declaration is cute and it works
nicely. Now what if <code>Car</code> was <code>Car a b c</code>?</p>
<pre class="haskell:hs"><code>tellCar :: (Show a) => Car String String a -> String
tellCar (Car {company = c, model = m, year = y}) = "This " ++ c ++ " " ++ m ++ " was made in " ++ show y</code></pre>
<p>We’d have to force this function to take a <code>Car</code> type of
<code>(Show a) => Car String String a</code>. You can see that the
type signature is more complicated and the only benefit we’d actually
get would be that we can use any type that’s an instance of the
<code>Show</code> typeclass as the type for <code>c</code>.</p>
<pre class="haskell:hs"><code>ghci> tellCar (Car "Ford" "Mustang" 1967)
"This Ford Mustang was made in 1967"
ghci> tellCar (Car "Ford" "Mustang" "nineteen sixty seven")
"This Ford Mustang was made in \"nineteen sixty seven\""
ghci> :t Car "Ford" "Mustang" 1967
Car "Ford" "Mustang" 1967 :: (Num t) => Car [Char] [Char] t
ghci> :t Car "Ford" "Mustang" "nineteen sixty seven"
Car "Ford" "Mustang" "nineteen sixty seven" :: Car [Char] [Char] [Char]</code></pre>
<p><img
src="assets/images/making-our-own-types-and-typeclasses/meekrat.png"
class="right" width="150" height="267" alt="meekrat" /></p>
<p>In real life though, we’d end up using
<code>Car String String Int</code> most of the time and so it would seem
that parameterizing the <code>Car</code> type isn’t really worth it. We
usually use type parameters when the type that’s contained inside the
data type’s various value constructors isn’t really that important for
the type to work. A list of stuff is a list of stuff and it doesn’t
matter what the type of that stuff is, it can still work. If we want to
sum a list of numbers, we can specify later in the summing function that
we specifically want a list of numbers. Same goes for
<code>Maybe</code>. <code>Maybe</code> represents an option of either
having nothing or having one of something. It doesn’t matter what the
type of that something is.</p>
<p>Another example of a parameterized type that we’ve already met is
<code>Map k v</code> from <code>Data.Map</code>. The <code>k</code> is
the type of the keys in a map and the <code>v</code> is the type of the
values. This is a good example of where type parameters are very useful.
Having maps parameterized enables us to have mappings from any type to
any other type, as long as the type of the key is part of the
<code>Ord</code> typeclass. If we were defining a mapping type, we could
add a typeclass constraint in the <em>data</em> declaration:</p>
<pre class="haskell:hs"><code>data (Ord k) => Map k v = ...</code></pre>
<p>However, it’s a very strong convention in Haskell to <strong>never
add typeclass constraints in data declarations.</strong> Why? Well,
because we don’t benefit a lot, but we end up writing more class
constraints, even when we don’t need them. If we put or don’t put the
<code>Ord k</code> constraint in the <em>data</em> declaration for
<code>Map k v</code>, we’re going to have to put the constraint into
functions that assume the keys in a map can be ordered. But if we don’t
put the constraint in the data declaration, we don’t have to put
<code>(Ord k) =></code> in the type declarations of functions that
don’t care whether the keys can be ordered or not. An example of such a
function is <code>toList</code>, that just takes a mapping and converts
it to an associative list. Its type signature is
<code>toList :: Map k a -> [(k, a)]</code>. If <code>Map k v</code>
had a type constraint in its <em>data</em> declaration, the type for
<code>toList</code> would have to be
<code>toList :: (Ord k) => Map k a -> [(k, a)]</code>, even though
the function doesn’t do any comparing of keys by order.</p>
<p>So don’t put type constraints into <em>data</em> declarations even if
it seems to make sense, because you’ll have to put them into the
function type declarations either way.</p>
<p>Let’s implement a 3D vector type and add some operations for it.
We’ll be using a parameterized type because even though it will usually
contain numeric types, it will still support several of them.</p>
<pre class="haskell:hs"><code>data Vector a = Vector a a a deriving (Show)
vplus :: (Num t) => Vector t -> Vector t -> Vector t
(Vector i j k) `vplus` (Vector l m n) = Vector (i+l) (j+m) (k+n)
vectMult :: (Num t) => Vector t -> t -> Vector t
(Vector i j k) `vectMult` m = Vector (i*m) (j*m) (k*m)
scalarMult :: (Num t) => Vector t -> Vector t -> t
(Vector i j k) `scalarMult` (Vector l m n) = i*l + j*m + k*n</code></pre>
<p><code>vplus</code> is for adding two vectors together. Two vectors
are added just by adding their corresponding components.
<code>scalarMult</code> is for the scalar product of two vectors and
<code>vectMult</code> is for multiplying a vector with a scalar. These
functions can operate on types of <code>Vector Int</code>,
<code>Vector Integer</code>, <code>Vector Float</code>, whatever, as
long as the <code>a</code> from <code>Vector a</code> is from the
<code>Num</code> typeclass. Also, if you examine the type declaration
for these functions, you’ll see that they can operate only on vectors of
the same type and the numbers involved must also be of the type that is
contained in the vectors. Notice that we didn’t put a <code>Num</code>
class constraint in the <em>data</em> declaration, because we’d have to
repeat it in the functions anyway.</p>
<p>Once again, it’s very important to distinguish between the type
constructor and the value constructor. When declaring a data type, the
part before the <code>=</code> is the type constructor and the
constructors after it (possibly separated by <code>|</code>’s) are value
constructors. Giving a function a type of
<code>Vector t t t -> Vector t t t -> t</code> would be wrong,
because we have to put types in type declaration and the vector
<strong>type</strong> constructor takes only one parameter, whereas the
value constructor takes three. Let’s play around with our vectors.</p>
<pre class="haskell:hs"><code>ghci> Vector 3 5 8 `vplus` Vector 9 2 8
Vector 12 7 16
ghci> Vector 3 5 8 `vplus` Vector 9 2 8 `vplus` Vector 0 2 3
Vector 12 9 19
ghci> Vector 3 9 7 `vectMult` 10
Vector 30 90 70
ghci> Vector 4 9 5 `scalarMult` Vector 9.0 2.0 4.0
74.0
ghci> Vector 2 9 3 `vectMult` (Vector 4 9 5 `scalarMult` Vector 9 2 4)
Vector 148 666 222</code></pre>
<h2 id="derived-instances">Derived instances</h2>
<p><img src="assets/images/making-our-own-types-and-typeclasses/gob.png"
class="right" width="112" height="350" alt="gob" /></p>
<p>In the <a
href="types-and-typeclasses.html#typeclasses-101">Typeclasses 101</a>
section, we explained the basics of typeclasses. We explained that a
typeclass is a sort of an interface that defines some behavior. A type
can be made an <strong>instance</strong> of a typeclass if it supports
that behavior. Example: the <code>Int</code> type is an instance of the
<code>Eq</code> typeclass because the <code>Eq</code> typeclass defines
behavior for stuff that can be equated. And because integers can be
equated, <code>Int</code> is a part of the <code>Eq</code> typeclass.
The real usefulness comes with the functions that act as the interface
for <code>Eq</code>, namely <code>==</code> and <code>/=</code>. If a
type is a part of the <code>Eq</code> typeclass, we can use the
<code>==</code> functions with values of that type. That’s why
expressions like <code>4 == 4</code> and <code>"foo" /= "bar"</code>
typecheck.</p>
<p>We also mentioned that they’re often confused with classes in
languages like Java, Python, C++ and the like, which then baffles a lot
of people. In those languages, classes are a blueprint from which we
then create objects that contain state and can do some actions.
Typeclasses are more like interfaces. We don’t make data from
typeclasses. Instead, we first make our data type and then we think
about what it can act like. If it can act like something that can be
equated, we make it an instance of the <code>Eq</code> typeclass. If it
can act like something that can be ordered, we make it an instance of
the <code>Ord</code> typeclass.</p>
<p>In the next section, we’ll take a look at how we can manually make
our types instances of typeclasses by implementing the functions defined
by the typeclasses. But right now, let’s see how Haskell can
automatically make our type an instance of any of the following
typeclasses: <code>Eq</code>, <code>Ord</code>, <code>Enum</code>,
<code>Bounded</code>, <code>Show</code>, <code>Read</code>. Haskell can
derive the behavior of our types in these contexts if we use the
<em>deriving</em> keyword when making our data type.</p>
<p>Consider this data type:</p>
<pre class="haskell:hs"><code>data Person = Person { firstName :: String
, lastName :: String
, age :: Int
}</code></pre>
<p>It describes a person. Let’s assume that no two people have the same
combination of first name, last name and age. Now, if we have records
for two people, does it make sense to see if they represent the same
person? Sure it does. We can try to equate them and see if they’re equal
or not. That’s why it would make sense for this type to be part of the
<code>Eq</code> typeclass. We’ll derive the instance.</p>
<pre class="haskell:hs"><code>data Person = Person { firstName :: String
, lastName :: String
, age :: Int
} deriving (Eq)</code></pre>
<p>When we derive the <code>Eq</code> instance for a type and then try
to compare two values of that type with <code>==</code> or
<code>/=</code>, Haskell will see if the value constructors match
(there’s only one value constructor here though) and then it will check
if all the data contained inside matches by testing each pair of fields
with <code>==</code>. There’s only one catch though, the types of all
the fields also have to be part of the <code>Eq</code> typeclass. But
since both <code>String</code> and <code>Int</code> are, we’re OK. Let’s
test our <code>Eq</code> instance.</p>
<pre class="haskell:hs"><code>ghci> let mikeD = Person {firstName = "Michael", lastName = "Diamond", age = 43}
ghci> let adRock = Person {firstName = "Adam", lastName = "Horovitz", age = 41}
ghci> let mca = Person {firstName = "Adam", lastName = "Yauch", age = 44}
ghci> mca == adRock
False
ghci> mikeD == adRock
False
ghci> mikeD == mikeD
True
ghci> mikeD == Person {firstName = "Michael", lastName = "Diamond", age = 43}
True</code></pre>
<p>Of course, since <code>Person</code> is now in <code>Eq</code>, we
can use it as the <code>a</code> for all functions that have a class
constraint of <code>Eq a</code> in their type signature, such as
<code>elem</code>.</p>
<pre class="haskell:hs"><code>ghci> let beastieBoys = [mca, adRock, mikeD]
ghci> mikeD `elem` beastieBoys
True</code></pre>
<p>The <code>Show</code> and <code>Read</code> typeclasses are for
things that can be converted to or from strings, respectively. Like with
<code>Eq</code>, if a type’s constructors have fields, their type has to
be a part of <code>Show</code> or <code>Read</code> if we want to make
our type an instance of them. Let’s make our <code>Person</code> data
type a part of <code>Show</code> and <code>Read</code> as well.</p>
<pre class="haskell:hs"><code>data Person = Person { firstName :: String
, lastName :: String
, age :: Int
} deriving (Eq, Show, Read)</code></pre>
<p>Now we can print a person out to the terminal.</p>
<pre class="haskell:hs"><code>ghci> let mikeD = Person {firstName = "Michael", lastName = "Diamond", age = 43}
ghci> mikeD
Person {firstName = "Michael", lastName = "Diamond", age = 43}
ghci> "mikeD is: " ++ show mikeD
"mikeD is: Person {firstName = \"Michael\", lastName = \"Diamond\", age = 43}"</code></pre>
<p>Had we tried to print a person on the terminal before making the
<code>Person</code> data type part of <code>Show</code>, Haskell would
have complained at us, claiming it doesn’t know how to represent a
person as a string. But now that we’ve derived a <code>Show</code>
instance for it, it does know.</p>
<p><code>Read</code> is pretty much the inverse typeclass of
<code>Show</code>. <code>Show</code> is for converting values of our a
type to a string, <code>Read</code> is for converting strings to values
of our type. Remember though, when we use the <code>read</code>
function, we have to use an explicit type annotation to tell Haskell
which type we want to get as a result. If we don’t make the type we want
as a result explicit, Haskell doesn’t know which type we want.</p>
<pre class="haskell:hs"><code>ghci> read "Person {firstName =\"Michael\", lastName =\"Diamond\", age = 43}" :: Person
Person {firstName = "Michael", lastName = "Diamond", age = 43}</code></pre>
<p>If we use the result of our <code>read</code> later on in a way that
Haskell can infer that it should read it as a person, we don’t have to
use type annotation.</p>
<pre class="haskell:hs"><code>ghci> read "Person {firstName =\"Michael\", lastName =\"Diamond\", age = 43}" == mikeD
True</code></pre>
<p>We can also read parameterized types, but we have to fill in the type
parameters. So we can’t do <code>read "Just 't'" :: Maybe a</code>, but
we can do <code>read "Just 't'" :: Maybe Char</code>.</p>
<p>We can derive instances for the <code>Ord</code> type class, which is
for types that have values that can be ordered. If we compare two values
of the same type that were made using different constructors, the value
which was made with a constructor that’s defined first is considered
smaller. For instance, consider the <code>Bool</code> type, which can
have a value of either <code>False</code> or <code>True</code>. For the
purpose of seeing how it behaves when compared, we can think of it as
being implemented like this:</p>
<pre class="haskell:hs"><code>data Bool = False | True deriving (Ord)</code></pre>
<p>Because the <code>False</code> value constructor is specified first
and the <code>True</code> value constructor is specified after it, we
can consider <code>True</code> as greater than <code>False</code>.</p>
<pre class="haskell:hs"><code>ghci> True `compare` False
GT
ghci> True > False
True
ghci> True < False
False</code></pre>
<p>In the <code>Maybe a</code> data type, the <code>Nothing</code> value
constructor is specified before the <code>Just</code> value constructor,
so a value of <code>Nothing</code> is always smaller than a value of
<code>Just something</code>, even if that something is minus one billion
trillion. But if we compare two <code>Just</code> values, then it goes
to compare what’s inside them.</p>
<pre class="haskell:hs"><code>ghci> Nothing < Just 100
True
ghci> Nothing > Just (-49999)
False
ghci> Just 3 `compare` Just 2
GT
ghci> Just 100 > Just 50
True</code></pre>
<p>But we can’t do something like <code>Just (*3) > Just (*2)</code>,
because <code>(*3)</code> and <code>(*2)</code> are functions, which
aren’t instances of <code>Ord</code>.</p>
<p>We can easily use algebraic data types to make enumerations and the
<code>Enum</code> and <code>Bounded</code> typeclasses help us with
that. Consider the following data type:</p>
<pre class="haskell:hs"><code>data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday</code></pre>
<p>Because all the value constructors are nullary (take no parameters,
i.e. fields), we can make it part of the <code>Enum</code> typeclass.
The <code>Enum</code> typeclass is for things that have predecessors and
successors. We can also make it part of the <code>Bounded</code>
typeclass, which is for things that have a lowest possible value and
highest possible value. And while we’re at it, let’s also make it an
instance of all the other derivable typeclasses and see what we can do
with it.</p>
<pre class="haskell:hs"><code>data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday
deriving (Eq, Ord, Show, Read, Bounded, Enum)</code></pre>
<p>Because it’s part of the <code>Show</code> and <code>Read</code>
typeclasses, we can convert values of this type to and from strings.</p>
<pre class="haskell:hs"><code>ghci> Wednesday
Wednesday
ghci> show Wednesday
"Wednesday"
ghci> read "Saturday" :: Day
Saturday</code></pre>
<p>Because it’s part of the <code>Eq</code> and <code>Ord</code>
typeclasses, we can compare or equate days.</p>
<pre class="haskell:hs"><code>ghci> Saturday == Sunday
False
ghci> Saturday == Saturday
True
ghci> Saturday > Friday
True
ghci> Monday `compare` Wednesday
LT</code></pre>
<p>It’s also part of <code>Bounded</code>, so we can get the lowest and
highest day.</p>
<pre class="haskell:hs"><code>ghci> minBound :: Day
Monday
ghci> maxBound :: Day
Sunday</code></pre>
<p>It’s also an instance of <code>Enum</code>. We can get predecessors
and successors of days and we can make list ranges from them!</p>
<pre class="haskell:hs"><code>ghci> succ Monday
Tuesday
ghci> pred Saturday
Friday
ghci> [Thursday .. Sunday]
[Thursday,Friday,Saturday,Sunday]
ghci> [minBound .. maxBound] :: [Day]
[Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday]</code></pre>
<p>That’s pretty awesome.</p>
<h2 id="type-synonyms">Type synonyms</h2>
<p>Previously, we mentioned that when writing types, the
<code>[Char]</code> and <code>String</code> types are equivalent and
interchangeable. That’s implemented with <strong>type synonyms</strong>.
Type synonyms don’t really do anything per se, they’re just about giving
some types different names so that they make more sense to someone
reading our code and documentation. Here’s how the standard library
defines <code>String</code> as a synonym for <code>[Char]</code>.</p>
<pre class="haskell:hs"><code>type String = [Char]</code></pre>
<p><img
src="assets/images/making-our-own-types-and-typeclasses/chicken.png"
class="left" width="169" height="225" alt="chicken" /></p>
<p>We’ve introduced the <em>type</em> keyword. The keyword might be
misleading to some, because we’re not actually making anything new (we
did that with the <em>data</em> keyword), but we’re just making a
synonym for an already existing type.</p>
<p>If we make a function that converts a string to uppercase and call it
<code>toUpperString</code> or something, we can give it a type
declaration of <code>toUpperString :: [Char] -> [Char]</code> or
<code>toUpperString :: String -> String</code>. Both of these are
essentially the same, only the latter is nicer to read.</p>
<p>When we were dealing with the <code>Data.Map</code> module, we first
represented a phonebook with an association list before converting it
into a map. As we’ve already found out, an association list is a list of
key-value pairs. Let’s look at a phonebook that we had.</p>
<pre class="haskell:hs"><code>phoneBook :: [(String,String)]
phoneBook =
[("amelia","555-2938")
,("freya","452-2928")
,("isabella","493-2928")
,("neil","205-2928")
,("roald","939-8282")
,("tenzing","853-2492")
]</code></pre>
<p>We see that the type of <code>phoneBook</code> is
<code>[(String,String)]</code>. That tells us that it’s an association
list that maps from strings to strings, but not much else. Let’s make a
type synonym to convey some more information in the type
declaration.</p>
<pre class="haskell:hs"><code>type PhoneBook = [(String,String)]</code></pre>
<p>Now the type declaration for our phonebook can be
<code>phoneBook :: PhoneBook</code>. Let’s make a type synonym for
<code>String</code> as well.</p>
<pre class="haskell:hs"><code>type PhoneNumber = String
type Name = String
type PhoneBook = [(Name,PhoneNumber)]</code></pre>
<p>Giving the <code>String</code> type synonyms is something that
Haskell programmers do when they want to convey more information about
what strings in their functions should be used as and what they
represent.</p>
<p>So now, when we implement a function that takes a name and a number
and sees if that name and number combination is in our phonebook, we can
give it a very pretty and descriptive type declaration.</p>
<pre class="haskell:hs"><code>inPhoneBook :: Name -> PhoneNumber -> PhoneBook -> Bool
inPhoneBook name pnumber pbook = (name,pnumber) `elem` pbook</code></pre>
<p>If we decided not to use type synonyms, our function would have a
type of
<code>String -> String -> [(String,String)] -> Bool</code>. In
this case, the type declaration that took advantage of type synonyms is
easier to understand. However, you shouldn’t go overboard with them. We
introduce type synonyms either to describe what some existing type
represents in our functions (and thus our type declarations become
better documentation) or when something has a long-ish type that’s
repeated a lot (like <code>[(String,String)]</code>) but represents
something more specific in the context of our functions.</p>
<p>Type synonyms can also be parameterized. If we want a type that
represents an association list type but still want it to be general so
it can use any type as the keys and values, we can do this:</p>
<pre class="haskell:hs"><code>type AssocList k v = [(k,v)]</code></pre>
<p>Now, a function that gets the value by a key in an association list
can have a type of
<code>(Eq k) => k -> AssocList k v -> Maybe v</code>.
<code>AssocList</code> is a type constructor that takes two types and
produces a concrete type, like <code>AssocList Int String</code>, for
instance.</p>
<div class="hintbox">
<p><strong>Fonzie says:</strong> Aaay! When I talk about <em>concrete
types</em> I mean like fully applied types like
<code>Map Int String</code> or if we’re dealin’ with one of them
polymorphic functions, <code>[a]</code> or
<code>(Ord a) => Maybe a</code> and stuff. And like, sometimes me and
my buddies say that <code>Maybe</code> is a type, but we don’t mean
that, cause every idiot knows <code>Maybe</code> is a type constructor.
When I apply an extra type to <code>Maybe</code>, like
<code>Maybe String</code>, then I have a concrete type. You know, values
can only have types that are concrete types! So in conclusion, live
fast, love hard and don’t let anybody else use your comb!</p>
</div>
<p>Just like we can partially apply functions to get new functions, we
can partially apply type parameters and get new type constructors from
them. Just like we call a function with too few parameters to get back a
new function, we can specify a type constructor with too few type
parameters and get back a partially applied type constructor. If we
wanted a type that represents a map (from <code>Data.Map</code>) from
integers to something, we could either do this:</p>
<pre class="haskell:hs"><code>type IntMap v = Map Int v</code></pre>
<p>Or we could do it like this:</p>
<pre class="haskell:hs"><code>type IntMap = Map Int</code></pre>
<p>Either way, the <code>IntMap</code> type constructor takes one
parameter and that is the type of what the integers will point to.</p>
<div class="hintbox">
<p><strong>Oh yeah</strong>. If you’re going to try and implement this,
you’ll probably going to do a qualified import of <code>Data.Map</code>.
When you do a qualified import, type constructors also have to be
preceded with a module name. So you’d write
<code>type IntMap = Map.Map Int</code>.</p>
</div>
<p>Make sure that you really understand the distinction between type
constructors and value constructors. Just because we made a type synonym
called <code>IntMap</code> or <code>AssocList</code> doesn’t mean that
we can do stuff like <code>AssocList [(1,2),(4,5),(7,9)]</code>. All it
means is that we can refer to its type by using different names. We can
do <code>[(1,2),(3,5),(8,9)] :: AssocList Int Int</code>, which will
make the numbers inside assume a type of <code>Int</code>, but we can
still use that list as we would any normal list that has pairs of
integers inside. Type synonyms (and types generally) can only be used in
the type portion of Haskell. We’re in Haskell’s type portion whenever
we’re defining new types (so in <em>data</em> and <em>type</em>
declarations) or when we’re located after a <code>::</code>. The
<code>::</code> is in type declarations or in type annotations.</p>
<p>Another cool data type that takes two types as its parameters is the
<code>Either a b</code> type. This is roughly how it’s defined:</p>
<pre class="haskell:hs"><code>data Either a b = Left a | Right b deriving (Eq, Ord, Read, Show)</code></pre>
<p>It has two value constructors. If the <code>Left</code> is used, then
its contents are of type <code>a</code> and if <code>Right</code> is
used, then its contents are of type <code>b</code>. So we can use this
type to encapsulate a value of one type or another and then when we get
a value of type <code>Either a b</code>, we usually pattern match on
both <code>Left</code> and <code>Right</code> and we different stuff
based on which one of them it was.</p>
<pre class="haskell:hs"><code>ghci> Right 20
Right 20
ghci> Left "w00t"
Left "w00t"
ghci> :t Right 'a'
Right 'a' :: Either a Char
ghci> :t Left True
Left True :: Either Bool b</code></pre>
<p>So far, we’ve seen that <code>Maybe a</code> was mostly used to
represent the results of computations that could have either failed or
not. But sometimes, <code>Maybe a</code> isn’t good enough because
<code>Nothing</code> doesn’t really convey much information other than
that something has failed. That’s cool for functions that can fail in
only one way or if we’re just not interested in how and why they failed.
A <code>Data.Map</code> lookup fails only if the key we were looking for
wasn’t in the map, so we know exactly what happened. However, when we’re
interested in how some function failed or why, we usually use the result
type of <code>Either a b</code>, where <code>a</code> is some sort of
type that can tell us something about the possible failure and
<code>b</code> is the type of a successful computation. Hence, errors
use the <code>Left</code> value constructor while results use
<code>Right</code>.</p>
<p>An example: a high-school has lockers so that students have some
place to put their Guns’n’Roses posters. Each locker has a code
combination. When a student wants a new locker, they tell the locker
supervisor which locker number they want and he gives them the code.
However, if someone is already using that locker, he can’t tell them the
code for the locker and they have to pick a different one. We’ll use a
map from <code>Data.Map</code> to represent the lockers. It’ll map from
locker numbers to a pair of whether the locker is in use or not and the
locker code.</p>
<pre class="haskell:hs"><code>import qualified Data.Map as Map
data LockerState = Taken | Free deriving (Show, Eq)
type Code = String
type LockerMap = Map.Map Int (LockerState, Code)</code></pre>
<p>Simple stuff. We introduce a new data type to represent whether a
locker is taken or free and we make a type synonym for the locker code.
We also make a type synonym for the type that maps from integers to
pairs of locker state and code. And now, we’re going to make a function
that searches for the code in a locker map. We’re going to use an
<code>Either String Code</code> type to represent our result, because
our lookup can fail in two ways — the locker can be taken, in which case
we can’t tell the code or the locker number might not exist at all. If
the lookup fails, we’re just going to use a <code>String</code> to tell
what’s happened.</p>
<pre class="haskell:hs"><code>lockerLookup :: Int -> LockerMap -> Either String Code
lockerLookup lockerNumber map =
case Map.lookup lockerNumber map of
Nothing -> Left $ "Locker number " ++ show lockerNumber ++ " doesn't exist!"
Just (state, code) -> if state /= Taken
then Right code
else Left $ "Locker " ++ show lockerNumber ++ " is already taken!"</code></pre>
<p>We do a normal lookup in the map. If we get a <code>Nothing</code>,
we return a value of type <code>Left String</code>, saying that the
locker doesn’t exist at all. If we do find it, then we do an additional
check to see if the locker is taken. If it is, return a
<code>Left</code> saying that it’s already taken. If it isn’t, then
return a value of type <code>Right Code</code>, in which we give the
student the correct code for the locker. It’s actually a
<code>Right String</code>, but we introduced that type synonym to
introduce some additional documentation into the type declaration.
Here’s an example map:</p>
<pre class="haskell:hs"><code>lockers :: LockerMap
lockers = Map.fromList
[(100,(Taken,"ZD39I"))
,(101,(Free,"JAH3I"))
,(103,(Free,"IQSA9"))
,(105,(Free,"QOTSA"))
,(109,(Taken,"893JJ"))
,(110,(Taken,"99292"))
]</code></pre>
<p>Now let’s try looking up some locker codes.</p>
<pre class="haskell:hs"><code>ghci> lockerLookup 101 lockers
Right "JAH3I"
ghci> lockerLookup 100 lockers
Left "Locker 100 is already taken!"
ghci> lockerLookup 102 lockers
Left "Locker number 102 doesn't exist!"
ghci> lockerLookup 110 lockers
Left "Locker 110 is already taken!"
ghci> lockerLookup 105 lockers
Right "QOTSA"</code></pre>
<p>We could have used a <code>Maybe a</code> to represent the result but
then we wouldn’t know why we couldn’t get the code. But now, we have
information about the failure in our result type.</p>
<h2 id="recursive-data-structures">Recursive data structures</h2>
<p><img
src="assets/images/making-our-own-types-and-typeclasses/thefonz.png"
class="right" width="168" height="301" alt="the fonz" /></p>
<p>As we’ve seen, a constructor in an algebraic data type can have
several (or none at all) fields and each field must be of some concrete
type. With that in mind, we can make types whose constructors have
fields that are of the same type! Using that, we can create recursive
data types, where one value of some type contains values of that type,
which in turn contain more values of the same type and so on.</p>
<p>Think about this list: <code>[5]</code>. That’s just syntactic sugar
for <code>5:[]</code>. On the left side of the <code>:</code>, there’s a
value and on the right side, there’s a list. And in this case, it’s an
empty list. Now how about the list <code>[4,5]</code>? Well, that
desugars to <code>4:(5:[])</code>. Looking at the first <code>:</code>,
we see that it also has an element on its left side and a list
(<code>5:[]</code>) on its right side. Same goes for a list like
<code>3:(4:(5:6:[]))</code>, which could be written either like that or
like <code>3:4:5:6:[]</code> (because <code>:</code> is
right-associative) or <code>[3,4,5,6]</code>.</p>
<p>We could say that a list can be an empty list or it can be an element
joined together with a <code>:</code> with another list (that can be
either the empty list or not).</p>
<p>Let’s use algebraic data types to implement our own list then!</p>
<pre class="haskell:hs"><code>data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)</code></pre>
<p>This reads just like our definition of lists from one of the previous
paragraphs. It’s either an empty list or a combination of a head with
some value and a list. If you’re confused about this, you might find it
easier to understand in record syntax.</p>
<pre class="haskell:hs"><code>data List a = Empty | Cons { listHead :: a, listTail :: List a} deriving (Show, Read, Eq, Ord)</code></pre>
<p>You might also be confused about the <code>Cons</code> constructor
here. <em>cons</em> is another word for <code>:</code>. You see, in
lists, <code>:</code> is actually a constructor that takes a value and
another list and returns a list. We can already use our new list type!
In other words, it has two fields. One field is of the type of
<code>a</code> and the other is of the type <code>[a]</code>.</p>
<pre class="haskell:hs"><code>ghci> Empty
Empty
ghci> 5 `Cons` Empty
Cons 5 Empty
ghci> 4 `Cons` (5 `Cons` Empty)
Cons 4 (Cons 5 Empty)
ghci> 3 `Cons` (4 `Cons` (5 `Cons` Empty))
Cons 3 (Cons 4 (Cons 5 Empty))</code></pre>
<p>We called our <code>Cons</code> constructor in an infix manner so you
can see how it’s just like <code>:</code>. <code>Empty</code> is like
<code>[]</code> and <code>4 `Cons` (5 `Cons` Empty)</code> is like
<code>4:(5:[])</code>.</p>
<p>We can define functions to be automatically infix by making them
comprised of only special characters. We can also do the same with
constructors, since they’re just functions that return a data type. So
check this out.</p>
<pre class="haskell:hs"><code>infixr 5 :-:
data List a = Empty | a :-: (List a) deriving (Show, Read, Eq, Ord)</code></pre>
<p>First off, we notice a new syntactic construct, the fixity
declarations. When we define functions as operators, we can use that to
give them a fixity (but we don’t have to). A fixity states how tightly
the operator binds and whether it’s left-associative or
right-associative. For instance, <code>*</code>’s fixity is
<code>infixl 7 *</code> and <code>+</code>’s fixity is
<code>infixl 6</code>. That means that they’re both left-associative
(<code>4 * 3 * 2</code> is <code>(4 * 3) * 2</code>) but <code>*</code>
binds tighter than <code>+</code>, because it has a greater fixity, so
<code>5 * 4 + 3</code> is <code>(5 * 4) + 3</code>.</p>
<p>Otherwise, we just wrote <code>a :-: (List a)</code> instead of
<code>Cons a (List a)</code>. Now, we can write out lists in our list
type like so:</p>
<pre class="haskell:hs"><code>ghci> 3 :-: 4 :-: 5 :-: Empty
(:-:) 3 ((:-:) 4 ((:-:) 5 Empty))
ghci> let a = 3 :-: 4 :-: 5 :-: Empty
ghci> 100 :-: a
(:-:) 100 ((:-:) 3 ((:-:) 4 ((:-:) 5 Empty)))</code></pre>
<p>When deriving <code>Show</code> for our type, Haskell will still
display it as if the constructor was a prefix function, hence the
parentheses around the operator (remember, <code>4 + 3</code> is
<code>(+) 4 3</code>).</p>
<p>Let’s make a function that adds two of our lists together. This is
how <code>++</code> is defined for normal lists:</p>
<pre class="haskell:hs"><code>infixr 5 ++