-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathfunctionally-solving-problems.html
491 lines (365 loc) · 37.8 KB
/
functionally-solving-problems.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
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
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en" dir="ltr">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<meta name="keywords" content="Erlang, problems, function, RPN calculator, shortest path, recursion, parsing, test case, fold, file" />
<meta name="description" content="Using Erlang to solve sequential programming problems. In this chapter we write a reverse polish notation calculator and write a program to find the shortest path between Heathrow and London." />
<meta name="google-site-verification" content="mi1UCmFD_2pMLt2jsYHzi_0b6Go9xja8TGllOSoQPVU" />
<link rel="stylesheet" type="text/css" href="static/css/screen.css" media="screen" />
<link rel="stylesheet" type="text/css" href="static/css/sh/shCore.css" media="screen" />
<link rel="stylesheet" type="text/css" href="static/css/sh/shThemeLYSE2.css" media="screen" />
<link rel="stylesheet" type="text/css" href="static/css/print.css" media="print" />
<link href="rss" type="application/rss+xml" rel="alternate" title="LYSE news" />
<link rel="icon" type="image/png" href="favicon.ico" />
<link rel="apple-touch-icon" href="static/img/touch-icon-iphone.png" />
<link rel="apple-touch-icon" sizes="72x72" href="static/img/touch-icon-ipad.png" />
<link rel="apple-touch-icon" sizes="114x114" href="static/img/touch-icon-iphone4.png" />
<title>Functionally Solving Problems | Learn You Some Erlang for Great Good!</title>
</head>
<body>
<div id="wrapper">
<div id="header">
<h1>Learn you some Erlang</h1>
<span>for great good!</span>
</div> <!-- header -->
<div id="menu">
<ul>
<li><a href="content.html" title="Home">Home</a></li>
<li><a href="faq.html" title="Frequently Asked Questions">FAQ</a></li>
<li><a href="rss" title="Latest News">RSS</a></li>
<li><a href="static/erlang/learn-you-some-erlang.zip" title="Source Code">Code</a></li>
</ul>
</div><!-- menu -->
<div id="content">
<div class="noscript"><noscript>Hey there, it appears your Javascript is disabled. That's fine, the site works without it. However, you might prefer reading it with syntax highlighting, which requires Javascript!</noscript></div>
<h2>Functionally Solving Problems</h2>
<div class="note" style="margin-top:2.5em">
<p>Sounds like we're ready to do something practical with all that Erlang juice we drank. Nothing new is going to be shown but how to apply bits of what we've seen before. The problems in this chapter were taken from Miran's <a class="external" href="http://learnyouahaskell.com/functionally-solving-problems" title="Miran's chapter">Learn You a Haskell</a>. I decided to take the same solutions so curious readers can compare solutions in Erlang and Haskell as they wish. If you do so, you might find the final results to be pretty similar for two languages with such different syntaxes. This is because once you know functional concepts, they're relatively easy to carry over to other functional languages.</p>
</div>
<h3><a class="section" name="rpn-calculator">Reverse Polish Notation Calculator</a></h3>
<p>Most people have learned to write arithmetic expressions with the operators in-between the numbers (<code>(2 + 2) / 5</code>). This is how most calculators let you insert mathematical expressions and probably the notation you were taught to count with in school. This notation has the downside of needing you to know about operator precedence: multiplication and division are more important (have a higher <em>precedence</em>) than addition and subtraction.</p>
<p>Another notation exists, called <em>prefix notation</em> or <em>Polish notation</em>, where the operator comes before the operands. Under this notation, <code>(2 + 2) / 5</code> would become <code>(/ (+ 2 2) 5)</code>. If we decide to say <code>+</code> and <code>/</code> always take two arguments, then <code>(/ (+ 2 2) 5)</code> can simply be written as <code>/ + 2 2 5</code>.</p>
<p>However, we will instead focus on <em>Reverse Polish notation</em> (or just <em>RPN</em>), which is the opposite of prefix notation: the operator follows the operands. The same example as above in RPN would be written <code>2 2 + 5 /</code>. Other example expressions could be <code>9 * 5 + 7</code> or <code>10 * 2 * (3 + 4) / 2</code> which get translated to <code>9 5 * 7 +</code> and <code>10 2 * 3 4 + * 2 /</code>, respectively. This notation was used a whole lot in early models of calculators as it would take little memory to use. In fact some people still carry RPN calculators around. We'll write one of these.</p>
<p>First of all, it might be good to understand how to read RPN expressions. One way to do it is to find the operators one by one and then regroup them with their operands by arity:</p>
<pre class="expand">
10 4 3 + 2 * -
10 (4 3 +) 2 * -
10 ((4 3 +) 2 *) -
(10 ((4 3 +) 2 *) -)
(10 (7 2 *) -)
(10 14 -)
-4
</pre>
<p>However, in the context of a computer or a calculator, a simpler way to do it is to make a <em>stack</em> of all the operands as we see them. Taking the mathematical expression <code>10 4 3 + 2 * -</code>, the first operand we see is <samp>10</samp>. We add that to the stack. Then there's <samp>4</samp>, so we also push that on top of the stack. In third place, we have <samp>3</samp>; let's push that one on the stack too. Our stack should now look like this:</p>
<img class="center explanation" src="static/img/stack1.png" width="95" height="113" alt="A stack showing the values [3 4 10]" />
<p>The next character to parse is a <code>+</code>. That one is a function of arity 2. In order to use it we will need to feed it two operands, which will be taken from the stack:</p>
<img class="center explanation" src="static/img/stack2.png" width="336" height="137" alt="Drawing showing the operands 3 and 4 taken from the stack, used in the postfix exppression '3 4 +' and returning 7 on top of the stack" />
<p>So we take that <samp>7</samp> and push it back on top of the stack (yuck, we don't want to keep these filthy numbers floating around!) The stack is now <samp>[7,10]</samp> and what's left of the expression is <code>2 * -</code>. We can take the <samp>2</samp> and push it on top of the stack. We then see <code>*</code>, which needs two operands to work. Again, we take them from the stack:</p>
<img class="center explanation" src="static/img/stack3.png" width="340" height="134" alt="Drawing showing the operands 2 and 7 taken from the stack, used in '7 2 *', which returns 14 and pushes it on top of the stack." />
<p>And push 14 back on top of our stack. All that remains is <code>-</code>, which also needs two operands. O Glorious luck! There are two operands left in our stack. Use them!</p>
<img class="center explanation" src="static/img/stack4.png" width="275" height="97" alt="Drawing of the operands 14 and 10 taken from the stack into the operation '10 14 -' for the result '-4'" />
<p>And so we have our result. This stack-based approach is relatively fool-proof and the low amount of parsing needed to be done before starting to calculate results explains why it was a good idea for old calculators to use this. There are other reasons to use RPN, but this is a bit out of the scope of this guide, so you might want to hit the <a class="external" href="http://en.wikipedia.org/wiki/Reverse_Polish_notation">Wikipedia article</a> instead.</p>
<p>Writing this solution in Erlang is not too hard once we've done the complex stuff. It turns out the tough part is figuring out what steps need to be done in order to get our end result and we just did that. Neat. Open a file named <code><a class="source" href="static/erlang/calc.erl" title="the file itself">calc.erl</a></code>.</p>
<p>The first part to worry about is how we're going to represent a mathematical expression. To make things simple, we'll probably input them as a string: <code>"10 4 3 + 2 * -"</code>. This string has whitespace, which isn't part of our problem-solving process, but is necessary in order to use a simple tokenizer. What would be usable then is a list of terms of the form <code>["10","4","3","+","2","*","-"]</code> after going through the tokenizer. Turns out the function <code><a class="docs" href="http://erldocs.com/17.3/stdlib/string.html#tokens/2" title="non-official doc">string:tokens/2</a></code> does just that:</p>
<pre class="brush:eshell">
1> string:tokens("10 4 3 + 2 * -", " ").
["10","4","3","+","2","*","-"]
</pre>
<p>That will be a good representation for our expression. The next part to define is the stack. How are we going to do that? You might have noticed that Erlang's lists act a lot like a stack. Using the cons (<code>|</code>) operator in <code>[Head|Tail]</code> effectively behaves the same as pushing <var>Head</var> on top of a stack (<var>Tail</var>, in this case). Using a list for a stack will be good enough.</p>
<p>To read the expression, we just have to do the same as we did when solving the problem by hand. Read each value from the expression, if it's a number, put it on the stack. If it's a function, pop all the values it needs from the stack, then push the result back in. To generalize, all we need to do is go over the whole expression as a loop only once and accumulate the results. Sounds like the perfect job for a fold!</p>
<p>What we need to plan for is the function that <code><a class="docs" href="http://erldocs.com/17.3/stdlib/lists.html#foldl/3">lists:foldl/3</a></code> will apply on every operator and operand of the expression. This function, because it will be run in a fold, will need to take two arguments: the first one will be the element of the expression to work with and the second one will be the stack.</p>
<p>We can start writing our code in the <code><a class="source" href="static/erlang/calc.erl">calc.erl</a></code> file. We'll write the function responsible for all the looping and also the removal of spaces in the expression:</p>
<pre class="brush:erl">
-module(calc).
-export([rpn/1]).
rpn(L) when is_list(L) ->
[Res] = lists:foldl(fun rpn/2, [], string:tokens(L, " ")),
Res.
</pre>
<p>We'll implement <code>rpn/2</code> next. Note that because each operator and operand from the expression ends up being put on top of the stack, the solved expression's result will be on that stack. We need to get that last value out of there before returning it to the user. This is why we pattern match over <code>[Res]</code> and only return <var>Res</var>.</p>
<p>Alright, now to the harder part. Our <code>rpn/2</code> function will need to handle the stack for all values passed to it. The head of the function will probably look like <code>rpn(Op,Stack)</code> and its return value like <code>[NewVal|Stack]</code>. When we get regular numbers, the operation will be:</p>
<pre class="brush:erl">
rpn(X, Stack) -> [read(X)|Stack].
</pre>
<p>Here, <code>read/1</code> is a function that converts a string to an integer or floating point value. Sadly, there is no built-in function to do this in Erlang (only one or the other). We'll add it ourselves:</p>
<pre class="brush:erl">
read(N) ->
case string:to_float(N) of
{error,no_float} -> list_to_integer(N);
{F,_} -> F
end.
</pre>
<p>Where <code><a class="docs" href="http://erldocs.com/17.3/stdlib/string.html#to_float/1" title="NO! don't click this! I explain it in this very sentence!">string:to_float/1</a></code> does the conversion from a string such as <samp>"13.37"</samp> to its numeric equivalent. However, if there is no way to read a floating point value, it returns <code>{error,no_float}</code>. When that happens, we need to call <code>list_to_integer/1</code> instead.</p>
<p>Now back to <code>rpn/2</code>. The numbers we encounter all get added to the stack. However, because our pattern matches on anything (see <a class="chapter local" href="syntax-in-functions.html#pattern-matching">Pattern Matching</a>), operators will also get pushed on the stack. To avoid this, we'll put them all in preceding clauses. The first one we'll try this with is the addition:</p>
<pre class="brush:erl">
rpn("+", [N1,N2|S]) -> [N2+N1|S];
rpn(X, Stack) -> [read(X)|Stack].
</pre>
<p>We can see that whenever we encounter the <code>"+"</code> string, we take two numbers from the top of the stack (<var>N1</var>,<var>N2</var>) and add them before pushing the result back onto that stack. This is exactly the same logic we applied when solving the problem by hand. Trying the program we can see that it works:</p>
<pre class="brush:eshell">
1> c(calc).
{ok,calc}
2> calc:rpn("3 5 +").
8
3> calc:rpn("7 3 + 5 +").
15
</pre>
<p>The rest is trivial, as you just need to add all the other operators:</p>
<pre class="brush:erl">
rpn("+", [N1,N2|S]) -> [N2+N1|S];
rpn("-", [N1,N2|S]) -> [N2-N1|S];
rpn("*", [N1,N2|S]) -> [N2*N1|S];
rpn("/", [N1,N2|S]) -> [N2/N1|S];
rpn("^", [N1,N2|S]) -> [math:pow(N2,N1)|S];
rpn("ln", [N|S]) -> [math:log(N)|S];
rpn("log10", [N|S]) -> [math:log10(N)|S];
rpn(X, Stack) -> [read(X)|Stack].
</pre>
<p>Note that functions that take only one argument such as logarithms only need to pop one element from the stack. It is left as an exercise to the reader to add functions such as 'sum' or 'prod' which return the sum of all the elements read so far or the products of them all. To help you out, they are implemented in my version of <code><a class="source" href="static/erlang/calc.erl">calc.erl</a></code> already.</p>
<p>To make sure this all works fine, we'll write very simple unit tests. Erlang's <code>=</code> operator can act as an <em>assertion</em> function. Assertions should crash whenever they encounter unexpected values, which is exactly what we need. Of course, there are more advanced testing frameworks for Erlang, including <a class="docs" href="http://erlang.org/doc/apps/common_test/write_test_chapter.html" title="Common Test's user guide">Common Test</a> and <a class="docs" href="http://erlang.org/doc/apps/eunit/chapter.html" title="EUnit's user guide">EUnit</a>. We'll check them out later, but for now the basic <code>=</code> will do the job:</p>
<pre class="brush:erl">
rpn_test() ->
5 = rpn("2 3 +"),
87 = rpn("90 3 -"),
-4 = rpn("10 4 3 + 2 * -"),
-2.0 = rpn("10 4 3 + 2 * - 2 /"),
ok = try
rpn("90 34 12 33 55 66 + * - +")
catch
error:{badmatch,[_|_]} -> ok
end,
4037 = rpn("90 34 12 33 55 66 + * - + -"),
8.0 = rpn("2 3 ^"),
true = math:sqrt(2) == rpn("2 0.5 ^"),
true = math:log(2.7) == rpn("2.7 ln"),
true = math:log10(2.7) == rpn("2.7 log10"),
50 = rpn("10 10 10 20 sum"),
10.0 = rpn("10 10 10 20 sum 5 /"),
1000.0 = rpn("10 10 20 0.5 prod"),
ok.
</pre>
<p>The test function tries all operations; if there's no exception raised, the tests are considered successful. The first four tests check that the basic arithmetic functions work right. The fifth test specifies behaviour I have not explained yet. The <code>try ... catch</code> expects a badmatch error to be thrown because the expression can't work:</p>
<pre class="expand">
90 34 12 33 55 66 + * - +
90 (34 (12 (33 (55 66 +) *) -) +)
</pre>
<p>At the end of <code>rpn/1</code>, the values <samp>-3947</samp> and <samp>90</samp> are left on the stack because there is no operator to work on the <samp>90</samp> that hangs there. Two ways to handle this problem are possible: either ignore it and only take the value on top of the stack (which would be the last result calculated) or crash because the arithmetic is wrong. Given Erlang's policy is to let it crash, it's what was chosen here. The part that actually crashes is the <code>[Res]</code> in <code>rpn/1</code>. That one makes sure only one element, the result, is left in the stack.</p>
<p>The few tests that are of the form <code>true = FunctionCall1 == FunctionCall2</code> are there because you can't have a function call on the left hand side of <code>=</code>. It still works like an assert because we compare the comparison's result to <samp>true</samp>.</p>
<p>I've also added the test cases for the sum and prod operators so you can exercise yourselves implementing them. If all tests are successful, you should see the following:</p>
<pre class="brush:eshell">
1> c(calc).
{ok,calc}
2> calc:rpn_test().
ok
3> calc:rpn("1 2 ^ 2 2 ^ 3 2 ^ 4 2 ^ sum 2 -").
28.0
</pre>
<p>Where <samp>28</samp> is indeed equal to <code>sum(1² + 2² + 3² + 4²) - 2</code>. Try as many of them as you wish.</p>
<p>One thing that could be done to make our calculator better would be to make sure it raises <code>badarith</code> errors when it crashes because of unknown operators or values left on the stack, rather than our current <code>badmatch</code> error. It would certainly make debugging easier for the user of the calc module.</p>
<h3><a class="section" name="heathrow-to-london">Heathrow to London</a></h3>
<p>Our next problem is also taken from <a class="external" href="http://learnyouahaskell.com/functionally-solving-problems#heathrow-to-london">Learn You a Haskell</a>. You're on a plane due to land at Heathrow airport in the next hours. You have to get to London as fast as possible; your rich uncle is dying and you want to be the first there to claim dibs on his estate.</p>
<p>There are two roads going from Heathrow to London and a bunch of smaller streets linking them together. Because of speed limits and usual traffic, some parts of the roads and smaller streets take longer to drive on than others. Before you land, you decide to maximize your chances by finding the optimal path to his house. Here's the map you've found on your laptop:</p>
<img class="center explanation" src="static/img/road1.png" width="494" height="172" alt="A little map with a main road 'A' with 4 segments of length 50, 5, 40 and 10, B with 4 segments of length 10, 90, 2 and 8, where each of these segments are joined by paths 'X' of length 30, 20, 25 and 0." />
<p>Having become a huge fan of Erlang after reading online books, you decide to solve the problem using that language. To make it easier to work with the map, you enter data the following way in a file named <a class="source" href="static/erlang/road.txt">road.txt</a>:</p>
<pre class="expand">
50
10
30
5
90
20
40
2
25
10
8
0
</pre>
<p>The road is laid in the pattern: <code>A1, B1, X1, A2, B2, X2, ..., An, Bn, Xn</code>, where <var>X</var> is one of the roads joining the A side to the B side of the map. We insert a <samp>0</samp> as the last <var>X</var> segment, because no matter what we do we're at our destination already. Data can probably be organized in tuples of 3 elements (triples) of the form <code>{A,B,X}</code>.</p>
<p>The next thing you realize is that it's worth nothing to try to solve this problem in Erlang when you don't know how to solve it by hand to begin with. In order to do this, we'll use what recursion taught us.</p>
<p>When writing a recursive function, the first thing to do is to find our base case. For our problem at hand, this would be if we had only one tuple to analyze, that is, if we only had to choose between <var>A</var>, <var>B</var> (and crossing <var>X</var>, which in this case is useless because we're at destination):</p>
<img class="center explanation" src="static/img/road2.png" width="244" height="130" alt="Only two paths A and B: A of length 10 and B of length 15." />
<p>Then the choice is only between picking which of path A or path B is the shortest. If you've learned your recursion right, you know that we ought to try and converge towards the base case. This means that on each step we'll take, we'll want to reduce the problem to choosing between A and B for the next step.</p>
<p>Let's extend our map and start over:</p>
<img class="center explanation" src="static/img/road3.png" width="290" height="123" alt="Path A: 5, 10. Path B: 1, 15. Crossover path X: 3." title="No idea why you'd need to switch paths in a bathroom." />
<p>Ah! It gets interesting! How can we reduce the triple <code>{5,1,3}</code> to a strict choice between A and B? Let's see how many options are possible for A. To get to the intersection of <var>A1</var> and <var>A2</var> (I'll call this the <em>point</em> <var>A1</var>), I can either take road <var>A1</var> directly (<samp>5</samp>), or come from <var>B1</var> (<samp>1</samp>) and then cross over <var>X1</var> (<samp>3</samp>). In this case, The first option (<samp>5</samp>) is longer than the second one (<samp>4</samp>). For the option A, the shortest path is <code>[B, X]</code>. So what are the options for B? You can either proceed from <var>A1</var> (<samp>5</samp>) then cross over <var>X1</var> (<samp>3</samp>), or strictly take the path <var>B1</var> (<samp>1</samp>).</p>
<p>Alright! What we've got is a length <samp>4</samp> with the path <code>[B, X]</code> towards the first intersection A and a length <samp>1</samp> with the path <code>[B]</code> towards the intersection of <var>B1</var> and <var>B2</var>. We then have to decide what to pick between going to the second point A (the intersection of <var>A2</var> and the endpoint or <var>X2</var>) and the second point B (intersection of <var>B2</var> and <var>X2</var>). To make a decision, I suggest we do the same as before. Now you don't have much choice but to obey, given I'm the guy writing this text. Here we go!</p>
<p>All possible paths to take in this case can be found in the same way as the previous one. We can get to the next point A by either taking the path <var>A2</var> from <code>[B, X]</code>, which gives us a length of <samp>14</samp> (<code>14 = 4 + 10</code>), or by taking <var>B2</var> then <var>X2</var> from <code>[B]</code>, which gives us a length of <samp>16</samp> (<code>16 = 1 + 15 + 0</code>). In this case, the path <code>[B, X, A]</code> is better than <code>[B, B, X]</code>.</p>
<img class="center explanation" src="static/img/road3.2.png" width="364" height="149" alt="Same drawing as the one above, but with the paths drawn over." />
<p>We can also get to the next point B by either taking the path <var>A2</var> from <code>[B, X]</code> and then crossing over <var>X2</var> for a length of <samp>14</samp> (<code>14 = 4 + 10 + 0</code>), or by taking the road <var>B2</var> from <code>[B]</code> for a length of <samp>16</samp> (<code>16 = 1 + 15</code>). Here, the best path is to pick the first option, <code>[B, X, A, X]</code>.</p>
<p>So when this whole process is done, we're left with two paths, A or B, both of length <samp>14</samp>. Either of them is the right one. The last selection will always have two paths of the same length, given the last X segment has a length 0. By solving our problem recursively, we've made sure to always get the shortest path at the end. Not too bad, eh?</p>
<p>Subtly enough, we've given ourselves the basic logical parts we need to build a recursive function. You can implement it if you want, but I promised we would have very few recursive functions to write ourselves. We'll use a fold.</p>
<div class="note">
<p><strong>Note:</strong> while I have shown folds being used and constructed with lists, folds represent a broader concept of iterating over a data structure with an accumulator. As such, folds can be implemented over trees, dictionaries, arrays, database tables, etc.</p>
<p>It is sometimes useful when experimenting to use abstractions like maps and folds; they make it easier to later change the data structure you use to work with your own logic.</p>
</div>
<p>So where were we? Ah, yes! We had the file we're going to feed as input ready. To do file manipulations, the <a class="docs" href="http://erldocs.com/17.3/kernel/file.html">file module</a> is our best tool. It contains many functions common to many programming languages in order to deal with files themselves (setting permissions, moving files around, renaming and deleting them, etc.)</p>
<p>It also contains the usual functions to read and/or write from files such as: <code><a class="docs" href="http://erldocs.com/17.3/kernel/file.html#open/2" title="Oh, look! another link cloud!">file:open/2</a></code> and <code><a class="docs" href="http://erldocs.com/17.3/kernel/file.html#close/1" title="Man I wonder what I can say on that one">file:close/1</a></code> to do as their names say (opening and closing files!), <code><a class="docs" href="http://erldocs.com/17.3/kernel/file.html#read/2" title="probably something like 'official link to unofficial doc'">file:read/2</a></code> to get the content a file (either as string or a binary), <code><a class="docs" href="http://erldocs.com/17.3/kernel/file.html#read_line/1" title="It's boring but true...">file:read_line/1</a></code> to read a single line, <code><a class="docs" href="http://erldocs.com/17.3/kernel/file.html#position/3" title="Is this what we call reading between the lines?">file:position/3</a></code> to move the pointer of an open file to a given position, etc.</p>
<p>There's a bunch of shortcut functions in there too, such as <code><a class="docs" href="http://erldocs.com/17.3/kernel/file.html#read_file/1" title="Maybe it is a subliminal message?">file:read_file/1</a></code> (opens and reads the contents as a binary), <code><a class="docs" href="http://erldocs.com/17.3/kernel/file.html#consult/1" title="JOIN THE NAVY">file:consult/1</a></code> (opens and parses a file as Erlang terms) or <code><a class="docs" href="http://erldocs.com/17.3/kernel/file.html#pread/2" title="And 5 cents added to my bank account">file:pread/2</a></code> (changes a position and then reads) and <code><a class="docs" href="http://erldocs.com/17.3/kernel/file.html#pwrite/2" title="Finally, this is over. I'm so sorry.">pwrite/2</a></code> (changes the position and writes content).</p>
<p>With all these choices available, it's going to be easy to find a function to read our <a class="source" href="static/erlang/road.txt">road.txt</a> file. Because we know our road is relatively small, we're going to call <code>file:read_file("road.txt").'</code>:</p>
<pre class="brush:eshell">
1> {ok, Binary} = file:read_file("road.txt").
{ok,<<"50\r\n10\r\n30\r\n5\r\n90\r\n20\r\n40\r\n2\r\n25\r\n10\r\n8\r\n0\r\n">>}
2> S = string:tokens(binary_to_list(Binary), "\r\n\t ").
["50","10","30","5","90","20","40","2","25","10","8","0"]
</pre>
<p>Note that in this case, I added a space (<code>" "</code>) and a tab (<code>"\t"</code>) to the valid tokens so the file could have been written in the form <samp>"50 10 30 5 90 20 40 2 25 10 8 0"</samp> too. Given that list, we'll need to transform the strings into integers. We'll use a similar manner to what we used in our RPN calculator:</p>
<pre class="brush:eshell">
3> [list_to_integer(X) || X <- S].
[50,10,30,5,90,20,40,2,25,10,8,0]
</pre>
<p>Let's start a new module called <a class="source" href="static/erlang/road.erl">road.erl</a> and write this logic down:</p>
<pre class="brush:erl">
-module(road).
-compile(export_all).
main() ->
File = "road.txt",
{ok, Bin} = file:read_file(File),
parse_map(Bin).
parse_map(Bin) when is_binary(Bin) ->
parse_map(binary_to_list(Bin));
parse_map(Str) when is_list(Str) ->
[list_to_integer(X) || X <- string:tokens(Str,"\r\n\t ")].
</pre>
<p>The function <code>main/0</code> is here responsible for reading the content of the file and passing it on to <code>parse_map/1</code>. Because we use the function <code>file:read_file/1</code> to get the contents out of <a class="source" href="static/erlang/road.txt">road.txt</a>, the result we obtain is a binary. For this reason, I've made the function <code>parse_map/1</code> match on both lists and binaries. In the case of a binary, we just call the function again with the string being converted to a list (our function to split the string works on lists only.)</p>
<p>The next step in parsing the map would be to regroup the data into the <code>{A,B,X}</code> form described earlier. Sadly, there's no simple generic way to pull elements from a list 3 at a time, so we'll have to pattern match our way in a recursive function in order to do it:</p>
<pre class="brush:erl">
group_vals([], Acc) ->
lists:reverse(Acc);
group_vals([A,B,X|Rest], Acc) ->
group_vals(Rest, [{A,B,X} | Acc]).
</pre>
<p>That function works in a standard tail-recursive manner; there's nothing too complex going on here. We'll just need to call it by modifying <code>parse_map/1</code> a bit:</p>
<pre class="brush:erl">
parse_map(Bin) when is_binary(Bin) ->
parse_map(binary_to_list(Bin));
parse_map(Str) when is_list(Str) ->
Values = [list_to_integer(X) || X <- string:tokens(Str,"\r\n\t ")],
group_vals(Values, []).
</pre>
<p>If we try and compile it all, we should now have a road that makes sense:</p>
<pre class="brush:eshell">
1> c(road).
{ok,road}
2> road:main().
[{50,10,30},{5,90,20},{40,2,25},{10,8,0}]
</pre>
<p>Ah yes, that looks right. We get the blocks we need to write our function that will then fit in a fold. For this to work, finding a good accumulator is necessary.</p>
<p>To decide what to use as an accumulator, the method I find the easiest to use is to imagine myself in the middle of the algorithm while it runs. For this specific problem, I'll imagine that I'm currently trying to find the shortest path of the second triple (<code>{5,90,20}</code>). To decide on which path is the best, I need to have the result from the previous triple. Luckily, we know how to do it, because we don't need an accumulator and we got all that logic out already. So for A:</p>
<img class="center explanation" src="static/img/road1.2.png" width="506" height="249" alt="Visual re-explanation of how to find the shortest path" title="biggest image on this site (except the squid) yet!" />
<p>And take the shortest of these two paths. For B, it was similar:</p>
<img class="center explanation" src="static/img/road1.3.png" width="506" height="236" alt="Visual re-explanation of how to find the shortest path" title="I do love copy/pasting." />
<p>So now we know that the current best path coming from A is <code>[B, X]</code>. We also know it has a length of 40. For B, the path is simply <code>[B]</code> and the length is 10. We can use this information to find the next best paths for A and B by reapplying the same logic, but counting the previous ones in the expression. The other data we need is the path traveled so we can show it to the user. Given we need two paths (one for A and one for B) and two accumulated lengths, our accumulator can take the form <code>{{DistanceA, PathA}, {DistanceB, PathB}}</code>. That way, each iteration of the fold has access to all the state and we build it up to show it to the user in the end.</p>
<p>This gives us all the parameters our function will need: the <code>{A,B,X}</code> triples and an accumulator of the form <code>{{DistanceA,PathA}, {DistanceB,PathB}}</code>.</p>
<p>Putting this into code in order to get our accumulator can be done the following way:</p>
<pre class="brush:erl">
shortest_step({A,B,X}, {{DistA,PathA}, {DistB,PathB}}) ->
OptA1 = {DistA + A, [{a,A}|PathA]},
OptA2 = {DistB + B + X, [{x,X}, {b,B}|PathB]},
OptB1 = {DistB + B, [{b,B}|PathB]},
OptB2 = {DistA + A + X, [{x,X}, {a,A}|PathA]},
{erlang:min(OptA1, OptA2), erlang:min(OptB1, OptB2)}.
</pre>
<p>Here, <var>OptA1</var> gets the first option for A (going through <var>A</var>), <var>OptA2</var> the second one (going through <var>B</var> then <var>X</var>). The variables <var>OptB1</var> and <var>OptB2</var> get the similar treatment for point B. Finally, we return the accumulator with the paths obtained.</p>
<p>About the paths saved in the code above, note that I decided to use the form <code>[{x,X}]</code> rather than <code>[x]</code> for the simple reason that it might be nice for the user to know the length of each segment. The other thing I'm doing is that I'm accumulating the paths backwards (<code>{x,X}</code> comes before <code>{b,B}</code>.) This is because we're in a fold, which is tail recursive: the whole list is reversed, so it is necessary to put the last one traversed before the others.</p>
<p>Finally, I use <code>erlang:min/2</code> to find the shortest path. It might sound weird to use such a comparison function on tuples, but remember that every Erlang term can be compared to any other! Because the length is the first element of the tuple, we can sort them that way.</p>
<p>What's left to do is to stick that function into a fold:</p>
<pre class="brush:erl">
optimal_path(Map) ->
{A,B} = lists:foldl(fun shortest_step/2, {{0,[]}, {0,[]}}, Map),
{_Dist,Path} = if hd(element(2,A)) =/= {x,0} -> A;
hd(element(2,B)) =/= {x,0} -> B
end,
lists:reverse(Path).
</pre>
<p>At the end of the fold, both paths should end up having the same distance, except one's going through the final <code>{x,0}</code> segment. The <code>if</code> looks at the last visited element of both paths and returns the one that doesn't go through <code>{x,0}</code>. Picking the path with the fewest steps (compare with <code>length/1</code>) would also work. Once the shortest one has been selected, it is reversed (it was built in a tail-recursive manner; you <strong>must</strong> reverse it). You can then display it to the world, or keep it secret and get your rich uncle's estate. To do that, you have to modify the main function to call <code>optimal_path/1</code>. Then it can be compiled.</p>
<pre class="brush:erl">
main() ->
File = "road.txt",
{ok, Bin} = file:read_file(File),
optimal_path(parse_map(Bin)).
</pre>
<p>Oh, look! We've got the right answer! Great Job!</p>
<pre class="brush:eshell">
1> c(road).
{ok,road}
2> road:main().
[{b,10},{x,30},{a,5},{x,20},{b,2},{b,8}]
</pre>
<p>Or, to put it in a visual way:</p>
<img class="center explanation" src="static/img/road1.4.png" width="426" height="157" alt="The shortest path, going through [b,x,a,x,b,b]" />
<p>But you know what would be really useful? Being able to run our program from outside the Erlang shell. We'll need to change our main function again:</p>
<pre class="brush:erl">
main([FileName]) ->
{ok, Bin} = file:read_file(FileName),
Map = parse_map(Bin),
io:format("~p~n",[optimal_path(Map)]),
erlang:halt().
</pre>
<p>The main function now has an arity of 1, needed to receive parameters from the command line. I've also added the function <code><a class="docs" href="http://erldocs.com/17.3/erts/erlang.html#halt/0" title="Unofficial and pretty Erlang documentation">erlang:halt/0</a></code>, which will shut down the Erlang VM after being called. I've also wrapped the call to <code>optimal_path/1</code> into <code>io:format/2</code> because that's the only way to have the text visible outside the Erlang shell.</p>
<p>With all of this, your <a class="source" href="static/erlang/road.erl">road.erl</a> file should now look like this (minus comments):</p>
<pre class="brush:erl">
-module(road).
-compile(export_all).
main([FileName]) ->
{ok, Bin} = file:read_file(FileName),
Map = parse_map(Bin),
io:format("~p~n",[optimal_path(Map)]),
erlang:halt(0).
%% Transform a string into a readable map of triples
parse_map(Bin) when is_binary(Bin) ->
parse_map(binary_to_list(Bin));
parse_map(Str) when is_list(Str) ->
Values = [list_to_integer(X) || X <- string:tokens(Str,"\r\n\t ")],
group_vals(Values, []).
group_vals([], Acc) ->
lists:reverse(Acc);
group_vals([A,B,X|Rest], Acc) ->
group_vals(Rest, [{A,B,X} | Acc]).
%% Picks the best of all paths, woo!
optimal_path(Map) ->
{A,B} = lists:foldl(fun shortest_step/2, {{0,[]}, {0,[]}}, Map),
{_Dist,Path} = if hd(element(2,A)) =/= {x,0} -> A;
hd(element(2,B)) =/= {x,0} -> B
end,
lists:reverse(Path).
%% actual problem solving
%% change triples of the form {A,B,X}
%% where A,B,X are distances and a,b,x are possible paths
%% to the form {DistanceSum, PathList}.
shortest_step({A,B,X}, {{DistA,PathA}, {DistB,PathB}}) ->
OptA1 = {DistA + A, [{a,A}|PathA]},
OptA2 = {DistB + B + X, [{x,X}, {b,B}|PathB]},
OptB1 = {DistB + B, [{b,B}|PathB]},
OptB2 = {DistA + A + X, [{x,X}, {a,A}|PathA]},
{erlang:min(OptA1, OptA2), erlang:min(OptB1, OptB2)}.
</pre>
<p>And running the code:</p>
<pre class="brush:eshell">
$ erlc road.erl
$ erl -noshell -run road main road.txt
[{b,10},{x,30},{a,5},{x,20},{b,2},{b,8}]
</pre>
<p>And yep, it's right! It's pretty much all you need to do to get things to work. You could make yourself a bash/batch file to wrap the line into a single executable, or you could check out <a class="docs" href="http://erlang.org/doc/man/escript.html">escript</a> to get similar results.</p>
<p>As we've seen with these two exercises, solving problems is much easier when you break them off in small parts that you can solve individually before piecing everything together. It's also not worth much to go ahead and program something without understanding it. Finally, a few tests are always appreciated. They'll let you make sure everything works fine and will let you change the code without changing the results at the end.</p>
<ul class="navigation">
<li><a href="errors-and-exceptions.html" title="Previous chapter">< Previous</a></li>
<li><a href="contents.html" title="Index">Index</a></li>
<li><a href="a-short-visit-to-common-data-structures.html" title="Next chapter">Next ></a></li>
</ul>
</div><!-- content -->
<div id="footer">
<a href="http://creativecommons.org/licenses/by-nc-nd/3.0/" title="Creative Commons License Details"><img src="static/img/cc.png" width="88" height="31" alt="Creative Commons Attribution Non-Commercial No Derivative License" /></a>
<p>Except where otherwise noted, content on this site is licensed under a Creative Commons Attribution Non-Commercial No Derivative License</p>
</div> <!-- footer -->
</div> <!-- wrapper -->
<div id="grass" />
<script type="text/javascript" src="static/js/shCore.js"></script>
<script type="text/javascript" src="static/js/shBrushErlang2.js%3F11"></script>
<script type="text/javascript">
SyntaxHighlighter.defaults.gutter = false;
SyntaxHighlighter.all();
</script>
</body>
</html>