Debian Codegraph @

src/Pipes/Parse/Tutorial.hs

raw
1 {-# OPTIONS_GHC -fno-warn-unused-imports #-}
2
3 {-| @pipes-parse@ builds upon @pipes@ to add several missing features necessary
4 to implement 'Parser's:
5
6 * End-of-input detection, so that 'Parser's can react to an exhausted input
7 stream
8
9 * Leftovers support, which simplifies several parsing problems
10
11 * Connect-and-resume, to connect a 'Producer' to a 'Parser' and retrieve
12 unused input
13 -}
14
15 module Pipes.Parse.Tutorial (
16 -- * Overview
17 -- $overview
18
19 -- * Parsers
20 -- $parsers
21
22 -- * Lenses
23 -- $lenses
24
25 -- * Getters
26 -- $getters
27
28 -- * Building Lenses
29 -- $buildlenses
30
31 -- * Conclusion
32 -- $conclusion
33 ) where
34
35 import Pipes
36 import Pipes.Parse
37
38 {- $overview
39 @pipes-parse@ centers on three abstractions:
40
41 * 'Producer's, unchanged from @pipes@
42
43 * 'Parser's, which play a role analogous to 'Consumer's
44
45 * 'Lens.Family2.Lens''es between 'Producer's, which play a role analogous to
46 'Pipe's
47
48 There are four ways to connect these three abstractions:
49
50 * Connect 'Parser's to 'Producer's using 'runStateT' \/ 'evalStateT' \/
51 'execStateT':
52
53 > runStateT :: Parser a m r -> Producer a m x -> m (r, Producer a m x)
54 > evalStateT :: Parser a m r -> Producer a m x -> m r
55 > execStateT :: Parser a m r -> Producer a m x -> m ( Producer a m x)
56
57
58 * Connect 'Lens.Family2.Lens''es to 'Parser's using
59 'Lens.Family.State.Strict.zoom'
60
61 > zoom :: Lens' (Producer a m x) (Producer b m y)
62 > -> Parser b m r
63 > -> Parser a m r
64
65 * Connect 'Producer's to 'Lens.Family2.Lens''es using ('Lens.Family.^.') or
66 'Lens.Family.view':
67
68 > (^.) :: Producer a m x
69 > -> Lens' (Producer a m x) (Producer b m y)
70 > -> Producer b m y
71
72 * Connect 'Lens.Family2.Lens''es to 'Lens.Family2.Lens''es using ('.') (i.e.
73 function composition):
74
75 > (.) :: Lens' (Producer a m x) (Producer b m y)
76 > -> Lens' (Producer b m y) (Producer c m z)
77 > -> Lens' (Producer a m x) (Producer c m z)
78
79 You can obtain the necessary lens utilities from either:
80
81 * The @lens-family-core@ library, importing @Lens.Family@ (for
82 ('Lens.Family.^.') \/ 'Lens.Family.view' and 'Lens.Family.over') and
83 @Lens.Family.State.Strict@ (for 'Lens.Family.State.Strict.zoom'), or:
84
85 * The @lens@ library, importing @Control.Lens@ (for ('Control.Lens.^.') \/
86 'Control.Lens.view', 'Control.Lens.over' and 'Control.Lens.zoom')
87
88 This tutorial uses @Lens.Family@ since it has fewer dependencies and simpler
89 types.
90 -}
91
92 {- $parsers
93 'Parser's handle end-of-input and pushback by storing a 'Producer' in a
94 'StateT' layer:
95
96 > type Parser a m r = forall x . StateT (Producer a m x) m r
97
98 To draw a single element from the underlying 'Producer', use the 'draw'
99 command:
100
101 > draw :: Monad m => Parser a m (Maybe a)
102
103 'draw' returns the next element from the 'Producer' wrapped in 'Just' or
104 returns 'Nothing' if the underlying 'Producer' is empty. Here's an example
105 'Parser' written using 'draw' that retrieves the first two elements from a
106 stream:
107
108 > import Pipes.Parse
109 >
110 > drawTwo :: Monad m => Parser a m (Maybe a, Maybe a)
111 > drawTwo = do
112 > mx <- draw
113 > my <- draw
114 > return (mx, my)
115 >
116 > -- or: drawTwo = liftM2 (,) draw draw
117
118 Since a 'Parser' is just a 'StateT' action, you run a 'Parser' using the
119 same run functions as 'StateT':
120
121 > -- Feed a 'Producer' to a 'Parser', returning the result and leftovers
122 > runStateT :: Parser a m r -> Producer a m x -> m (r, Producer a m x)
123 >
124 > -- Feed a 'Producer' to a 'Parser', returning only the result
125 > evalStateT :: Parser a m r -> Producer a m x -> m r
126 >
127 > -- Feed a 'Producer' to a 'Parser', returning only the leftovers
128 > execStateT :: Parser a m r -> Producer a m x -> m ( Producer a m x)
129
130 All three of these functions require a 'Producer' which we feed to the
131 'Parser'. For example, we can feed standard input:
132
133 >>> evalStateT drawTwo Pipes.Prelude.stdinLn
134 Pink<Enter>
135 Elephants<Enter>
136 (Just "Pink",Just "Elephants")
137
138 The result is wrapped in a 'Maybe' because 'draw' can fail if the 'Producer'
139 is empty:
140
141 >>> evalStateT drawTwo (yield 0)
142 (Just 0,Nothing)
143
144 Parsing might not necessarily consume the entire stream. We can use
145 'runStateT' or 'execStateT' to retrieve unused elements that our parser does
146 not consume:
147
148 >>> import Pipes
149 >>> (result, unused) <- runStateT drawTwo (each [1..4])
150 >>> -- View the parsed result
151 >>> result
152 (Just 1,Just 2)
153 >>> -- Now print the leftovers
154 >>> runEffect $ for unused (lift . print)
155 3
156 4
157
158 -}
159
160 {- $lenses
161 @pipes-parse@ also provides a convenience function for testing purposes that
162 draws all remaining elements and returns them as a list:
163
164 > drawAll :: Monad m => Parser a m [a]
165
166 For example:
167
168 >>> import Pipes
169 >>> import Pipes.Parse
170 >>> evalStateT drawAll (each [1..10])
171 [1,2,3,4,5,6,7,8,9,10]
172
173 However, this function is not recommended in general because it loads the
174 entire input into memory, which defeats the purpose of streaming parsing.
175
176 You can instead use 'foldAll' if you wish to fold all input elements into a
177 single result:
178
179 >>> evalStateT (foldAll (+) 0 id) (each [1..10])
180 55
181
182 You can also use the @foldl@ package to simplify writing more complex folds:
183
184 >>> import Control.Applicative
185 >>> import Control.Foldl as L
186 >>> evalStateT (purely foldAll (liftA2 (,) L.sum L.maximum)) (each [1..10])
187 (55,Just 10)
188
189 But what if you wanted to draw or fold just the first three elements from
190 an infinite stream instead of the entire input? This is what lenses are
191 for:
192
193 > import Lens.Family
194 > import Lens.Family.State.Strict
195 > import Pipes
196 > import Pipes.Parse
197 >
198 > import Prelude hiding (splitAt, span)
199 >
200 > drawThree :: Monad m => Parser a m [a]
201 > drawThree = zoom (splitAt 3) drawAll
202
203 'Lens.Family.State.Strict.zoom' lets you delimit a 'Parser' using a
204 'Lens.Family2.Lens''. The above code says to limit 'drawAll' to a subset of
205 the input, in this case the first three elements:
206
207 >>> evalStateT drawThree (each [1..])
208 [1,2,3]
209
210 'splitAt' is a 'Lens.Family2.Lens'' with the following type:
211
212 > splitAt
213 > :: Monad m
214 > => Int -> Lens' (Producer a m x) (Producer a m (Producer a m x))
215
216 The easiest way to understand 'splitAt' is to study what happens when you
217 use it as a getter:
218
219 > view (splitAt 3) :: Producer a m x -> Producer a m (Producer a m x)
220
221 In this context, @(splitAt 3)@ behaves like 'splitAt' from the Prelude,
222 except instead of splitting a list it splits a 'Producer'. Here's an
223 example of how you can use 'splitAt':
224
225 > outer :: Monad m => Producer Int m (Producer Int m ())
226 > outer = each [1..6] ^. splitAt 3
227
228 The above definition of @outer@ is exactly equivalent to:
229
230 > outer = do
231 > each [1..3]
232 > return (each [4..6])
233
234 We can prove this by successively running the outer and inner 'Producer'
235 layers:
236
237 >>> -- Print all the elements in the outer layer and return the inner layer
238 >>> inner <- runEffect $ for outer (lift . print)
239 1
240 2
241 3
242 >>> -- Now print the elements in the inner layer
243 >>> runEffect $ for inner (lift . print)
244 4
245 5
246 6
247
248 We can also use lenses to modify 'Parser's, using
249 'Lens.Family.State.Strict.zoom'. When we combine
250 'Lens.Family.State.Strict.zoom' with @(splitAt 3)@ we limit a parser to the
251 the first three elements of the stream. When the parser is done
252 'Lens.Family.State.Strict.zoom' also returns unused elements back to the
253 original stream. We can demonstrate this using the following example
254 parser:
255
256 > splitExample :: Monad m => Parser a m ([a], Maybe a, [a])
257 > splitExample = do
258 > x <- zoom (splitAt 3) drawAll
259 > y <- zoom (splitAt 3) draw
260 > z <- zoom (splitAt 3) drawAll
261 > return (x, y, z)
262
263 The second parser begins where the first parser left off:
264
265 >>> evalStateT splitExample (each [1..])
266 ([1,2,3],Just 4,[5,6,7])
267
268 'span' behaves the same way, except that it uses a predicate and takes as
269 many consecutive elements as possible that satisfy the predicate:
270
271 > spanExample :: Monad m => Parser Int m (Maybe Int, [Int], Maybe Int)
272 > spanExample = do
273 > x <- zoom (span (>= 4)) draw
274 > y <- zoom (span (< 4)) drawAll
275 > z <- zoom (span (>= 4)) draw
276 > return (x, y, z)
277
278 Note that even if the first parser fails, subsequent parsers can still
279 succeed because they operate under a different lens:
280
281 >>> evalStateT spanExample (each [1..])
282 (Nothing,[1,2,3],Just 4)
283
284 You can even nest 'Lens.Family.State.Strict.zoom's, too:
285
286 > nestExample :: Monad m => Parser Int m (Maybe Int, [Int], Maybe Int)
287 > nestExample = zoom (splitAt 2) spanExample
288
289 All the parsers from @spanExample@ now only see a subset of the input,
290 namely the first two elements:
291
292 >>> evalStateT nestExample (each [1..])
293 (Nothing,[1,2],Nothing)
294
295 -}
296
297 {- $getters
298 Not all transformations are reversible. For example, consider the following
299 contrived function:
300
301 > import Pipes
302 > import qualified Pipes.Prelude as P
303 >
304 > map' :: Monad m => (a -> b) -> Producer a m r -> Producer b m r
305 > map' f p = p >-> P.map f
306
307 Given a function of type @(a -> b)@, we can transform a stream of @a@'s into
308 a stream of @b@'s, but not the other way around. Transformations which are
309 not reversible and cannot be modeled as 'Pipe's can only be modeled as
310 functions between 'Producer's. However, 'Pipe's are preferable to functions
311 between 'Producer's when possible because 'Pipe's can transform both
312 'Producer's and 'Consumer's.
313
314 If you prefer, you can use lens-like syntax for functions between
315 'Producer's by promoting them to @Getter@s using 'Lens.Family.to':
316
317 > import Lens.Family
318 >
319 > example :: Monad m => Producer Int m ()
320 > example = each [1..3] ^. to (map' (*2))
321
322 However, a function of 'Producer's (or the equivalent @Getter@) cannot be
323 used transform 'Parser's (using 'Lens.Family.State.Strict.zoom' or
324 otherwise) . This reflects the fact that such a transformation cannot be
325 applied in reversed.
326 -}
327
328 {- $buildlenses
329 Lenses are very easy to write if you are willing to depend on either the
330 @lens-family@ or @lens@ library. Both of these libraries provide an
331 'Lens.Family2.Unchecked.iso' function that you can use to assemble your own
332 lenses. You only need two functions which reversibly transform back and
333 forth between a stream of @a@s and a stream of @b@s:
334
335 > -- "Forward"
336 > fw :: Producer a m x -> Producer b m y
337 >
338 > -- "Backward"
339 > bw :: Producer b m y -> Producer a m x
340
341 ... such that:
342
343 > fw . bw = id
344 >
345 > bw . fw = id
346
347 You can then convert them to a 'Lens.Family2.Lens'' using
348 'Lens.Family2.Unchecked.iso':
349
350 > import Lens.Family2 (Lens')
351 > import Lens.Family2.Unchecked (iso)
352 >
353 > lens :: Lens' (Producer a m x) (Producer b m y)
354 > lens = iso fw bw
355
356 You can even do this without incurring any dependencies if you rewrite the
357 above code like this:
358
359 > -- This type synonym requires the 'RankNTypes' extension
360 > type Lens' a b = forall f . Functor f => (b -> f b) -> (a -> f a)
361 >
362 > lens :: Lens' (Producer a m x) (Producer b m y)
363 > lens k p = fmap bw (k (fw p))
364
365 This is what @pipes-parse@ does internally, and you will find several
366 examples of this pattern in the source code of the "Pipes.Parse" module.
367
368 Lenses defined using either approach will work with both the @lens@ and
369 @lens-family@ libraries.
370
371 You can even use `Parser`s to build a function between `Producer`s. For
372 example, a very common idiom is to define a function of type:
373
374 > example :: Monad m => Producer a m r -> Producer b m (Producer a m r)
375
376 ... which parses as many @\'b\'@s as possible from the input stream of
377 @\'a\'@s, returning the remainder of the stream if parsing fails.
378
379 You can define that in terms of a parser of type:
380
381 > parser :: Monad m => StateT (Producer a m x) (Producer b m) r
382 >
383 > example = execStateT parser
384
385 However, writing a parser of that type requires a few changes for
386 everything to type-check. For example, the `draw` function does not have
387 the correct type for the above @parser@:
388
389 > draw :: StateT (Producer a m x) m (Maybe a)
390
391 ... but @(hoist lift draw)@ does have the correct type, where `Pipes.hoist`
392 comes from the @mmorph@ library and is re-exported by @pipes@:
393
394 > hoist lift draw :: StateT (Producer a m x) (Producer b m) (Maybe a)
395
396 Similarly, `yield` does not have the right type when you want to emit an
397 element of type @\'b\'@:
398
399 > yield :: Monad m => b -> Producer b m ()
400
401 ... but @(lift . yield)@ does have the right type:
402
403 > lift . yield :: Monad m => b -> StateT (Producer a m x) (Producer b m) ()
404
405 -}
406
407 {- $conclusion
408 @pipes-parse@ introduces core idioms for @pipes@-based parsing. These
409 idioms reuse 'Producer's, but introduce two new abstractions:
410 'Lens.Family2.Lens''es and 'Parser's.
411
412 This library is very minimal and only contains datatype-agnostic parsing
413 utilities, so this tutorial does not explore the full range of parsing
414 tricks using lenses. For example, you can also use lenses to change the
415 element type.
416
417 Several downstream libraries provide more specific functionality, including:
418
419 * @pipes-binary@: Lenses and parsers for @binary@ values
420
421 * @pipes-attoparsec@: Converts @attoparsec@ parsers to @pipes@ parsers
422
423 * @pipes-aeson@: Lenses and parsers for JSON values
424
425 * @pipes-bytestring@: Lenses and parsers for byte streams
426
427 * @pipes-text@: Lenses and parsers for text encodings
428
429 To learn more about @pipes-parse@, ask questions, or follow development, you
430 can subscribe to the @haskell-pipes@ mailing list at:
431
432 <https://groups.google.com/forum/#!forum/haskell-pipes>
433
434 ... or you can mail the list directly at:
435
436 <mailto:[email protected]>
437 -}