-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
363 lines (356 loc) · 52.1 KB
/
index.html
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
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>An Alga tutorial</title>
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head><style>
body {
padding: 3% 5%;
counter-reset: part;
}
img {
display: block;
margin-left: auto;
margin-right: auto;
padding: 2% 0%;
width: 25%;
}
.big {
width: 55%;
}
h1::before {
counter-increment: part;
content: "Part " counter(part) ". ";
}
h1.title::before {
content: none;
counter-increment: none;
}
pre {
padding: 0.5%;
}
.haskell {
background-color: #e6e6e6;
}
.verbated {
background-color: #e6e6e6;
padding: 0.1%;
}
</style>
<body>
<header id="title-block-header">
<h1 class="title">An Alga tutorial</h1>
</header>
<nav>
<ol>
<li><a href="#introduction">Introduction</a></li>
<li><a href="#the-graph-definition">The graph definition</a></li>
<li><a href="#going-deeper-in-the-definition">Going deeper in the definition</a></li>
<li><a href="#the-benefits-of-the-definition">The benefits of the definition</a></li>
<li><a href="#the-problems-of-the-definition">The problems of the definition</a></li>
<li><a href="#useful-instances">Useful instances</a></li>
<li><a href="#an-example-a-social-network">An example a social network</a></li>
</ol></nav>
<h1 id="introduction">Introduction</h1>
<p>Here you will learn the basics of <a href="http://hackage.haskell.org/package/algebraic-graphs">Alga</a>, an implementation of an algebra of graphs. Every given examples is runnable, so please feel free to install alga (with <code class="verbated">cabal</code> or <code class="verbated">stack</code>) and have a GHCi console near you if you want to try the code. All you need to have is inside the <code class="verbated">Algebra.Graph</code> module. Don’t hesitate to have a look at the <a href="http://hackage.haskell.org/package/algebraic-graphs-0.1.1.1/docs/Algebra-Graph.html">module documentation</a> if you want more informations.<br />
<br />
If you encounter any bug (I hope you will not), please open an issue at <a href="https://github.com/snowleopard/alga/issues/">https://github.com/snowleopard/alga/issues/</a>.</p>
<h1 id="the-graph-definition">The graph definition</h1>
<h2 id="the-problem">The problem</h2>
<p>Graphs are traditionally defined as a pair comprising a set <span class="math inline"><em>V</em></span> of vertices and a set <span class="math inline"><em>E</em> ⊆ <em>V</em> × <em>V</em></span> of edges. This is great when working with traditional imperative languages, but leads to some problems when trying to use it in a functional languages such as Haskell.</p>
<p>The idea of alga is to use an other definition of graph, more “functional-friendly“. As the most part of the “functional-friendly” data structures is recursive, such is the alga’s graph definition:</p>
<h2 id="a-solution">A solution</h2>
<div class="sourceCode" id="cb1" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb1-1"><a href="#cb1-1" aria-hidden="true" tabindex="-1"></a><span class="kw">data</span> <span class="dt">Graph</span> a <span class="ot">=</span> <span class="dt">Empty</span></span>
<span id="cb1-2"><a href="#cb1-2" aria-hidden="true" tabindex="-1"></a> <span class="op">|</span> <span class="dt">Vertex</span> a</span>
<span id="cb1-3"><a href="#cb1-3" aria-hidden="true" tabindex="-1"></a> <span class="op">|</span> <span class="dt">Overlay</span> (<span class="dt">Graph</span> a) (<span class="dt">Graph</span> a)</span>
<span id="cb1-4"><a href="#cb1-4" aria-hidden="true" tabindex="-1"></a> <span class="op">|</span> <span class="dt">Connect</span> (<span class="dt">Graph</span> a) (<span class="dt">Graph</span> a)</span></code></pre></div>
<p>So it says:</p>
<ol>
<li><p>You have an only way to construct the empty graph, using the constructor <code class="verbated">Empty</code> which does not take any argument.</p></li>
<li><p>You can construct a graph from anything, transforming it in a single vertex using the constructor <code class="verbated">Vertex</code>.</p></li>
<li><p>You can overlay two graphs, that is just to put them next one to another.</p>
<div class="center">
<p><img src="figspng/overlay.png" class="big" alt="image" /></p>
</div></li>
<li><p>You can connect two graphs, that is drawing an edge from each vertex of the left side to each vertex to the right side.</p>
<div class="center">
<p><img src="figspng/connect.png" class="big" alt="image" /></p>
</div></li>
</ol>
<p>Simple, no? … Well ok this is not a standard way to see a graph, but don’t worry, you will get used to it.</p>
<p>Just remember: <em>The only way to create edges is using</em> <code class="verbated">Connect</code>.</p>
<p>This definition allow us to deal with <em>directed</em> graphs: An edge from vertex 1 to vertex 2 is NOT the same than an edge from vertex 2 to vertex 1.</p>
<h2 id="some-examples">Some examples</h2>
<p>So, how to use this definition? Here is some examples:</p>
<ul>
<li><p>A single path, from a vertex 0 to a vertex 1 can be viewed as <code class="verbated">Connect (Vertex 0) (Vertex 1)</code></p>
<div class="center">
<p><img src="figspng/e2.png" alt="image" /></p>
</div></li>
<li><p>A triangle, with an edge from vertex 0 to vertex 1, an edge from vertex 0 to vertex 2, and an edge from vertex 1 to vertex 2 can be viewed as <code class="verbated">Connect (Vertex 0) (Connect (Vertex 1) (Vertex 2))</code>.</p>
<div class="center">
<p><img src="figspng/e1.png" alt="image" /></p>
</div></li>
</ul>
<p>I heard you from my desktop:</p>
<blockquote>
<p>“Berk, but writing big graphs by hand can become very annoying !“</p>
</blockquote>
<p>Don’t worry, there are some shortcuts.</p>
<h1 id="going-deeper-in-the-definition">Going deeper in the definition</h1>
<h2 id="the-num-instance">The Num instance</h2>
<p><code class="verbated">Overlay</code> and <code class="verbated">Connect</code> look like operators, and we want to use them as. So we pose:</p>
<div class="sourceCode" id="cb2" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb2-1"><a href="#cb2-1" aria-hidden="true" tabindex="-1"></a>(<span class="op">+</span>) <span class="ot">=</span> <span class="dt">Overlay</span></span>
<span id="cb2-2"><a href="#cb2-2" aria-hidden="true" tabindex="-1"></a>(<span class="op">*</span>) <span class="ot">=</span> <span class="dt">Connect</span></span></code></pre></div>
<p>In fact, if we have something of the <code class="verbated">Num</code> instance, we can transform it directly into a graph using <code class="verbated">Vertex</code>. This leads to this instance:</p>
<div class="sourceCode" id="cb3" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb3-1"><a href="#cb3-1" aria-hidden="true" tabindex="-1"></a><span class="kw">instance</span> <span class="dt">Num</span> a <span class="ot">=></span> <span class="dt">Num</span> (<span class="dt">Graph</span> a) <span class="kw">where</span></span>
<span id="cb3-2"><a href="#cb3-2" aria-hidden="true" tabindex="-1"></a> <span class="fu">fromInteger</span> <span class="ot">=</span> <span class="dt">Vertex</span> <span class="op">.</span> <span class="fu">fromInteger</span></span>
<span id="cb3-3"><a href="#cb3-3" aria-hidden="true" tabindex="-1"></a> (<span class="op">+</span>) <span class="ot">=</span> <span class="dt">Overlay</span></span>
<span id="cb3-4"><a href="#cb3-4" aria-hidden="true" tabindex="-1"></a> (<span class="op">*</span>) <span class="ot">=</span> <span class="dt">Connect</span></span>
<span id="cb3-5"><a href="#cb3-5" aria-hidden="true" tabindex="-1"></a> <span class="fu">signum</span> <span class="ot">=</span> <span class="fu">const</span> <span class="dt">Empty</span></span>
<span id="cb3-6"><a href="#cb3-6" aria-hidden="true" tabindex="-1"></a> <span class="fu">abs</span> <span class="ot">=</span> <span class="fu">id</span></span>
<span id="cb3-7"><a href="#cb3-7" aria-hidden="true" tabindex="-1"></a> <span class="fu">negate</span> <span class="ot">=</span> <span class="fu">id</span></span></code></pre></div>
<p>This means that, in a context of a <code class="verbated">Graph</code>, we have <code class="verbated">Vertex 1 == 1</code>, which is quite useful!</p>
<p>Do you see why alga is an implementation of an <em>algebra</em> of graphs? There is a lot of maths here! No please don’t run away like you have seen a zombie in a graveyard! Don’t worry, this is not-so-difficult math.</p>
<h4 id="note">Note</h4>
<p>We will use the <code class="verbated">(+)</code> and <code class="verbated">(*)</code> notation, but these laws are true even when dealing with any graphs.</p>
<h2 id="overlay">Overlay</h2>
<p>As usual, <code class="verbated">(+)</code> is <em>associative</em> (the order in which you are choosing to overlay graphs is not important):</p>
<div class="sourceCode" id="cb4" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb4-1"><a href="#cb4-1" aria-hidden="true" tabindex="-1"></a>(<span class="dv">1</span> <span class="op">+</span> <span class="dv">2</span>) <span class="op">+</span> <span class="dv">3</span> <span class="op">==</span> <span class="dv">1</span> <span class="op">+</span> (<span class="dv">2</span> <span class="op">+</span> <span class="dv">3</span>)</span></code></pre></div>
<p><code class="verbated">(+)</code> is also <em>commutative</em> (overlaying <span class="math inline"><em>a</em></span> and <span class="math inline"><em>b</em></span> is the same as overlaying <span class="math inline"><em>b</em></span> and <span class="math inline"><em>a</em></span>):</p>
<div class="sourceCode" id="cb5" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb5-1"><a href="#cb5-1" aria-hidden="true" tabindex="-1"></a><span class="dv">1</span> <span class="op">+</span> <span class="dv">2</span> <span class="op">==</span> <span class="dv">2</span> <span class="op">+</span> <span class="dv">1</span></span></code></pre></div>
<p><code class="verbated">(+)</code> has <code class="verbated">Empty</code> as a neutral element (overlaying an <code class="verbated">Empty</code> graph to another graph is this graph):</p>
<div class="sourceCode" id="cb6" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb6-1"><a href="#cb6-1" aria-hidden="true" tabindex="-1"></a><span class="dv">1</span> <span class="op">+</span> <span class="dt">Empty</span> <span class="op">==</span> <span class="dv">1</span> <span class="op">==</span> <span class="dt">Empty</span> <span class="op">+</span> <span class="dv">1</span></span></code></pre></div>
<p><code class="verbated">(+)</code> is <em>idempotent</em> (overlaying a graph with itself is the same graph):</p>
<div class="sourceCode" id="cb7" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb7-1"><a href="#cb7-1" aria-hidden="true" tabindex="-1"></a><span class="dv">1</span> <span class="op">+</span> <span class="dv">1</span> <span class="op">==</span> <span class="dv">1</span></span></code></pre></div>
<h2 id="connect">Connect</h2>
<p>As usual, <code class="verbated">(*)</code> is <em>associative</em> (the order in which you are choosing to connect graphs is not important):</p>
<div class="sourceCode" id="cb8" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb8-1"><a href="#cb8-1" aria-hidden="true" tabindex="-1"></a>(<span class="dv">1</span> <span class="op">*</span> <span class="dv">2</span>) <span class="op">*</span> <span class="dv">3</span> <span class="op">==</span> <span class="dv">1</span> <span class="op">*</span> (<span class="dv">2</span> <span class="op">*</span> <span class="dv">3</span>)</span></code></pre></div>
<p><code class="verbated">(*)</code> is NOT <em>commutative</em> (drawing an edge from vertex 1 to vertex 2 is not the same as drawing an edge from vertex 2 to vertex 1):</p>
<div class="sourceCode" id="cb9" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb9-1"><a href="#cb9-1" aria-hidden="true" tabindex="-1"></a><span class="dv">1</span> <span class="op">*</span> <span class="dv">2</span> <span class="op">/=</span> <span class="dv">2</span> <span class="op">*</span> <span class="dv">1</span></span></code></pre></div>
<p><code class="verbated">(*)</code> it has <code class="verbated">Empty</code> as a neutral element (connecting an <code class="verbated">Empty</code> graph to another graph is this graph):</p>
<div class="sourceCode" id="cb10" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb10-1"><a href="#cb10-1" aria-hidden="true" tabindex="-1"></a><span class="dv">1</span> <span class="op">*</span> <span class="dt">Empty</span> <span class="op">==</span> <span class="dv">1</span> <span class="op">==</span> <span class="dt">Empty</span> <span class="op">*</span> <span class="dv">1</span></span></code></pre></div>
<p><code class="verbated">(*)</code> can saturate (connecting three times the same graph is the same as connecting two times the same graph)</p>
<div class="sourceCode" id="cb11" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb11-1"><a href="#cb11-1" aria-hidden="true" tabindex="-1"></a><span class="dv">1</span> <span class="op">*</span> <span class="dv">1</span> <span class="op">*</span> <span class="dv">1</span> <span class="op">==</span> <span class="dv">1</span> <span class="op">*</span> <span class="dv">1</span></span></code></pre></div>
<p>Why <code class="verbated">(*)</code> is not <em>idempotent</em>? Because connecting a vertex with himself allow to create a <em>loop</em>:</p>
<div class="center">
<p><img src="figspng/saturate.png" class="big" alt="image" /></p>
</div>
<h2 id="the-two-together">The two together</h2>
<p>Do you remind when you have discovered that you can mix <span class="math inline">+</span> and <span class="math inline">*</span> in the same equation? This is the same thing here!</p>
<div class="sourceCode" id="cb12" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb12-1"><a href="#cb12-1" aria-hidden="true" tabindex="-1"></a><span class="dv">1</span> <span class="op">*</span> (<span class="dv">2</span> <span class="op">+</span> <span class="dv">3</span>) <span class="op">==</span> <span class="dv">1</span> <span class="op">*</span> <span class="dv">2</span> <span class="op">+</span> <span class="dv">1</span> <span class="op">*</span> <span class="dv">3</span></span></code></pre></div>
<p>Connecting the single vertex 1 to both 2 and 3 can be done of two <em>equivalent</em> ways:</p>
<ul>
<li><p>either you are connecting 1 to 2 and 3 “overlayed“.</p></li>
<li><p>or you are overlaying the two edges <code class="verbated">(1,2)</code> and <code class="verbated">(1,3)</code>.</p></li>
</ul>
<p>Whew, this is done we can make a step forward.</p>
<h2 id="making-graphs">Making graphs</h2>
<p>I haven’t answered on question yet:</p>
<blockquote>
<p>Is the definition usable? Can we represent every graph in alga’s representation ?</p>
</blockquote>
<p>Let’s try to answer this <em>important</em> question. As said, graphs are (almost all the time) defined as a pair <span class="math inline"><em>V</em></span> of vertices and <span class="math inline"><em>E</em> ⊆ <em>V</em> × <em>V</em></span> a set of edges. So to prove that we can represents any graph, we need to define a function <code class="verbated">create :: [a] -> [(a,a)] -> Graph a</code> that create a graph from this standard representation.</p>
<p>Let us forget about the edges: we are first going to make <code class="verbated">vertices :: [a] -> Graph a</code> that transform a list of vertices into a <code class="verbated">Graph</code> containing all the single vertices. It looks like we are going to <code class="verbated">fold</code> a list</p>
<div class="sourceCode" id="cb13" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb13-1"><a href="#cb13-1" aria-hidden="true" tabindex="-1"></a><span class="ot">vertices ::</span> [a] <span class="ot">-></span> <span class="dt">Graph</span> a</span>
<span id="cb13-2"><a href="#cb13-2" aria-hidden="true" tabindex="-1"></a>vertices <span class="ot">=</span> <span class="fu">foldr</span> (\v g <span class="ot">-></span> <span class="dt">Overlay</span> (<span class="dt">Vertex</span> v) g) <span class="dt">Empty</span></span></code></pre></div>
<p>Any idea how to do <code class="verbated">edges :: [(a,a)] -> Graph a</code>? The same way, obviously:</p>
<div class="sourceCode" id="cb14" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb14-1"><a href="#cb14-1" aria-hidden="true" tabindex="-1"></a><span class="ot">edges ::</span> [(a,a)] <span class="ot">-></span> <span class="dt">Graph</span> a</span>
<span id="cb14-2"><a href="#cb14-2" aria-hidden="true" tabindex="-1"></a>edges <span class="ot">=</span> <span class="fu">foldr</span></span>
<span id="cb14-3"><a href="#cb14-3" aria-hidden="true" tabindex="-1"></a> (\(x,y) g <span class="ot">-></span> <span class="dt">Overlay</span> (<span class="dt">Connect</span> (<span class="dt">Vertex</span> x) (<span class="dt">Vertex</span> y)) g)</span>
<span id="cb14-4"><a href="#cb14-4" aria-hidden="true" tabindex="-1"></a> <span class="dt">Empty</span></span></code></pre></div>
<p>And so, what can be our <code class="verbated">create :: [a] -> [(a,a)] -> Graph a</code>? Simply:</p>
<div class="sourceCode" id="cb15" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb15-1"><a href="#cb15-1" aria-hidden="true" tabindex="-1"></a><span class="ot">create ::</span> [a] <span class="ot">-></span> [(a,a)] <span class="ot">-></span> <span class="dt">Graph</span> a</span>
<span id="cb15-2"><a href="#cb15-2" aria-hidden="true" tabindex="-1"></a>create v e <span class="ot">=</span> <span class="dt">Overlay</span> (vertices v) (edges e)</span></code></pre></div>
<p>So we have defined the desired function, thus we can safely use the alga’s definition!</p>
<h1 id="the-benefits-of-the-definition">The benefits of the definition</h1>
<h2 id="foldg">foldg</h2>
<p>One of the very advantage given by this representation is the ability to define the <code class="verbated">foldg</code> function, a kind of adapted <code class="verbated">fold</code> for graph:</p>
<div class="sourceCode" id="cb16" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb16-1"><a href="#cb16-1" aria-hidden="true" tabindex="-1"></a><span class="ot">foldg ::</span> b <span class="ot">-></span> (a <span class="ot">-></span> b) <span class="ot">-></span> (b <span class="ot">-></span> b <span class="ot">-></span> b)</span>
<span id="cb16-2"><a href="#cb16-2" aria-hidden="true" tabindex="-1"></a> <span class="ot">-></span> (b <span class="ot">-></span> b <span class="ot">-></span> b) <span class="ot">-></span> <span class="dt">Graph</span> a <span class="ot">-></span> b</span>
<span id="cb16-3"><a href="#cb16-3" aria-hidden="true" tabindex="-1"></a>foldg e v o c <span class="ot">=</span> go</span>
<span id="cb16-4"><a href="#cb16-4" aria-hidden="true" tabindex="-1"></a> <span class="kw">where</span></span>
<span id="cb16-5"><a href="#cb16-5" aria-hidden="true" tabindex="-1"></a> go <span class="dt">Empty</span> <span class="ot">=</span> e</span>
<span id="cb16-6"><a href="#cb16-6" aria-hidden="true" tabindex="-1"></a> go (<span class="dt">Vertex</span> x ) <span class="ot">=</span> v x</span>
<span id="cb16-7"><a href="#cb16-7" aria-hidden="true" tabindex="-1"></a> go (<span class="dt">Overlay</span> x y) <span class="ot">=</span> o (go x) (go y)</span>
<span id="cb16-8"><a href="#cb16-8" aria-hidden="true" tabindex="-1"></a> go (<span class="dt">Connect</span> x y) <span class="ot">=</span> c (go x) (go y)</span></code></pre></div>
<p>In other words, the <code class="verbated">foldg</code> function take a base case for <code class="verbated">Empty</code> graphs, something to transform a <code class="verbated">Vertex</code> and combining functions when we encounter <code class="verbated">Overlay</code> or <code class="verbated">Connect</code>.</p>
<h2 id="transpose">transpose</h2>
<p>We have a wonderful graph and we want to <code class="verbated">transpose</code> it. Transposing an directed graph consist in inverting the orientation of all edges. Using <code class="verbated">foldg</code>, this is a piece of cake:</p>
<div class="sourceCode" id="cb17" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb17-1"><a href="#cb17-1" aria-hidden="true" tabindex="-1"></a><span class="ot">transpose ::</span> <span class="dt">Graph</span> a <span class="ot">-></span> <span class="dt">Graph</span> a</span>
<span id="cb17-2"><a href="#cb17-2" aria-hidden="true" tabindex="-1"></a>transpose <span class="ot">=</span> foldg <span class="dt">Empty</span> <span class="dt">Vertex</span> <span class="dt">Overlay</span> (<span class="fu">flip</span> <span class="dt">Connect</span>)</span></code></pre></div>
<h2 id="induce">induce</h2>
<p>Still not convinced? Let’s try to build an induced sub-graph. An induced sub-graph is a sub-graph that “forget“ about some vertices and all edges to and from these vertices.</p>
<p>So we are going to code the <code class="verbated">induce :: (a -> bool) -> Graph a -> Graph a</code> function. We will use <code class="verbated">foldg</code> of course.</p>
<p>What is the base case? Do we need to change an <code class="verbated">Empty</code> graph? Obviously, not at all:</p>
<div class="sourceCode" id="cb18" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb18-1"><a href="#cb18-1" aria-hidden="true" tabindex="-1"></a><span class="ot">induce ::</span> (a <span class="ot">-></span> <span class="dt">Bool</span>) <span class="ot">-></span> <span class="dt">Graph</span> a <span class="ot">-></span> <span class="dt">Graph</span> a</span>
<span id="cb18-2"><a href="#cb18-2" aria-hidden="true" tabindex="-1"></a>induce predicate <span class="ot">=</span> foldg</span>
<span id="cb18-3"><a href="#cb18-3" aria-hidden="true" tabindex="-1"></a> <span class="dt">Empty</span></span>
<span id="cb18-4"><a href="#cb18-4" aria-hidden="true" tabindex="-1"></a> <span class="fu">undefined</span></span>
<span id="cb18-5"><a href="#cb18-5" aria-hidden="true" tabindex="-1"></a> <span class="fu">undefined</span></span>
<span id="cb18-6"><a href="#cb18-6" aria-hidden="true" tabindex="-1"></a> <span class="fu">undefined</span></span></code></pre></div>
<p>Then if we encounter a vertex, we need to verify if it satisfy the predicate. If it does not, we will simply replace it…Let’s say by the <code class="verbated">Empty</code> graph!</p>
<div class="sourceCode" id="cb19" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb19-1"><a href="#cb19-1" aria-hidden="true" tabindex="-1"></a><span class="ot">induce ::</span> (a <span class="ot">-></span> <span class="dt">Bool</span>) <span class="ot">-></span> <span class="dt">Graph</span> a <span class="ot">-></span> <span class="dt">Graph</span> a</span>
<span id="cb19-2"><a href="#cb19-2" aria-hidden="true" tabindex="-1"></a>induce predicate <span class="ot">=</span> foldg</span>
<span id="cb19-3"><a href="#cb19-3" aria-hidden="true" tabindex="-1"></a> <span class="dt">Empty</span></span>
<span id="cb19-4"><a href="#cb19-4" aria-hidden="true" tabindex="-1"></a> (\x <span class="ot">-></span> <span class="kw">if</span> predicate x <span class="kw">then</span> <span class="dt">Vertex</span> x <span class="kw">else</span> <span class="dt">Empty</span>)</span>
<span id="cb19-5"><a href="#cb19-5" aria-hidden="true" tabindex="-1"></a> <span class="fu">undefined</span></span>
<span id="cb19-6"><a href="#cb19-6" aria-hidden="true" tabindex="-1"></a> <span class="fu">undefined</span></span></code></pre></div>
<p>And finally do we need to touch connection between base graphs? Not at all! Remember, <code class="verbated">Empty</code> is the neutral element of <em>both</em> <code class="verbated">Connect</code> and <code class="verbated">Overlay</code>. So we can leave our empty graphs inside the structure without problem (don’t worry, the real implementation get rid of these empty leaves). So we come to:</p>
<div class="sourceCode" id="cb20" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb20-1"><a href="#cb20-1" aria-hidden="true" tabindex="-1"></a><span class="ot">induce ::</span> (a <span class="ot">-></span> <span class="dt">Bool</span>) <span class="ot">-></span> <span class="dt">Graph</span> a <span class="ot">-></span> <span class="dt">Graph</span> a</span>
<span id="cb20-2"><a href="#cb20-2" aria-hidden="true" tabindex="-1"></a>induce predicate <span class="ot">=</span> foldg</span>
<span id="cb20-3"><a href="#cb20-3" aria-hidden="true" tabindex="-1"></a> <span class="dt">Empty</span></span>
<span id="cb20-4"><a href="#cb20-4" aria-hidden="true" tabindex="-1"></a> (\x <span class="ot">-></span> <span class="kw">if</span> predicate x <span class="kw">then</span> <span class="dt">Vertex</span> x <span class="kw">else</span> <span class="dt">Empty</span>)</span>
<span id="cb20-5"><a href="#cb20-5" aria-hidden="true" tabindex="-1"></a> <span class="dt">Overlay</span></span>
<span id="cb20-6"><a href="#cb20-6" aria-hidden="true" tabindex="-1"></a> <span class="dt">Connect</span></span></code></pre></div>
<p>So simple, isn’t it?</p>
<p>This even allow us to define:</p>
<div class="sourceCode" id="cb21" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb21-1"><a href="#cb21-1" aria-hidden="true" tabindex="-1"></a><span class="ot">removeVertex ::</span> a <span class="ot">-></span> <span class="dt">Graph</span> a <span class="ot">-></span> <span class="dt">Graph</span> a</span>
<span id="cb21-2"><a href="#cb21-2" aria-hidden="true" tabindex="-1"></a>removeVertex x <span class="ot">=</span> induce (<span class="op">/=</span>x)</span></code></pre></div>
<h2 id="hasedge">hasEdge</h2>
<p><code class="verbated">foldg</code> and <code class="verbated">induce</code> are so cool that a good part of the Alga API is made from them. For example, let’s take a look at the <code class="verbated">hasEdge</code> definition:</p>
<div class="sourceCode" id="cb22" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb22-1"><a href="#cb22-1" aria-hidden="true" tabindex="-1"></a><span class="ot">hasEdge ::</span> <span class="dt">Ord</span> a <span class="ot">=></span> a <span class="ot">-></span> a <span class="ot">-></span> <span class="dt">Graph</span> a <span class="ot">-></span> <span class="dt">Graph</span> a</span>
<span id="cb22-2"><a href="#cb22-2" aria-hidden="true" tabindex="-1"></a>hasEdge u v <span class="ot">=</span></span>
<span id="cb22-3"><a href="#cb22-3" aria-hidden="true" tabindex="-1"></a> (<span class="dt">Connect</span> (<span class="dt">Vertex</span> u) (<span class="dt">Vertex</span> v) <span class="ot">`isSubgraphOf`</span>) <span class="op">.</span></span>
<span id="cb22-4"><a href="#cb22-4" aria-hidden="true" tabindex="-1"></a> induce (<span class="ot">`elem`</span> [u, v])</span></code></pre></div>
<p>To check if a graph contains an edge from <span class="math inline"><em>x</em></span> to <span class="math inline"><em>y</em></span>, you can remove every vertices different of <span class="math inline"><em>x</em></span> and <span class="math inline"><em>y</em></span>, and then check if the edge <em>alone</em> is a sub-graph of the induced sub-graph. Note that <code class="verbated">hasEdge</code> is requiring an <code class="verbated">Ord</code> instance because <code class="verbated">isSubgraphOf</code> is requiring it.</p>
<h1 id="the-problems-of-the-definition">The problems of the definition</h1>
<h2 id="equality">Equality</h2>
<p>There is no canonical way to define a graph in alga. For example:</p>
<div class="sourceCode" id="cb23" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb23-1"><a href="#cb23-1" aria-hidden="true" tabindex="-1"></a><span class="dt">Overlay</span> (<span class="dt">Vertex</span> <span class="dv">1</span>) (<span class="dt">Vertex</span> <span class="dv">2</span>)</span>
<span id="cb23-2"><a href="#cb23-2" aria-hidden="true" tabindex="-1"></a><span class="op">==</span> <span class="dt">Overlay</span> (<span class="dt">Vertex</span> <span class="dv">2</span>) (<span class="dt">Vertex</span> <span class="dv">1</span>)</span>
<span id="cb23-3"><a href="#cb23-3" aria-hidden="true" tabindex="-1"></a><span class="op">==</span> <span class="dt">Connect</span> <span class="dt">Empty</span> (<span class="dt">Overlay</span> (<span class="dt">Vertex</span> <span class="dv">1</span>) (<span class="dt">Vertex</span> <span class="dv">2</span>))</span>
<span id="cb23-4"><a href="#cb23-4" aria-hidden="true" tabindex="-1"></a><span class="op">==</span> <span class="dt">Overlay</span></span>
<span id="cb23-5"><a href="#cb23-5" aria-hidden="true" tabindex="-1"></a> (<span class="dt">Connect</span> (<span class="dt">Vertex</span> <span class="dv">1</span>) <span class="dt">Empty</span>)</span>
<span id="cb23-6"><a href="#cb23-6" aria-hidden="true" tabindex="-1"></a> (<span class="dt">Connect</span> <span class="dt">Empty</span> (<span class="dt">Vertex</span> <span class="dv">2</span>))</span></code></pre></div>
<p>Fortunately, you don’t have to bother with the internal definition since the <code class="verbated">Eq</code> instance (which provide <code class="verbated">(==)</code>) take care of this problem for you.</p>
<p>Alga is also providing <code class="verbated">(===)</code> which denote <em>structural</em> equality, and thus:</p>
<div class="sourceCode" id="cb24" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb24-1"><a href="#cb24-1" aria-hidden="true" tabindex="-1"></a><span class="dt">Overlay</span> (<span class="dt">Vertex</span> <span class="dv">1</span>) (<span class="dt">Vertex</span> <span class="dv">2</span>)</span>
<span id="cb24-2"><a href="#cb24-2" aria-hidden="true" tabindex="-1"></a><span class="op">===</span></span>
<span id="cb24-3"><a href="#cb24-3" aria-hidden="true" tabindex="-1"></a><span class="dt">Overlay</span> (<span class="dt">Vertex</span> <span class="dv">2</span>) (<span class="dt">Vertex</span> <span class="dv">1</span>)</span>
<span id="cb24-4"><a href="#cb24-4" aria-hidden="true" tabindex="-1"></a><span class="op">==</span> <span class="dt">False</span></span></code></pre></div>
<h2 id="take-care-when-defining-functions">Take care when defining functions</h2>
<p>Here is a nasty function that you can define:</p>
<div class="sourceCode" id="cb25" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb25-1"><a href="#cb25-1" aria-hidden="true" tabindex="-1"></a>close <span class="op">:</span> <span class="dt">Graph</span> <span class="dt">A</span> <span class="ot">-></span> <span class="dt">Graph</span> <span class="dt">A</span></span>
<span id="cb25-2"><a href="#cb25-2" aria-hidden="true" tabindex="-1"></a>close <span class="dt">Empty</span> <span class="ot">=</span> <span class="dt">Empty</span></span>
<span id="cb25-3"><a href="#cb25-3" aria-hidden="true" tabindex="-1"></a>close (<span class="dt">Vertex</span> x) <span class="ot">=</span> <span class="dt">Vertex</span> x</span>
<span id="cb25-4"><a href="#cb25-4" aria-hidden="true" tabindex="-1"></a>close (<span class="dt">Overlay</span> x y) <span class="ot">=</span> <span class="dt">Connect</span> x y</span>
<span id="cb25-5"><a href="#cb25-5" aria-hidden="true" tabindex="-1"></a>close (<span class="dt">Connect</span> x y) <span class="ot">=</span> <span class="dt">Connect</span> x y</span></code></pre></div>
<p>Do you see the problem?</p>
<div class="sourceCode" id="cb26" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb26-1"><a href="#cb26-1" aria-hidden="true" tabindex="-1"></a><span class="op">>>></span> <span class="kw">let</span> x <span class="ot">=</span> <span class="dt">Vertex</span> <span class="dv">0</span></span>
<span id="cb26-2"><a href="#cb26-2" aria-hidden="true" tabindex="-1"></a><span class="op">>>></span> <span class="kw">let</span> y <span class="ot">=</span> <span class="dt">Overlay</span> (<span class="dt">Vertex</span> <span class="dv">0</span>) (<span class="dt">Vertex</span> <span class="dv">0</span>)</span>
<span id="cb26-3"><a href="#cb26-3" aria-hidden="true" tabindex="-1"></a><span class="op">>>></span> x <span class="op">==</span> y</span>
<span id="cb26-4"><a href="#cb26-4" aria-hidden="true" tabindex="-1"></a><span class="dt">True</span></span>
<span id="cb26-5"><a href="#cb26-5" aria-hidden="true" tabindex="-1"></a><span class="op">>>></span> <span class="fu">print</span> (close x)</span>
<span id="cb26-6"><a href="#cb26-6" aria-hidden="true" tabindex="-1"></a><span class="dt">Vertex</span> <span class="dv">0</span></span>
<span id="cb26-7"><a href="#cb26-7" aria-hidden="true" tabindex="-1"></a><span class="op">>>></span> <span class="fu">print</span> (close y)</span>
<span id="cb26-8"><a href="#cb26-8" aria-hidden="true" tabindex="-1"></a>(<span class="dt">Vertex</span> <span class="dv">0</span>) <span class="op">*</span> (<span class="dt">Vertex</span> <span class="dv">0</span>)</span>
<span id="cb26-9"><a href="#cb26-9" aria-hidden="true" tabindex="-1"></a><span class="op">>>></span> close x <span class="op">==</span> close y</span>
<span id="cb26-10"><a href="#cb26-10" aria-hidden="true" tabindex="-1"></a><span class="dt">False</span></span></code></pre></div>
<p>For the moment, one can mess the internal structure, and the equality loose its meaning (ie <span class="math inline">∀(<em>f</em>:<em>G</em><em>r</em><em>a</em><em>p</em><em>h</em> <em>A</em>→<em>G</em><em>r</em><em>a</em><em>p</em><em>h</em> <em>B</em>) : <em>g</em> = <em>y</em> ⟹ <em>f</em> <em>g</em> = <em>f</em> <em>y</em></span> does NOT hold ).</p>
<h1 id="useful-instances">Useful instances</h1>
<p>Alga’s graphs are instance of some classical Haskell classes:</p>
<h2 id="eq-show">Eq, Show</h2>
<p>Of course, you have Graph equality, and you can show a Graph. Alga can also export to the <em>DOT file format</em> through the <code class="verbated">Algebra.Graph.Export.Dot</code> module.</p>
<h2 id="ord">Ord</h2>
<p>Less trivially, there is a total order defined on graphs and implemented in alga. It use the size-lexicographic/ comparison:</p>
<ul>
<li><p>Compare the number of vertices. In case of a tie, continue.</p></li>
<li><p>Compare the sets of vertices. In case of a tie, continue.</p></li>
<li><p>Compare the number of edges. In case of a tie, continue.</p></li>
<li><p>Compare the sets of edges.</p></li>
</ul>
<p>So first, it is indeed and order (this relation is transitive, reflexive and anti-symmetric) and it is <em>total</em> (you can compare any graphs). The second is that this order is, in some way, compatible with graphs operations:</p>
<ul>
<li><p><span class="math inline">∀<em>g</em></span>: <code class="verbated">(empty <= x) == True</code></p></li>
<li><p>If <span class="math inline"><em>x</em></span> is a sub-graph of <span class="math inline"><em>y</em></span>, then <code class="verbated">(x <= y) == True</code></p></li>
<li><p><span class="math inline">∀<em>x</em>, <em>y</em></span>: <code class="verbated">(x <= x+y) == True</code></p></li>
<li><p><span class="math inline">∀<em>x</em>, <em>y</em></span>: <code class="verbated">(x+y <= x*y) == True</code></p></li>
</ul>
<h2 id="functor">Functor</h2>
<p>Not so surprisingly, <code class="verbated">Graph</code> is an instance of <code class="verbated">Functor</code>:</p>
<div class="sourceCode" id="cb27" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb27-1"><a href="#cb27-1" aria-hidden="true" tabindex="-1"></a><span class="kw">instance</span> <span class="dt">Functor</span> (<span class="dt">Graph</span> a) <span class="kw">where</span></span>
<span id="cb27-2"><a href="#cb27-2" aria-hidden="true" tabindex="-1"></a> <span class="fu">fmap</span> _ <span class="dt">Empty</span> <span class="ot">=</span> <span class="dt">Empty</span></span>
<span id="cb27-3"><a href="#cb27-3" aria-hidden="true" tabindex="-1"></a> <span class="fu">fmap</span> f (<span class="dt">Vertex</span> a) <span class="ot">=</span> <span class="dt">Vertex</span> <span class="op">$</span> f a</span>
<span id="cb27-4"><a href="#cb27-4" aria-hidden="true" tabindex="-1"></a> <span class="fu">fmap</span> f (<span class="dt">Overlay</span> a b) <span class="ot">=</span> <span class="dt">Overlay</span> (<span class="fu">fmap</span> f a) (<span class="fu">fmap</span> f b)</span>
<span id="cb27-5"><a href="#cb27-5" aria-hidden="true" tabindex="-1"></a> <span class="fu">fmap</span> f (<span class="dt">Connect</span> a b) <span class="ot">=</span> <span class="dt">Connect</span> (<span class="fu">fmap</span> f a) (<span class="fu">fmap</span> f b)</span></code></pre></div>
<p>This means that if you have something to transform a <code class="verbated">a</code> in a <code class="verbated">b</code> then you can transform a <code class="verbated">Graph a</code> into a <code class="verbated">Graph b</code>. For example:</p>
<div class="center">
<p><img src="figspng/fmap.png" class="big" alt="image" /></p>
</div>
<p>If you want to test it, the first graph in alga’s representation is: <code class="verbated">1 * (2 + 5) * 0</code><br />
<br />
Alert! Alert! Haskeller’s alarms are ringing! If there is a <code class="verbated">Functor</code> instance, is there a <code class="verbated">Monad</code> one?</p>
<h2 id="monad">Monad</h2>
<p><code class="verbated">Graph</code> are indeed a <code class="verbated">Monad</code> instance:</p>
<div class="sourceCode" id="cb28" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb28-1"><a href="#cb28-1" aria-hidden="true" tabindex="-1"></a><span class="kw">instance</span> <span class="dt">Monad</span> (<span class="dt">Graph</span> a) <span class="kw">where</span></span>
<span id="cb28-2"><a href="#cb28-2" aria-hidden="true" tabindex="-1"></a> <span class="fu">return</span> <span class="ot">=</span> <span class="dt">Vertex</span></span>
<span id="cb28-3"><a href="#cb28-3" aria-hidden="true" tabindex="-1"></a> g <span class="op">>>=</span> f <span class="ot">=</span> foldg <span class="dt">Empty</span> f <span class="dt">Connect</span> <span class="dt">Overlay</span> g</span></code></pre></div>
<p>You can convert anything into a graph, simply by transforming it in a single vertex. Moreover, if you can produce a graph from a type <code class="verbated">a</code> then you can replace every vertex of a <code class="verbated">Graph a</code> with the result, transforming it into a <code class="verbated">Graph b</code>.</p>
<p>For example, one can redefine the previously-viewed <code class="verbated">induce</code> as:</p>
<div class="sourceCode" id="cb29" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb29-1"><a href="#cb29-1" aria-hidden="true" tabindex="-1"></a><span class="ot">induce ::</span> (a <span class="ot">-></span> <span class="dt">Bool</span>) <span class="ot">-></span> <span class="dt">Graph</span> a <span class="ot">-></span> <span class="dt">Graph</span> a</span>
<span id="cb29-2"><a href="#cb29-2" aria-hidden="true" tabindex="-1"></a>induce predicate g</span>
<span id="cb29-3"><a href="#cb29-3" aria-hidden="true" tabindex="-1"></a> <span class="ot">=</span> g <span class="op">>>=</span> (\x <span class="ot">-></span> <span class="kw">if</span> predicate x <span class="kw">then</span> <span class="dt">Vertex</span> x <span class="kw">else</span> <span class="dt">Empty</span>)</span></code></pre></div>
<h2 id="foldable-and-traversable">Foldable and Traversable</h2>
<p><code class="verbated">Graph</code> can be a valid <code class="verbated">Foldable</code> and a valid <code class="verbated">Traversable</code> instance, but these are <em>not</em> defined in the <code class="verbated">Algebra.Graph</code> module.<br />
The reason is that these instances are not compatible with the rest of the library. For example, <code class="verbated">vertexList g /= toList g</code> because a vertex can be multiple times in the structure.</p>
<h1 id="an-example-a-social-network">An example: A social network</h1>
<h2 id="the-goal">The goal</h2>
<p>Ok, now we are wanting to build something real with all of this. Let’s say a social network: one can represent them easily through graphs. The marketing team analysed the market, and decided to make something “à la Twitter“. The vertices will be users, and an edge from <span class="math inline"><em>x</em></span> to <span class="math inline"><em>y</em></span> will denote that <span class="math inline"><em>x</em></span> is following <span class="math inline"><em>y</em></span>.</p>
<h2 id="handlerequest">handleRequest</h2>
<p>The staff meeting has chosen you to build the <code class="verbated">handleRequest</code> function:</p>
<div class="sourceCode" id="cb30" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb30-1"><a href="#cb30-1" aria-hidden="true" tabindex="-1"></a><span class="kw">type</span> <span class="dt">User</span> <span class="ot">=</span> <span class="dt">Int</span></span>
<span id="cb30-2"><a href="#cb30-2" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb30-3"><a href="#cb30-3" aria-hidden="true" tabindex="-1"></a><span class="kw">data</span> <span class="dt">RequestM</span> <span class="ot">=</span> <span class="dt">AddUser</span> <span class="dt">User</span></span>
<span id="cb30-4"><a href="#cb30-4" aria-hidden="true" tabindex="-1"></a> <span class="op">|</span> <span class="dt">RemoveUser</span> <span class="dt">User</span></span>
<span id="cb30-5"><a href="#cb30-5" aria-hidden="true" tabindex="-1"></a> <span class="op">|</span> <span class="dt">ConnectU</span> <span class="dt">User</span> <span class="dt">User</span></span>
<span id="cb30-6"><a href="#cb30-6" aria-hidden="true" tabindex="-1"></a> <span class="op">|</span> <span class="dt">DisconnectU</span> <span class="dt">User</span> <span class="dt">User</span></span>
<span id="cb30-7"><a href="#cb30-7" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb30-8"><a href="#cb30-8" aria-hidden="true" tabindex="-1"></a><span class="ot">handleRequestM ::</span> <span class="dt">RequestM</span> <span class="ot">-></span> <span class="dt">Graph</span> <span class="dt">User</span> <span class="ot">-></span> <span class="dt">Graph</span> <span class="dt">User</span></span></code></pre></div>
<p>This is now a pretty simple job and the implementation is straightforward:</p>
<div class="sourceCode" id="cb31" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb31-1"><a href="#cb31-1" aria-hidden="true" tabindex="-1"></a><span class="ot">handleRequestM ::</span> <span class="dt">RequestM</span> <span class="ot">-></span> <span class="dt">Graph</span> <span class="dt">User</span> <span class="ot">-></span> <span class="dt">Graph</span> <span class="dt">User</span></span>
<span id="cb31-2"><a href="#cb31-2" aria-hidden="true" tabindex="-1"></a>handleRequestM (<span class="dt">AddUser</span> a) <span class="ot">=</span> <span class="dt">Overlay</span> (<span class="dt">Vertex</span> a)</span>
<span id="cb31-3"><a href="#cb31-3" aria-hidden="true" tabindex="-1"></a>handleRequestM (<span class="dt">RemoveUser</span> a) <span class="ot">=</span> removeVertex a</span>
<span id="cb31-4"><a href="#cb31-4" aria-hidden="true" tabindex="-1"></a>handleRequestM (<span class="dt">ConnectU</span> a b) <span class="ot">=</span></span>
<span id="cb31-5"><a href="#cb31-5" aria-hidden="true" tabindex="-1"></a> <span class="dt">Overlay</span> (<span class="dt">Connect</span> (<span class="dt">Vertex</span> a) (<span class="dt">Vertex</span> b))</span>
<span id="cb31-6"><a href="#cb31-6" aria-hidden="true" tabindex="-1"></a>handleRequestM (<span class="dt">DisconnectU</span> a b) <span class="ot">=</span> removeEdge a b</span></code></pre></div>
<h2 id="inspection">Inspection</h2>
<p>Viewing that you implemented your function very quickly, you are being asked to help one of your co-workers on his function. He was working about the <code class="verbated">getFollowing :: User -> Graph User -> [User]</code> function.</p>
<p>One possible way is to use the <code class="verbated">edgeList :: Ord a => Graph a -> [(a,a)]</code> function.</p>
<div class="sourceCode" id="cb32" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb32-1"><a href="#cb32-1" aria-hidden="true" tabindex="-1"></a><span class="ot">getFollowing ::</span> <span class="dt">User</span> <span class="ot">-></span> <span class="dt">Graph</span> <span class="dt">User</span> <span class="ot">-></span> [<span class="dt">User</span>]</span>
<span id="cb32-2"><a href="#cb32-2" aria-hidden="true" tabindex="-1"></a>getFollowing u <span class="ot">=</span></span>
<span id="cb32-3"><a href="#cb32-3" aria-hidden="true" tabindex="-1"></a> <span class="fu">map</span> <span class="fu">snd</span> <span class="op">.</span> <span class="fu">filter</span> (\(v,_) <span class="ot">-></span> u <span class="op">==</span> v ) <span class="op">.</span> edgeList</span></code></pre></div>
<p>you can even implement blindly the <code class="verbated">getFollowers</code> function:</p>
<div class="sourceCode" id="cb33" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb33-1"><a href="#cb33-1" aria-hidden="true" tabindex="-1"></a><span class="ot">getFollowers ::</span> <span class="dt">User</span> <span class="ot">-></span> <span class="dt">Graph</span> <span class="dt">User</span> <span class="ot">-></span> [<span class="dt">User</span>]</span>
<span id="cb33-2"><a href="#cb33-2" aria-hidden="true" tabindex="-1"></a>getFollowers u <span class="ot">=</span></span>
<span id="cb33-3"><a href="#cb33-3" aria-hidden="true" tabindex="-1"></a> <span class="fu">map</span> <span class="fu">fst</span> <span class="op">.</span> <span class="fu">filter</span> (\(_,v) <span class="ot">-></span> u <span class="op">==</span> v ) <span class="op">.</span> edgeList</span></code></pre></div>
<h2 id="going-io">Going IO</h2>
<p>Ok, pure <code class="verbated">Graph</code> inspection is cool, but how do inspect with IO? Your superior want to know from time to time how many users are connected. He has wrote <code class="verbated">isConnected</code> <code class="verbated">:: User -> IO Bool</code>, and he is asking you to write <code class="verbated">numberOfConnected</code> <code class="verbated">:: Graph User -> IO Int</code>. Using <code class="verbated">traverse</code> on the list of the vertices, you quickly answer:</p>
<div class="sourceCode" id="cb34" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb34-1"><a href="#cb34-1" aria-hidden="true" tabindex="-1"></a><span class="ot">numberOfConnected ::</span> <span class="dt">Graph</span> <span class="dt">User</span> <span class="ot">-></span> <span class="dt">IO</span> <span class="dt">Int</span></span>
<span id="cb34-2"><a href="#cb34-2" aria-hidden="true" tabindex="-1"></a>numberOfConnected <span class="ot">=</span> <span class="fu">fmap</span> (<span class="fu">length</span> <span class="op">.</span> <span class="fu">filter</span> <span class="fu">id</span>) <span class="op">.</span></span>
<span id="cb34-3"><a href="#cb34-3" aria-hidden="true" tabindex="-1"></a> foldg (<span class="fu">pure</span> <span class="dt">Empty</span>) (<span class="fu">fmap</span> <span class="dt">Vertex</span> <span class="op">.</span> isConnected) (liftA2 <span class="dt">Overlay</span>) (liftA2 <span class="dt">Connect</span>) <span class="op">.</span></span>
<span id="cb34-4"><a href="#cb34-4" aria-hidden="true" tabindex="-1"></a> vertexList</span></code></pre></div>
<p>Note that this version is easy to understand and to write, but nor very efficient. One can write a more efficient one using <code class="verbated">foldg</code> and <code class="verbated">IntSet</code>:</p>
<div class="sourceCode" id="cb35" data-language="Haskell" data-frame="single"><pre class="sourceCode haskell prettyprint"><code class="sourceCode haskell"><span id="cb35-1"><a href="#cb35-1" aria-hidden="true" tabindex="-1"></a><span class="kw">import</span> <span class="kw">qualified</span> <span class="dt">Data.IntSet</span> <span class="kw">as</span> <span class="dt">Set</span></span>
<span id="cb35-2"><a href="#cb35-2" aria-hidden="true" tabindex="-1"></a><span class="kw">import</span> <span class="dt">Control.Applicative</span> (liftA2)</span>
<span id="cb35-3"><a href="#cb35-3" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb35-4"><a href="#cb35-4" aria-hidden="true" tabindex="-1"></a><span class="ot">numberOfConnected ::</span> <span class="dt">Graph</span> <span class="dt">User</span> <span class="ot">-></span> <span class="dt">IO</span> <span class="dt">Int</span></span>
<span id="cb35-5"><a href="#cb35-5" aria-hidden="true" tabindex="-1"></a>numberOfConnected <span class="ot">=</span> <span class="fu">fmap</span> Set.size <span class="op">.</span> foldg</span>
<span id="cb35-6"><a href="#cb35-6" aria-hidden="true" tabindex="-1"></a> (<span class="fu">return</span> Set.empty)</span>
<span id="cb35-7"><a href="#cb35-7" aria-hidden="true" tabindex="-1"></a> (\x <span class="ot">-></span> <span class="fu">fmap</span></span>
<span id="cb35-8"><a href="#cb35-8" aria-hidden="true" tabindex="-1"></a> (\y <span class="ot">-></span> <span class="kw">if</span> y</span>
<span id="cb35-9"><a href="#cb35-9" aria-hidden="true" tabindex="-1"></a> <span class="kw">then</span> Set.singleton x</span>
<span id="cb35-10"><a href="#cb35-10" aria-hidden="true" tabindex="-1"></a> <span class="kw">else</span> Set.empty</span>
<span id="cb35-11"><a href="#cb35-11" aria-hidden="true" tabindex="-1"></a> )</span>
<span id="cb35-12"><a href="#cb35-12" aria-hidden="true" tabindex="-1"></a> (isConnected x)</span>
<span id="cb35-13"><a href="#cb35-13" aria-hidden="true" tabindex="-1"></a> )</span>
<span id="cb35-14"><a href="#cb35-14" aria-hidden="true" tabindex="-1"></a> (liftA2 Set.union)</span>
<span id="cb35-15"><a href="#cb35-15" aria-hidden="true" tabindex="-1"></a> (liftA2 Set.union)</span></code></pre></div>
<script src="https://cdn.rawgit.com/google/code-prettify/master/loader/run_prettify.js?lang=hs"></script>
</body>
</html>