fparsec / Doc / html / users-guide / where-is-the-monad.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
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
 <title>Where is the monad?</title>
 <link rel="stylesheet" type="text/css" media="all" href="../css/style.css" />
 <link rel="stylesheet" type="text/css" media="screen" href="../css/screen-sidebar.css" />
 <!--[if lt IE 9]>
 <link rel="stylesheet" type="text/css" media="all" href="../css/style-ie.css" />
 <![endif]-->
 <!--[if IE 6]>
 <link rel="stylesheet" type="text/css" media="all" href="../css/style-ie6.css" />
 <![endif]-->
 <link rel="stylesheet" type="text/css" media="print" href="../css/print.css" />
</head>
<body>
 <div id="fixed-layer">
 <div id="fixed-wrapper">
 <div id="sidebar">
  <div id="top-links"><span><a href="http://bitbucket.org/fparsec/main">FParsec @ BitBucket</a> | <a href="https://bitbucket.org/fparsec/main/issues">Report a bug</a> | <a href="mailto:fparsec [at] quanttec.com?subject=FParsec&amp;body=Hello Stephan,%0A%0A[your feedback]">Feedback</a></span></div>
  <div id="nav-tree">
   <table class="nav n1">
    <tbody class="nav-open n1">
     <tr class="nav-entry n1 _1">
      <td class="nav-number n1"></td>
      <td class="nav-title n1"><a href="../index.html">FParsec Documentation</a></td>
     </tr>
     <tr class="nav-subentries n1 _1">
      <td class="nav-subentries-number n1"></td>
      <td class="nav-subentries n1">
       <table class="nav n2">
        <tbody class="nav-before-open n2">
         <tr class="nav-entry n2 _1">
          <td class="nav-number n2"><a href="../about/index.html"><span class="section-number">1</span><span class="nav-space"></span></a></td>
          <td class="nav-title n2"><a href="../about/index.html">About FParsec</a></td>
         </tr>
         <tr class="nav-entry n2 _2">
          <td class="nav-number n2"><a href="../license.html"><span class="section-number">2</span><span class="nav-space"></span></a></td>
          <td class="nav-title n2"><a href="../license.html">License</a></td>
         </tr>
         <tr class="nav-entry n2 _3">
          <td class="nav-number n2">
           <a href="../download-and-installation.html"><span class="section-number">3</span><span class="nav-space"></span></a>
          </td>
          <td class="nav-title n2"><a href="../download-and-installation.html">Download and installation</a></td>
         </tr>
         <tr class="nav-entry n2 _4">
          <td class="nav-number n2"><a href="../tutorial.html"><span class="section-number">4</span><span class="nav-space"></span></a></td>
          <td class="nav-title n2"><a href="../tutorial.html">Tutorial</a></td>
         </tr>
        </tbody>
        <tbody class="nav-open n2">
         <tr class="nav-entry n2 _5">
          <td class="nav-number n2"><a href="index.html"><span class="section-number">5</span><span class="nav-space"></span></a></td>
          <td class="nav-title n2"><a href="index.html">User’s Guide</a></td>
         </tr>
         <tr class="nav-subentries n2 _5">
          <td class="nav-subentries-number n2"></td>
          <td class="nav-subentries n2">
           <table class="nav n3">
            <tbody class="nav-before-open n3">
             <tr class="nav-entry n3 _1">
              <td class="nav-number n3"><a href="parser-functions.html"><span class="section-number">1</span><span class="nav-space"></span></a></td>
              <td class="nav-title n3"><a href="parser-functions.html">Parser functions</a></td>
             </tr>
             <tr class="nav-entry n3 _2">
              <td class="nav-number n3">
               <a href="running-parsers-on-input.html"><span class="section-number">2</span><span class="nav-space"></span></a>
              </td>
              <td class="nav-title n3"><a href="running-parsers-on-input.html">Running parsers on input</a></td>
             </tr>
             <tr class="nav-entry n3 _3">
              <td class="nav-number n3">
               <a href="internals-of-a-simple-parser-function.html"><span class="section-number">3</span><span class="nav-space"></span></a>
              </td>
              <td class="nav-title n3">
               <a href="internals-of-a-simple-parser-function.html">Internals of a simple <code class="fsharp"><span class="ci">Parser</span></code>
               function</a>
              </td>
             </tr>
             <tr class="nav-entry n3 _4">
              <td class="nav-number n3">
               <a href="applying-parsers-in-sequence.html"><span class="section-number">4</span><span class="nav-space"></span></a>
              </td>
              <td class="nav-title n3"><a href="applying-parsers-in-sequence.html">Applying parsers in sequence</a></td>
             </tr>
             <tr class="nav-entry n3 _5">
              <td class="nav-number n3"><a href="parsing-sequences.html"><span class="section-number">5</span><span class="nav-space"></span></a></td>
              <td class="nav-title n3"><a href="parsing-sequences.html">Parsing sequences</a></td>
             </tr>
             <tr class="nav-entry n3 _6">
              <td class="nav-number n3">
               <a href="parsing-alternatives.html"><span class="section-number">6</span><span class="nav-space"></span></a>
              </td>
              <td class="nav-title n3"><a href="parsing-alternatives.html">Parsing alternatives</a></td>
             </tr>
             <tr class="nav-entry n3 _7">
              <td class="nav-number n3">
               <a href="looking-ahead-and-backtracking.html"><span class="section-number">7</span><span class="nav-space"></span></a>
              </td>
              <td class="nav-title n3"><a href="looking-ahead-and-backtracking.html">Looking ahead and backtracking</a></td>
             </tr>
             <tr class="nav-entry n3 _8">
              <td class="nav-number n3">
               <a href="customizing-error-messages.html"><span class="section-number">8</span><span class="nav-space"></span></a>
              </td>
              <td class="nav-title n3"><a href="customizing-error-messages.html">Customizing error messages</a></td>
             </tr>
             <tr class="nav-entry n3 _9">
              <td class="nav-number n3">
               <a href="parsing-with-user-state.html"><span class="section-number">9</span><span class="nav-space"></span></a>
              </td>
              <td class="nav-title n3"><a href="parsing-with-user-state.html">Parsing with user state</a></td>
             </tr>
            </tbody>
            <tbody class="nav-open selected n3">
             <tr class="nav-entry selected n3 _0">
              <td class="nav-number selected n3"><a href="#"><span class="section-number">10</span><span class="nav-space"></span></a></td>
              <td class="nav-title selected n3"><a href="#">Where is the monad?</a></td>
             </tr>
             <tr class="nav-subentries selected n3 _0">
              <td class="nav-subentries-number selected n3"></td>
              <td class="nav-subentries selected n3">
               <table class="nav n4">
                <tbody class="nav-before-open n4">
                 <tr class="nav-entry n4 _1">
                  <td class="nav-number n4">
                   <a href="#an-example-using-the-monadic-syntax"><span class="section-number">1</span><span class="nav-space"></span></a>
                  </td>
                  <td class="nav-title n4"><a href="#an-example-using-the-monadic-syntax">An example using the monadic syntax</a></td>
                 </tr>
                 <tr class="nav-entry n4 _2">
                  <td class="nav-number n4">
                   <a href="#how-the-monadic-syntax-works"><span class="section-number">2</span><span class="nav-space"></span></a>
                  </td>
                  <td class="nav-title n4"><a href="#how-the-monadic-syntax-works">How the monadic syntax works</a></td>
                 </tr>
                 <tr class="nav-entry n4 _3">
                  <td class="nav-number n4"><a href="#the-term-monad"><span class="section-number">3</span><span class="nav-space"></span></a></td>
                  <td class="nav-title n4"><a href="#the-term-monad">The term &#x201C;monad&#x201D;</a></td>
                 </tr>
                 <tr class="nav-entry n4 _4">
                  <td class="nav-number n4">
                   <a href="#why-the-monadic-syntax-is-slow"><span class="section-number">4</span><span class="nav-space"></span></a>
                  </td>
                  <td class="nav-title n4"><a href="#why-the-monadic-syntax-is-slow">Why the monadic syntax is slow</a></td>
                 </tr>
                </tbody>
               </table>
              </td>
             </tr>
            </tbody>
            <tbody class="nav-after-open n3">
             <tr class="nav-entry n3 _1">
              <td class="nav-number n3">
               <a href="debugging-a-parser.html"><span class="section-number">11</span><span class="nav-space"></span></a>
              </td>
              <td class="nav-title n3"><a href="debugging-a-parser.html">Debugging a parser</a></td>
             </tr>
             <tr class="nav-entry n3 _2">
              <td class="nav-number n3">
               <a href="performance-optimizations.html"><span class="section-number">12</span><span class="nav-space"></span></a>
              </td>
              <td class="nav-title n3"><a href="performance-optimizations.html">Performance optimizations</a></td>
             </tr>
             <tr class="nav-entry n3 _3">
              <td class="nav-number n3"><a href="tips-and-tricks.html"><span class="section-number">13</span><span class="nav-space"></span></a></td>
              <td class="nav-title n3"><a href="tips-and-tricks.html">Tips and tricks</a></td>
             </tr>
            </tbody>
           </table>
          </td>
         </tr>
        </tbody>
        <tbody class="nav-after-open n2">
         <tr class="nav-entry n2 _6">
          <td class="nav-number n2"><a href="../reference/index.html"><span class="section-number">6</span><span class="nav-space"></span></a></td>
          <td class="nav-title n2"><a href="../reference/index.html">Reference</a></td>
         </tr>
        </tbody>
       </table>
      </td>
     </tr>
    </tbody>
   </table>
  </div>
  <div id="copyright">
    <span>Copyright © 2012 <a href="../about/contact.html">Stephan Tolksdorf</a></span>
  </div>
 </div>
 </div>
 </div>
 <div id="wrapper">
 <div id="main">
 <div id="main-content">
 <div id="breadcrumbs">
  <span class="breadcrumbs">
   <span id="breadcrumbs-parents"><a href="../index.html">FParsec Documentation</a><span class="breadcrumbs-sep"> > </span><a href="index.html">User’s Guide</a></span><span class="breadcrumbs-sep"> > </span>Where is the monad?
  </span>
 </div>
 <div class="section s2">
  <h1 class="title h2"><span><span class="section-number">5.10</span> Where is the monad?</span></h1>
  <div class="intro i2">
   <div class="para _1">
    <p>
     If you have previously used Haskell’s Parsec library or an early version of FParsec you’re probably wondering by now where the &#x201C;monadic
     syntax&#x201D; has gone. There’s also a chance that you’ve stumbled upon FParsec while searching for a &#x201C;monadic parser library&#x201D; for
     F#/.Net and you’re now wondering whether FParsec actually is one.
    </p>
   </div>
   <div class="para _2">
    <p>
     To answer these questions right away: FParsec supports a monadic parser construction syntax, but this syntax is only an optional feature, not the
     foundation of the library design. FParsec doesn’t use the monadic syntax internally and we no longer recommend using it for new parser projects
     when performance is a concern.
    </p>
   </div>
  </div>
  <div id="an-example-using-the-monadic-syntax" class="section s3">
   <h2 class="title h3"><span><span class="section-number">5.10.1</span> An example using the monadic syntax</span></h2>
   <div class="intro i3">
    <div class="para _1">
     <p>With the monadic syntax you can, for example, write a parser for a pair of floating‐point numbers as follows:</p>
    </div>
    <div class="para _2 lcinp">
<pre class="code fsharp"><span class="ck">open</span> <span class="ci">FParsec</span>

<span class="ck">let</span> <span class="ci">ws</span> <span class="cp">=</span> <a href="../reference/charparsers.html#members.spaces"><span class="ci">spaces</span></a> <span class="clc"><span class="cld">//</span> whitespace parser</span>

<span class="ck">let</span> <span class="ci">str_ws</span> <span class="ci">str</span> <span class="cp">=</span> <a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="ck">do!</span> <span class="ci">skipString</span> <span class="ci">str</span>
                        <span class="ck">do!</span> <span class="ci">ws</span>
                        <span class="ck">return</span> <span class="cp">()</span><span class="cp">}</span>

<span class="ck">let</span> <span class="ci">number_ws</span> <span class="cp">=</span> <a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="ck">let!</span> <span class="ci">number</span> <span class="cp">=</span> <a href="../reference/charparsers.html#members.pfloat"><span class="ci">pfloat</span></a>
                       <span class="ck">do!</span> <span class="ci">ws</span>
                       <span class="ck">return</span> <span class="ci">number</span><span class="cp">}</span>

<span class="ck">let</span> <span class="ci">pairOfNumbers</span> <span class="cp">=</span> <a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="ck">do!</span> <span class="ci">str_ws</span> <span class="cs"><span class="cld">"</span>(<span class="crd">"</span></span>
                           <span class="ck">let!</span> <span class="ci">number1</span> <span class="cp">=</span> <span class="ci">number_ws</span>
                           <span class="ck">let!</span> <span class="ci">number2</span> <span class="cp">=</span> <span class="ci">number_ws</span>
                           <span class="ck">do!</span> <span class="ci">str_ws</span> <span class="cs"><span class="cld">"</span>)<span class="crd">"</span></span>
                           <span class="ck">return</span> <span class="cp">(</span><span class="ci">number1</span><span class="cp">,</span> <span class="ci">number2</span><span class="cp">)</span><span class="cp">}</span>
</pre>
    </div>
    <div class="para _3">
     <p>
      We’ll explain how the F# compiler handles the <code class="fsharp"><a href="../reference/primitives.html#members.parse"><span
      class="ci">parse</span></a> <span class="cp">{</span><span class="co">...</span><span class="cp">}</span></code> expressions in the next
      section. For now, just compare the previous implementation with the following one using the usual FParsec combinators:
     </p>
    </div>
    <div class="para _4 lcinp">
<pre class="code fsharp"><span class="ck">open</span> <span class="ci">FParsec</span>

<span class="ck">let</span> <span class="ci">ws</span> <span class="cp">=</span> <a href="../reference/charparsers.html#members.spaces"><span class="ci">spaces</span></a> <span class="clc"><span class="cld">//</span> whitespace parser</span>

<span class="ck">let</span> <span class="ci">str_ws</span> <span class="ci">str</span> <span class="cp">=</span> <span class="ci">skipString</span> <span class="ci">str</span> <a href="../reference/primitives.html#members.:62::62:.."><span class="co">&gt;&gt;.</span></a> <span class="ci">ws</span>

<span class="ck">let</span> <span class="ci">number_ws</span> <span class="cp">=</span> <a href="../reference/charparsers.html#members.pfloat"><span class="ci">pfloat</span></a> <a href="../reference/primitives.html#members...:62::62:"><span class="co">.&gt;&gt;</span></a> <span class="ci">ws</span>

<span class="ck">let</span> <span class="ci">pairOfNumbers</span> <span class="cp">=</span> <a href="../reference/primitives.html#members.between"><span class="ci">between</span></a> <span class="cp">(</span><span class="ci">str_ws</span> <span class="cs"><span class="cld">"</span>(<span class="crd">"</span></span><span class="cp">)</span> <span class="cp">(</span><span class="ci">str_ws</span> <span class="cs"><span class="cld">"</span>)<span class="crd">"</span></span><span class="cp">)</span>
                            <span class="cp">(</span><a href="../reference/primitives.html#members.tuple2"><span class="ci">tuple2</span></a> <span class="ci">number1</span> <span class="ci">number2</span><span class="cp">)</span>
</pre>
    </div>
    <div class="para _5">
     <p>
      The latter implementation is obviously more concise, but – at least for users without prior exposure to FParsec – the first implementation is
      probably a bit more intuitive and self‐explanatory. What makes the first implementation so intuitive is that the syntax of the <code
      class="fsharp"><a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span
      class="co">...</span><span class="cp">}</span></code> expressions is a) very close to what developers are used to from their normal work with F#
      and b) expressive enough that it obviates the need for many of FParsec’s basic combinators. Unfortunately, the intuitiveness of the monadic
      syntax comes at the price of a large performance penalty.
     </p>
    </div>
   </div>
  </div>
  <div id="how-the-monadic-syntax-works" class="section s3">
   <h2 class="title h3"><span><span class="section-number">5.10.2</span> How the monadic syntax works</span></h2>
   <div class="intro i3">
    <div class="para _1">
     <p>
      To explain how the monadic syntax works, we need to take a look at how the F# compiler translates the <code class="fsharp"><a
      href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="co">...</span><span
      class="cp">}</span></code> expressions.
     </p>
    </div>
    <div class="para _2 lcinp">
     <p>
      The foundation for the monadic syntax is the <code class="fsharp"><a href="../reference/primitives.html#members.:62::62::61:"><span
      class="co">&gt;&gt;=</span></a></code> combinator introduced in <a href="applying-parsers-in-sequence.html#the-combinator">section 5.4.5</a>:
     </p>
<pre class="code fsharp"><span class="ck">val</span> <span class="cp">(</span><a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a><span class="cp">)</span><span class="cp">:</span> <a href="../reference/primitives.html#members.Parser"><span class="ci">Parser</span></a><span class="cp">&lt;</span><span class="ctv">'a</span><span class="cp">,</span><span class="ctv">'u</span><span class="cp">&gt;</span> <span class="cr">-&gt;</span> <span class="cp">(</span><span class="ctv">'a</span> <span class="cr">-&gt;</span> <a href="../reference/primitives.html#members.Parser"><span class="ci">Parser</span></a><span class="cp">&lt;</span><span class="ctv">'b</span><span class="cp">,</span><span class="ctv">'u</span><span class="cp">&gt;</span><span class="cp">)</span> <span class="cr">-&gt;</span> <a href="../reference/primitives.html#members.Parser"><span class="ci">Parser</span></a><span class="cp">&lt;</span><span class="ctv">'b</span><span class="cp">&gt;</span></pre>
    </div>
    <div class="para _3">
     <p>
      This operator takes a parser and a function returning a parser as arguments. The combined parser <code class="fsharp"><span
      class="ci">p</span> <a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a> <span
      class="ci">f</span></code> first applies the parser <code class="fsharp"><span class="ci">p</span></code> to the input, then it applies the
      function <code class="fsharp"><span class="ci">f</span></code> to the result returned by <code class="fsharp"><span class="ci">p</span></code>
      and finally it applies the parser returned by <code class="fsharp"><span class="ci">f</span></code> to the input. As we exlained in <a
      href="applying-parsers-in-sequence.html#the-combinator">section 5.4.5</a>, this way to combine parsers is powerful enough that we can express
      many other sequencing combinators in terms of <code class="fsharp"><a href="../reference/primitives.html#members.:62::62::61:"><span
      class="co">&gt;&gt;=</span></a></code> and <code class="fsharp"><a href="../reference/primitives.html#members.preturn"><span
      class="ci">preturn</span></a></code>.
     </p>
    </div>
    <div class="para _4">
     <p>
      For example, we could implement the <code class="fsharp"><a href="../reference/primitives.html#members.pipe3"><span
      class="ci">pipe3</span></a></code> combinator for sequentially applying three parsers as follows:
     </p>
    </div>
    <div class="para _5 lcinp">
<pre class="code fsharp"><span class="ck">let</span> <a href="../reference/primitives.html#members.pipe3"><span class="ci">pipe3</span></a> <span class="ci">p1</span> <span class="ci">p2</span> <span class="ci">p3</span> <span class="ci">f</span> <span class="cp">=</span>
    <span class="ci">p1</span> <a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a> <span class="ck">fun</span> <span class="ci">x1</span> <span class="cr">-&gt;</span>
             <span class="ci">p2</span> <a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a> <span class="ck">fun</span> <span class="ci">x2</span> <span class="cr">-&gt;</span>
                      <span class="ci">p3</span> <a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a> <span class="ck">fun</span> <span class="ci">x3</span> <span class="cr">-&gt;</span>
                               <a href="../reference/primitives.html#members.preturn"><span class="ci">preturn</span></a> <span class="cp">(</span><span class="ci">f</span> <span class="ci">x1</span> <span class="ci">x2</span> <span class="ci">x3</span><span class="cp">)</span>
</pre>
    </div>
    <div class="para _6">
     <p>
      Directly using the <code class="fsharp"><a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a></code>
      and <code class="fsharp"><a href="../reference/primitives.html#members.preturn"><span class="ci">preturn</span></a></code> combinators obviously
      leads to somewhat unwieldy and unreadable expressions. Fortunately, F#’s <a
      href="http://msdn.microsoft.com/en-us/library/dd233182.aspx">computation expressions</a> allow us to rewrite this expression in a more intuitive
      way:
     </p>
    </div>
    <div class="para _7 lcinp">
<pre class="code fsharp"><span class="ck">let</span> <a href="../reference/primitives.html#members.pipe3"><span class="ci">pipe3</span></a> <span class="ci">p1</span> <span class="ci">p2</span> <span class="ci">p3</span> <span class="ci">f</span> <span class="cp">=</span>
    <a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="ck">let!</span> <span class="ci">x1</span> <span class="cp">=</span> <span class="ci">p1</span>
           <span class="ck">let!</span> <span class="ci">x2</span> <span class="cp">=</span> <span class="ci">p2</span>
           <span class="ck">let!</span> <span class="ci">x3</span> <span class="cp">=</span> <span class="ci">p3</span>
           <span class="ck">return</span> <span class="ci">f</span> <span class="ci">x1</span> <span class="ci">x2</span> <span class="ci">x3</span><span class="cp">}</span>
</pre>
    </div>
    <div class="para _8">
     <p>
      The <code class="fsharp"><a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a></code> object that we reference
      in this and other code snippets of this chapter is a so‐called &#x201C;builder&#x201D; object for computation expressions. It is defined in
      FParsec’s <code class="fsharp"><a href="../reference/primitives.html"><span class="ci">Primitives</span></a></code> module. Using the methods of
      this object, the F# compiler translates the computation expression in the curly braces to the following equivalent expression:
     </p>
    </div>
    <div class="para _9 lcinp">
<pre class="code fsharp"><span class="ck">let</span> <a href="../reference/primitives.html#members.pipe3"><span class="ci">pipe3</span></a> <span class="ci">p1</span> <span class="ci">p2</span> <span class="ci">p3</span> <span class="ci">f</span> <span class="cp">=</span>
    <a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a><span class="cm">.</span><span class="ci">Delay</span><span class="cp">(</span><span class="ck">fun</span> <span class="cp">()</span> <span class="cr">-&gt;</span>
      <a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a><span class="cm">.</span><span class="ci">Bind</span><span class="cp">(</span><span class="ci">p1</span><span class="cp">,</span> <span class="ck">fun</span> <span class="ci">x1</span> <span class="cr">-&gt;</span>
        <a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a><span class="cm">.</span><span class="ci">Bind</span><span class="cp">(</span><span class="ci">p2</span><span class="cp">,</span> <span class="ck">fun</span> <span class="ci">x2</span> <span class="cr">-&gt;</span>
          <a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a><span class="cm">.</span><span class="ci">Bind</span><span class="cp">(</span><span class="ci">p3</span><span class="cp">,</span> <span class="ck">fun</span> <span class="ci">x3</span> <span class="cr">-&gt;</span>
            <a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a><span class="cm">.</span><span class="ci">Return</span><span class="cp">(</span><span class="ci">f</span> <span class="cp">(</span><span class="ci">x1</span> <span class="ci">x2</span> <span class="ci">x3</span><span class="cp">)</span><span class="cp">)</span><span class="cp">)</span><span class="cp">)</span><span class="cp">)</span><span class="cp">)</span>
</pre>
    </div>
    <div class="para _0">
     <p>
      When we replace the <code class="fsharp"><a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a></code> object
      method calls with the respective method bodies, we will see that this definition is equivalent to our original definition using <code
      class="fsharp"><a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a></code> and <code
      class="fsharp"><a href="../reference/primitives.html#members.preturn"><span class="ci">preturn</span></a></code>.
     </p>
    </div>
    <div class="para _1 lcinp">
     <p>
      The <code class="fsharp"><span class="ci">Bind</span></code>, <code class="fsharp"><span class="ci">Return</span></code> and <code
      class="fsharp"><span class="ci">Delay</span></code> methods of the <code class="fsharp"><a
      href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a></code> object are defined as:
     </p>
<pre class="code fsharp">    <span class="ck">member</span> <span class="ci">t</span><span class="cm">.</span><span class="ci">Bind</span><span class="cp">(</span><span class="ci">p</span><span class="cp">,</span> <span class="ci">f</span><span class="cp">)</span> <span class="cp">=</span> <span class="ci">p</span> <a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a> <span class="ci">f</span>
    <span class="ck">member</span> <span class="ci">t</span><span class="cm">.</span><span class="ci">Return</span><span class="cp">(</span><span class="ci">x</span><span class="cp">)</span> <span class="cp">=</span> <a href="../reference/primitives.html#members.preturn"><span class="ci">preturn</span></a> <span class="ci">x</span>
    <span class="ck">member</span> <span class="ci">t</span><span class="cm">.</span><span class="ci">Delay</span><span class="cp">(</span><span class="ci">f</span><span class="cp">:</span><span class="cp">(</span><span class="ci">unit</span> <span class="cr">-&gt;</span> <a href="../reference/primitives.html#members.Parser"><span class="ci">Parser</span></a><span class="cp">&lt;</span><span class="ctv">'a</span><span class="cp">,</span><span class="ctv">'u</span><span class="cp">&gt;</span><span class="cp">)</span><span class="cp">)</span> <span class="cp">=</span> <span class="ck">fun</span> <span class="ci">stream</span> <span class="cr">-&gt;</span> <span class="cp">(</span><span class="ci">f</span> <span class="cp">()</span><span class="cp">)</span> <span class="ci">stream</span>
</pre>
    </div>
    <div class="para _2">
     <p>
      Substituting these method bodies into the previous expression yields an expression that is very similar to the original one (except for the
      additional indirection introduced by the <code class="fsharp"><span class="ci">Delay</span></code> method<sup class="fn-mark"><a
      id="how-the-monadic-syntax-works.:FN:1:B:" href="#how-the-monadic-syntax-works.:FN:1">[1]</a></sup>):
     </p>
    </div>
    <div class="para _3 lcinp">
<pre class="code fsharp"><span class="ck">let</span> <a href="../reference/primitives.html#members.pipe3"><span class="ci">pipe3</span></a> <span class="ci">p1</span> <span class="ci">p2</span> <span class="ci">p3</span> <span class="ci">f</span> <span class="cp">=</span>
    <span class="ck">fun</span> <span class="ci">stream</span> <span class="cr">-&gt;</span>
      <span class="cp">(</span><span class="ci">p1</span> <a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a> <span class="ck">fun</span> <span class="ci">x1</span> <span class="cr">-&gt;</span>
                <span class="ci">p2</span> <a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a> <span class="ck">fun</span> <span class="ci">x2</span> <span class="cr">-&gt;</span>
                         <span class="ci">p3</span> <a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a> <span class="ck">fun</span> <span class="ci">x3</span> <span class="cr">-&gt;</span>
                                  <a href="../reference/primitives.html#members.preturn"><span class="ci">preturn</span></a> <span class="cp">(</span><span class="ci">f</span> <span class="ci">x1</span> <span class="ci">x2</span> <span class="ci">x3</span><span class="cp">)</span><span class="cp">)</span> <span class="ci">stream</span>
</pre>
    </div>
    <div class="para _4">
     <p>
      In summary, the <code class="fsharp"><a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span
      class="cp">{</span><span class="co">...</span><span class="cp">}</span></code> syntax is syntactic sugar for defining parsers with the <code
      class="fsharp"><a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a></code> operator. The
      expressiveness of this syntax stems from the power of the <code class="fsharp"><a href="../reference/primitives.html#members.:62::62::61:"><span
      class="co">&gt;&gt;=</span></a></code> operator.
     </p>
    </div>
   </div>
  </div>
  <div id="the-term-monad" class="section s3">
   <h2 class="title h3"><span><span class="section-number">5.10.3</span> The term &#x201C;monad&#x201D;</span></h2>
   <div class="intro i3">
    <div class="para _1">
     <p>
      A function with a signature like the one of the <code class="fsharp"><a href="../reference/primitives.html#members.:62::62::61:"><span
      class="co">&gt;&gt;=</span></a></code> operator is often called &#x201C;bind&#x201D;. The above examples make it obvious why: the <code
      class="fsharp"><a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a></code> combinator binds the
      result of the parser on the left‐hand side to the function argument on the right‐hand side.
     </p>
    </div>
    <div class="para _2">
     <p>
      The <code class="fsharp"><a href="../reference/primitives.html#members.Parser"><span class="ci">Parser</span></a></code> type together with the
      <code class="fsharp"><a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a></code> and <code
      class="fsharp"><a href="../reference/primitives.html#members.preturn"><span class="ci">preturn</span></a></code> operations constitute a <a
      href="http://en.wikipedia.org/wiki/Monad_%28functional_programming%29">monad</a>, which is an abstraction in type theory that denotes this kind
      of combination of a generic type with associated bind and return operations.
     </p>
    </div>
    <div class="para _3">
     <p>
      Discussing the theoretical background of monads would be outside the scope of this user’s guide. For our purposes it is enough to note that the
      monad abstraction is so useful for certain applications that F# comes with built‐in syntax support for monadic expressions. FParsec utilizes
      this language feature (<a href="http://msdn.microsoft.com/en-us/library/dd233182.aspx">computation expressions</a>) to enable <code
      class="fsharp"><a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span
      class="co">...</span><span class="cp">}</span></code> expressions.
     </p>
    </div>
    <div class="para _4">
     <p>
      Be assured that you don’t need to know anything about monads in general in order to use FParsec’s <code class="fsharp"><a
      href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="co">...</span><span
      class="cp">}</span></code> expressions. To fully understand this feature all you need to know to is how the F# compiler translates <code
      class="fsharp"><a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span
      class="co">...</span><span class="cp">}</span></code> expressions into normal code.
     </p>
    </div>
    <div class="para _5">
     <p>
      Besides <code class="fsharp"><span class="ck">let!</span></code>, <code class="fsharp"><span class="ck">do!</span></code> and <code
      class="fsharp"><span class="ck">return</span></code> there are some more language constructs that are supported inside <code class="fsharp"><a
      href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="co">...</span><span
      class="cp">}</span></code> expressions. Please refer to the <a href="../reference/primitives.html#members.parse">reference documentation</a> for
      more information.
     </p>
    </div>
   </div>
  </div>
  <div id="why-the-monadic-syntax-is-slow" class="section s3">
   <h2 class="title h3"><span><span class="section-number">5.10.4</span> Why the monadic syntax is slow</span></h2>
   <div class="intro i3">
    <div class="para _1">
     <p>
      Compared to parsers implemented with only the usual FParsec operators and functions, parsers implemented with <code class="fsharp"><a
      href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="co">...</span><span
      class="cp">}</span></code> expressions can be up to several times slower.
     </p>
    </div>
    <div class="para _2">
     <p>
      The relatively bad performance can be directly attributed to the way <code class="fsharp"><a
      href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="co">...</span><span
      class="cp">}</span></code> expressions are compiled. As you have seen above, a <code class="fsharp"><a
      href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="co">...</span><span
      class="cp">}</span></code> expression is simply translated into a series of nested closures that are chained through calls to the <code
      class="fsharp"><a href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a></code> operator. <em>With the
      current compiler technology and the current implementation of FParsec</em> this introduces some significant overhead.
     </p>
    </div>
    <div class="para _3 lcinp">
     <p>
      <em>Every time</em> a <code class="fsharp"><a href="../reference/primitives.html#members.Parser"><span class="ci">Parser</span></a></code>
      function constructed with the <code class="fsharp"><a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span
      class="cp">{</span><span class="co">...</span><span class="cp">}</span></code> syntax is called:
     </p>
     <ul class="l1">
      <li class="_1">
       Two function closures get newly instantiated for each invocation of the <code class="fsharp"><a
       href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a></code> operator: the closure that is passed as
       the second argument to <code class="fsharp"><a href="../reference/primitives.html#members.:62::62::61:"><span
       class="co">&gt;&gt;=</span></a></code> and the closure that is returned by <code class="fsharp"><a
       href="../reference/primitives.html#members.:62::62::61:"><span class="co">&gt;&gt;=</span></a></code>.
      </li>
      <li class="_2">
       Any parser created inside a <code class="fsharp"><a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span
       class="cp">{</span><span class="co">...</span><span class="cp">}</span></code> expression gets (re‐)created every time execution reaches that
       point in the expression.
      </li>
     </ul>
    </div>
    <div class="para _4">
     <p>
      In principle, you can avoid the overhead described in the second point by moving the construction of parser functions out of the <code
      class="fsharp"><a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span
      class="co">...</span><span class="cp">}</span></code> expression.
     </p>
    </div>
    <div class="para _5 lcinp">
     <p>For example, you can avoid the repeated construction of the <code class="fsharp"><span class="ci">skipString</span></code> parsers in</p>
<pre class="code fsharp"><span class="ck">let</span> <span class="ci">numberInParens</span> <span class="cp">=</span> <a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="ck">do!</span> <span class="ci">skipString</span> <span class="cs"><span class="cld">"</span>(<span class="crd">"</span></span>
                            <span class="ck">let!</span> <span class="ci">number</span> <span class="cp">=</span> <a href="../reference/charparsers.html#members.pfloat"><span class="ci">pfloat</span></a>
                            <span class="ck">do!</span> <span class="ci">skipString</span> <span class="cs"><span class="cld">"</span>)<span class="crd">"</span></span>
                            <span class="ck">return</span> <span class="ci">number</span><span class="cp">}</span>
</pre>
     <p>by rewriting the code as</p>
<pre class="code fsharp"><span class="ck">let</span> <span class="ci">parenOpen</span> <span class="cp">=</span> <span class="ci">skipString</span> <span class="cs"><span class="cld">"</span>(<span class="crd">"</span></span>
<span class="ck">let</span> <span class="ci">parenClose</span> <span class="cp">=</span> <span class="ci">skipString</span> <span class="cs"><span class="cld">"</span>)<span class="crd">"</span></span>
<span class="ck">let</span> <span class="ci">numberInParens</span> <span class="cp">=</span> <a href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="ck">do!</span> <span class="ci">parenOpen</span>
                            <span class="ck">let!</span> <span class="ci">number</span> <span class="cp">=</span> <a href="../reference/charparsers.html#members.pfloat"><span class="ci">pfloat</span></a>
                            <span class="ck">do!</span> <span class="ci">parenClose</span>
                            <span class="ck">return</span> <span class="ci">number</span><span class="cp">}</span>
</pre>
    </div>
    <div class="para _6">
     <p>
      However, if you wanted to factor out any parser construction from a <code class="fsharp"><a
      href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="co">...</span><span
      class="cp">}</span></code> expression, you’d also have to factor out any use of parser combinators, which would take away a lot from the
      attractiveness of the syntax.
     </p>
    </div>
    <div class="para _7">
     <p>
      If performance is not that important for your application, you can just ignore that a parser like <code class="fsharp"><span
      class="ci">skipString</span> <span class="cs"><span class="cld">"</span>(<span class="crd">"</span></span></code> is repeatedly constructed,
      since its construction is relatively cheap. But if you do the same for parsers based on <code class="fsharp"><a
      href="../reference/charparsers.html#members.regex"><span class="ci">regex</span></a></code> or <code class="fsharp"><a
      href="../reference/charparsers.html#members.anyOf"><span class="ci">anyOf</span></a></code>, where the construction potentially involves some
      relatively expensive compilation or runtime code generation, you might be surprised just how slow your parsers can become.
     </p>
    </div>
    <div class="para _8">
     <p>
      Because of the described performance issues, we recommend not to use <code class="fsharp"><a
      href="../reference/primitives.html#members.parse"><span class="ci">parse</span></a> <span class="cp">{</span><span class="co">...</span><span
      class="cp">}</span></code> expressions and instead work with FParsec’s rich set of operators and other combinators. Not only does the
      operator‐based notation (which is used everywhere else in FParsec’s documentation) lead to faster parsers, it also allows for more concise
      parser code with a higher signal‐to‐noise ratio.
     </p>
    </div>
   </div>
  </div>
  <div class="fn-list">
   <div class="fn-title">Footnotes:</div>
   <table class="fn">
    <tr class="fn _1">
     <th class="fn _1"><a class="footnote-backlink" id="how-the-monadic-syntax-works.:FN:1" href="#how-the-monadic-syntax-works.:FN:1:B:">[1]</a></th>
     <td class="fn _2">
      The computation expression specification does not require a <code class="fsharp"><span class="ci">Delay</span></code> method. So, we could avoid
      the overhead associated with the additional indirection by removing the <code class="fsharp"><span class="ci">Delay</span></code> method from
      the <code class="fsharp"><a href="../reference/primitives.html#members.ParserCombinator"><span class="ci">ParserCombinator</span></a></code>
      class. However, this would make the behaviour of <code class="fsharp"><a href="../reference/primitives.html#members.parse"><span
      class="ci">parse</span></a></code> expressions somewhat counter‐intuitive, as the behaviour would differ from the behaviour of F#’s <code
      class="fsharp"><span class="ci">seq</span></code> and <code class="fsharp"><span class="ci">async</span></code> expressions.
     </td>
    </tr>
   </table>
  </div>
 </div>
 </div>
 </div>
 </div>
</body>
</html>
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.