-
Notifications
You must be signed in to change notification settings - Fork 1
/
srfi-171.html
611 lines (432 loc) · 25.8 KB
/
srfi-171.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
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<title>SRFI 171: Transducers</title>
<meta name="viewport" content="width=device-width, initial-scale=1" />
<link rel="stylesheet" href="/srfi.css" type="text/css" />
<link href="/favicon.png" rel="icon" sizes="192x192" type="image/png" />
</head>
<body>
<h1 id="title">Title</h1>
<p>Transducers</p>
<h1 id="author">Author</h1>
<p>Linus Björnstam <a href="mailto:bjornstam.linus@fastmail.se">bjornstam.linus@fastmail.se</a></p>
<h1 id="status">Status</h1>
<p>This SRFI is currently in <em>final</em> status. Here is <a href="https://srfi.schemers.org/srfi-process.html">an explanation</a> of each status that a SRFI can hold. To provide input on this SRFI, please send email to <code><a href="mailto:srfi+minus+171+at+srfi+dotschemers+dot+org">srfi-171@<span class="antispam">nospam</span>srfi.schemers.org</a></code>. To subscribe to the list, follow <a href="https://srfi.schemers.org/srfi-list-subscribe.html">these instructions</a>. You can access previous messages via the mailing list <a href="https://srfi-email.schemers.org/srfi-171">archive</a>.</p>
<ul>
<li>Received: 2019-06-14</li>
<li>Draft #1 published: 2019-06-24</li>
<li>Draft #2 published: 2019-07-25</li>
<li>Draft #3 published: 2019-10-04</li>
<li>Finalized: 2019-10-26</li>
</ul>
<h1 id="abstract">Abstract</h1>
<p>A library implementing transducers — composable algorithmic
transformations. Scheme has many different ways of expressing
transformations over different collection types, but they are all
unique to whatever base type they work on. This SRFI proposes a new
construct, the transducer, that is oblivious to the context in which
it is being used.</p>
<h1 id="rationale">Rationale</h1>
<p>Some of the most common operations used in the Scheme language are
those transforming lists: <code>map</code>, <code>filter</code>,
<code>take</code> and so on. They work well, are well understood,
and are used daily by most Scheme programmers. They are however not
general because they only work on lists, and they do not compose
very well since combining <code>N</code> of them builds <code>(- N
1)</code> intermediate lists.</p>
<p>Transducers are oblivious to what kind of process they are used in,
and are composable without building intermediate collections. This
means we can create a transducer that squares all odd numbers:
<code>(compose (tfilter odd?) (tmap (lambda (x) (* x x))))</code>
and reuse it with lists, vectors, or in just about any context where
data flows in one direction. We could use it as a processing step
for asynchronous channels, with an event framework as a
pre-processing step, or even in lazy contexts where you pass a lazy
collection and a transducer to a function and get a new lazy
collection back.</p>
<p>The traditional Scheme approach of having collection-specific
procedures is not changed. We instead specify a general form of
transformations that complement these procedures. The benefits are
obvious: We get a clear, well-understood way of describing common
transformations in a way that is faster than just chaining the
collection-specific counterparts. Even for slower Schemes where the
overhead of transducers is big, the effects on garbage collection
times are often dramatic, making transducers very attractive.</p>
<h2 id="dependencies">Dependencies</h2>
<p>The sample implementation of transducers depends on the following:</p>
<ul>
<li>SRFI 9, <code>define-record-type</code> (included in R<sup>7</sup>RS
small)</li>
<li>SRFI-69 (hash-tables)</li>
<li>Proper compose procedure (included if it is not available)</li>
<li>A <code>vector->list</code> that behaves like in SRFI 43
(included in R<sup>7</sup>RS small).</li></ul>
<h2 id="portability">Portability</h2>
<p>The sample implementation is easily portable to any
R<sup>5</sup>RS/R<sup>6</sup>RS/R<sup>7</sup>RS-compatible Scheme. The non-standard things are:</p>
<ul>
<li>a <code>vector->list</code> that takes start and end
arguments</li>
<li>A hash-table implementation with support for arbitrary equality
predicates</li>
<li><code>case-lambda</code>, preferably efficiently
implemented</li></ul>
<h1 id="general-discussion">General discussion</h1>
<h2 id="concept-reducers">Concept: Reducers</h2>
<p>The central part of transducers are 3-arity reducing functions.</p>
<ul>
<li><code>()</code>: Produce an identity</li>
<li><code>(</code><em>result-so-far</em><code>)</code>: completion.
If you have nothing to do, then just return the result so far</li>
<li><code>(</code><em>result-so-far input</em><code>)</code> do
whatever you like to the input and produce a new
<em>result-so-far</em></li>
</ul>
<p>In the case of a summing <code>+</code> reducer, the reducer would
produce, in arity order: <code>0</code>, <em>result-so-far</em>,
(<code>+</code> <em>result-so-far input</em>). This happens to be
exactly what the regular <code>+</code> does.</p>
<h2 id="concept-transducers">Concept: Transducers</h2>
<p>A transducer is a one-arity function that takes a reducer and produces a
reducing function that behaves as follows:</p>
<ul>
<li><code>()</code>: calls <em>reducer</em> with no arguments
(producing its identity)</li>
<li><code>(</code><em>result-so-far</em><code>)</code>: Maybe
transform the <em>result-so-far</em> and call <em>reducer</em>
with it.</li>
<li><code>(</code><em>result-so-far input</em><code>)</code> Maybe
do something to <em>input</em> and maybe call the reducer with
<em>result-so-far</em> and the maybe-transformed
<em>input</em>.</li></ul>
<p> A simple example is as following: <code>(list-transduce (tfilter
odd?) + '(1 2 3 4 5))</code>. This first returns a transducer
filtering all odd elements, then it runs <code>+</code> without
arguments to retrieve its identity. It then starts the transduction
by passing + to the transducer returned by <code>(tfilter
odd?)</code> which returns a reducing function. It works not unlike
<code>reduce</code> from SRFI 1, but also checks whether one of the
intermediate transducers returns a "reduced" value
(implemented as a SRFI 9 record), which means the reduction finished
early.</p>
<p>Because transducers compose and the final reduction is only
executed in the last step, composed transducers will not build any
intermediate result or collections. Although the normal way of
thinking about application of composed functions is right to left,
due to how the transduction is built it is applied left to
right. <code>(compose (tfilter odd?) (tmap sqrt))</code> will
create a transducer that first filters out any odd values and then
computes the square root of the rest.</p>
<h2 id="state">State</h2>
<p> Even though transducers appear to be somewhat of a generalisation
of <code>map</code> and friends, this is not really true. Since
transducers don't know in which context they are being used, some
transducers must keep state where their collection-specific
counterparts do not. This SRFI requires some transducers to be
stateless (as is stated in the documentation of each transducer),
but many are allowed to keep state. How state is kept is not
specified. The sample implementation uses mutable values in
closures, which is efficient and portable, but has all the problems
of hidden mutable state.</p>
<h2 id="naming">Naming</h2>
<p>Transducers and procedures that return transducers all have names
starting with t. Reducing functions that are supposed to be used at
the end of a transduction all start with r. Some reducers are just
straight-up reducers, whereas others, like <code>rany</code> and
<code>revery</code>, are procedures that return reducers.</p>
<h2 id="scope-considerations">Scope considerations</h2>
<p>The procedures specified here are only for the collections defined
in R<sup>7</sup>RS small. They could easily be extended to support
R<sup>7</sup>RS large red docket, but specifying that would require
conforming implementations to also support a substantial part of the
red docket. I therefore leave transduce unspecified for many data
types. It is however encouraged to add [datatype]-transduce for
whatever types your Scheme supports. Adding support for the
collections of the R<sup>7</sup>RS red docket (sets, hash-tables,
ilists, rlists, ideque, texts, lseqs, streams and list-queues) is
trivial.</p>
<h2 id="lazy-eager">Eager or lazy semantics</h2>
<p> There is some overlap in the use case of transducers and lazy constructs
like generators or streams. One big benefit is that you can compose
transformations without building unnecessary intermediate state. There
are, however, differences. Laziness is usually described as having "pull"
semantics, i.e: you pull values through a pipeline of lazy constructs,
transforming and filtering them on the way. This way you get only what
you need.
</p>
<p> Transducers, being oblivious to context, are neither eager nor lazy, but are
generally meant for eager contexts. The transduce form is always eager, and
any general lazy application of transducers is outside the scope of this SRFI.
</p>
<h1 id="specification">Specification</h1>
<h2 id="applying-transducers">Applying transducers</h2>
<h3 id="list-transduce">list-transduce</h3>
<p><code>(list-transduce</code> <em>xform f lst</em><code>)</code>
<br />
<code>(list-transduce</code> <em>xform f identity lst</em><code>)</code></p>
<p> Initializes the transducer <em>xform</em> by passing the reducer <em>f</em>
to it. If no identity is provided, <em>f</em> is run without
arguments to return the reducer identity. It then reduces over
<em>lst</em> using the identity as the seed.</p>
<p> If one of the transducers finishes early (such as <code>ttake</code> or <code>tdrop</code>),
it communicates this by returning a reduced value, which in the
sample implementation is just a value wrapped in a SRFI 9 record
type named "reduced". If such a value is returned by the
transducer, <code>list-transduce</code> must stop execution and
return an unreduced value immediately.</p>
<h3 id="vector-transduce">vector-transduce</h3>
<p><code>(vector-transduce</code> <em>xform f vec</em><code>)</code>
<br />
<code>(vector-transduce</code> <em>xform f identity vec</em><code>)</code></p>
<p>Same as <code>list-transduce</code>, but reduces over a vector instead of a list.</p>
<h3 id="string-transduce">string-transduce</h3>
<p><code>(string-transduce</code> <em>xform f str</em><code>)</code>
<br />
<code>(string-transduce</code> <em>xform f identity str</em><code>)</code></p>
<p>Same as <code>list-transduce</code>, but for strings.</p>
<h3 id="bytevector-u8-transduce">bytevector-u8-transduce</h3>
<p><code>(bytevector-u8-transduce</code> <em>xform f bvec</em><code>)</code>
<br />
<code>(bytevector-u8-transduce</code> <em>xform f identity bvec</em><code>)</code></p>
<p>Same as <code>list-transduce</code>, but for u8-bytevectors.</p>
<h3 id="port-transduce">port-transduce</h3>
<p><code>(port-transduce</code> <em>xform f reader</em><code>)</code>
<br />
<code>(port-transduce</code> <em>xform f reader port</em><code>)</code>
<br />
<code>(port-transduce</code> <em>xform f init reader port</em><code>)</code></p>
<p> If <em>port</em> is provided, it applies <code>(xform f)</code> to every value
produced by <code>(reader port)</code> until the EOF object is returned.
If <em>port</em> is not provided, it calls <em>reader</em> without arguments until
the EOF object is returned.
</p>
<p><code>(port-transduce (tfilter odd?) rcons read (open-input-string "1 2 3 4"))</code>
=> (1 3)</p>
<h3 id="generator-transduce">generator-transduce</h3>
<p><code>(generator-transduce</code> <em>xform f gen</em><code>)</code>
<br />
<code>(generator-transduce</code> <em>xform f init gen</em><code>)</code></p>
<p> Same as <code>list-transduce</code>, but for srfi-158-styled generators.</p>
<h2 id="reducers">Reducers</h2>
<h3 id="rcons"><code>rcons</code></h3>
<p>a simple consing reducer. When called without values, it returns
its identity, '(). With one value, which will be a list, it
reverses the list. When called with two values, it conses the
second value to the first.</p>
<p><code>(list-transduce (tmap (lambda (x) (+ x 1)) rcons (list 0 1 2 3))</code> => <code>(1 2 3 4)</code></p>
<h3 id="reverse-rcons"><code>reverse-rcons</code></h3>
<p>same as <code>rcons</code>, but leaves the values in their reversed order.</p>
<p><code>(list-transduce (tmap (lambda (x) (+ x 1))) reverse-rcons (list 0 1 2 3))</code> => <code>(4 3 2
1)</code></p>
<h3 id="rany-pred"><code>(rany</code> <em>pred?</em><code>)</code></h3>
<p>The reducer version of <code>any</code>. Returns <code>(reduced
(pred? value))</code> if any <code>(pred? value)</code> returns
non-<code>#f</code>. The identity is <code>#f</code>.</p>
<p><code>(list-transduce (tmap (lambda (x) (+ x 1))) (rany odd?) (list 1 3 5))</code>
=> <code>#f</code>
<br />
<br />
<code>(list-transduce (tmap (lambda (x) (+ x 1))) (rany odd?) (list 1 3
4 5))</code> => <code>#t</code></p>
<h3 id="revery-pred"><code>(revery</code> <em>pred?</em><code>)</code></h3>
<p>The reducer version of <code>every</code>. Stops the transduction
and returns <code>(reduced #f)</code> if any <code>(pred?
value)</code> returns <code>#f</code>. If every <code>(pred?
value)</code> returns true, it returns the result of the last
invocation of <code>(pred? value)</code>. The identity is
<code>#t</code>.</p>
<p><pre>(list-transduce
(tmap (lambda (x) (+ x 1)))
(revery (lambda (v) (if (odd? v) v #f)))
(list 2 4 6))</pre> => <code>7</code>
<br />
<br />
<code>(list-transduce (tmap (lambda (x) (+ x 1)) (revery odd?) (list 2 4 5 6))</code> => <code>#f</code></p>
<h3 id="rcount"><code>rcount</code></h3>
<p>A simple counting reducer. Counts the values that pass through the
transduction.</p>
<p><code>(list-transduce (tfilter odd?) rcount (list 1 2 3 4))</code> => <code>2.</code></p>
<h2 id="transducers">Transducers</h2>
<h3 id="tmap-proc"><code>(tmap</code> <em>proc</em><code>)</code></h3>
<p>Returns a transducer that applies <em>proc</em> to all values. Must be
stateless.</p>
<h3 id="tfilter-pred"><code>(tfilter</code> <em>pred?</em><code>)</code></h3>
<p>Returns a transducer that removes values for which <em>pred?</em> returns
<code>#f</code>. Must be stateless.</p>
<h3 id="tremove-pred"><code>(tremove</code> <em>pred?</em><code>)</code></h3>
<p>Returns a transducer that removes values for which <em>pred?</em> returns
non-<code>#f</code>. Must be stateless.</p>
<h3 id="tfilter-map-proc"><code>(tfilter-map</code> <em>proc</em><code>)</code></h3>
<p>The same as <code>(compose (tmap proc) (tfilter values))</code>.
Must be stateless.</p>
<h3 id="treplace-mapping"><code>(treplace</code> <em>mapping</em><code>)</code></h3>
<p>The argument <em>mapping</em> is an association list (using <code>equal?</code>
to compare keys), a hash-table, a one-argument procedure taking
one argument and either producing that same argument or a
replacement value, or another implementation-defined mapping
object.</p>
<p>Returns a transducer which checks for the presence of any value passed through it in
<em>mapping</em>. If a mapping is found, the value of that mapping is
returned, otherwise it just returns the original value.</p>
<p>Must not keep any internal state. Modifying the mapping while it's
in use by <code>treplace</code> is an error.</p>
<h3 id="tdrop-n"><code>(tdrop</code> <em>n</em><code>)</code></h3>
<p>Returns a transducer that discards the first <em>n</em> values.</p>
<p>Stateful.</p>
<h3 id="ttake-n"><code>(ttake</code> <em>n</em><code>)</code></h3>
<p>Returns a transducer that discards all values and stops the
transduction after the first <em>n</em> values have been let through. Any
subsequent values are ignored.</p>
<p>Stateful.</p>
<h3 id="tdrop-while-pred"><code>(tdrop-while</code> <em>pred?</em><code>)</code></h3>
<p>Returns a transducer that discards the first values for which
<em>pred?</em> returns true.</p>
<p>Stateful.</p>
<h3 id="ttake-while-pred"><code>(ttake-while</code> <em>pred?</em> <em>[retf]</em><code>)</code></h3>
<p>Returns a transducer that stops the transduction after <em>pred?</em>
has returned <code>#f</code>. Any subsequent values are ignored and
the last successful value is returned. <code>retf</code> is a function that gets called whenever
<em>pred?</em> returns false. The arguments passed are the result so far and the input for which
<em>pred?</em> returns <code>#f</code>. The default function is
<code>(lambda (result input) result)</code></p>
<p>Stateful.</p>
<h3 id="tconcatenate"><code>tconcatenate</code></h3>
<p><code>tconcatenate</code> <strong>is</strong> a transducer that
concatenates the content of each value (that must be a list) into
the reduction.</p>
<p><code>(list-transduce tconcatenate rcons '((1 2) (3 4 5) (6 (7 8) 9)))</code>
=>
<code>(1 2 3 4 5 6 (7 8) 9)</code></p>
<h3 id="tappend-map-proc"><code>(tappend-map</code> <em>proc</em><code>)</code></h3>
<p>The same as <code>(compose (tmap proc) tconcatenate)</code>.</p>
<h3 id="tflatten"><code>tflatten</code></h3>
<p><code>tflatten</code> <strong>is</strong> a transducer that flattens an input
consisting of lists.</p>
<p><code>(list-transduce tflatten rcons '((1 2) 3 (4 (5 6) 7 8) 9)</code> =>
<code>(1 2 3 4 5 6 7 8 9)</code></p>
<h3 id="tdelete-neighbor-duplicates"><code>(tdelete-neighbor-duplicates <em>[equality-predicate]</em>)</code></h3>
<p>Returns a transducer that removes any directly following duplicate
elements. The default <em>equality-predicate</em> is <code>equal?</code>.</p>
<p>Stateful.</p>
<h3 id="tremove-duplicates"><code>(tdelete-duplicates <em>[equality-predicate]</em>)</code></h3>
<p>Returns a transducer that removes any subsequent duplicate elements compared using
<em>equality-predicate</em>. If the underlying data structure used for detecting duplicates
can't handle arbitrary equality predicates, it should at least support
<code>eq?</code>, <code>eqv?</code> and <code>equal?</code>. The default <em>equality-predicate</em>
is <code>equal?</code>.</p>
<p>Stateful.</p>
<h3 id="tsegment"><code>(tsegment</code> <em>n</em><code>)</code></h3>
<p>Returns a transducer that groups <em>n</em> inputs in lists of
<em>n</em> elements. When the transduction stops, it flushes any
remaining collection, even if it contains fewer than <em>n</em>
elements.</p>
<p>Stateful.</p>
<h3 id="tpartition-pred"><code>(tpartition</code> <em>pred?</em><code>)</code></h3>
<p>Returns a transducer that groups inputs in lists by whenever
<code>(</code><em>pred? input</em><code>)</code> changes value.</p>
<p>Stateful.</p>
<h3 id="tadd-between-value"><code>(tadd-between </code> <em>value</em><code>)</code></h3>
<p>Returns a transducer which interposes <em>value</em> between each
value and the next. This does not compose gracefully with
transducers like <code>ttake</code>, as you might end up ending the
transduction on <em>value</em>.</p>
<p>Stateful.</p>
<h3 id="tenumerate-start"><code>(tenumerate</code> <em>[start]</em><code>)</code></h3>
<p> Returns a transducer that indexes values passed through it,
starting at <em>start</em>, which defaults to 0. The indexing is done
through <code>cons</code> pairs like <code>(</code><em>index</em>
<code>.</code> <em>input</em><code>)</code>.</p>
<p> <code>(list-transduce (tenumerate 1) rcons (list 'first 'second 'third))</code> =>
<code> ((1 . first) (2 . second) (3 . third))</code></p>
<p>Stateful.</p>
<h3 id="tlog-logger"><code>(tlog</code> <em>[logger]</em><code>)</code></h3>
<p>Returns a transducer that can be used to log or print values and
results. The result of the logger procedure is discarded. The
default logger is <code>(lambda (result input) (write input) (newline))</code>.</p>
<h2 id="helpers">Helper functions for writing transducers</h2>
<p>These functions are in the <code>(srfi 171 meta)</code> module and are only usable
when you want to write your own transducers. </p>
<h3 id="reduced"><code>(reduced</code> <em>value</em><code>)</code></h3>
<p> Wraps a value in a <code><reduced></code> container, signalling that the
reduction should stop.</p>
<h3 id="reducedp"><code>(reduced?</code> <em>value</em><code>)</code></h3>
<p> Returns <code>#t</code> if <em>value</em> is <code>reduced</code>.</p>
<h3 id="unreduce"><code>(unreduce</code> <em>reduced-container</em><code>)</code></h3>
<p> Returns the value in <em>reduced-container</em>.</p>
<h3 id="ensure-reduced"><code>(ensure-reduced</code> <em>value</em><code>)</code></h3>
<p> Wraps <em>value</em> in a reduced container if it is not already reduced.</p>
<h3 id="preserving-reduced"><code>(preserving-reduced</code> <em>reducer</em><code>)</code></h3>
<p> Wraps <em>reducer</em> in another reducer that encapsulates any
returned reduced value in another reduced container. This is useful
in places where you re-use a reducer with
<em>[collection]-reduce</em>. If the reducer returns a reduced
value, <em>[collection]-reduce</em> unwraps it. Unless handled, this
leads to the reduction continuing. </p>
<h3 id="list-reduce"><code>(list-reduce</code> <em>f identity lst</em><code>)</code></h3>
<p> The reducing function used internally by <code>list-transduce</code>. <em>f</em> is reducer
as returned by a transducer. <em>identity</em> is the identity (sometimes called "seed") of
the reduction. <em>lst</em> is a list. If the <em>f</em> returns a reduced value, the reduction
stops immediately and the unreduced value is returned.</p>
<h3 id="vector-reduce"><code>(vector-reduce</code> <em> f identity vec</em><code>)</code></h3>
<p> The vector version of <code>list-reduce</code>.</p>
<h3 id="string-reduce"><code>(string-reduce</code> <em> f identity str</em><code>)</code></h3>
<p> The string version of <code>list-reduce</code>.</p>
<h3 id="bytevector-u8-reduce"><code>(bytevector-u8-reduce</code> <em> f identity bv</em><code>)</code></h3>
<p> The bytevector-u8 version of <code>list-reduce</code>.</p>
<h3 id="port-reduce"><code>(port-reduce</code> <em> f identity reader port</em><code>)</code></h3>
<p> The port version of <code>list-reduce</code>. It reduces over <em>port</em> using
<em>reader</em> until <em>reader</em> returns the EOF object.</p>
<h3 id="generator-reduce"><code>(generator-reduce</code> <em> f identity gen</em><code>)</code></h3>
<p> The generator version of <code>list-reduce</code>. It reduces over <em>gen</em> until it returns
the EOF object</p>
<h1 id="sample-implementation">Sample implementation</h1>
<p> The sample implementation is written in Guile, but should be
straightforward to port since it uses no Guile-specific features
apart from Guile's hash-table implementation. It is written for
clarity over speed, but should be plenty fast anyway.
The low-hanging fruit for optimization is to replace the composed
transducers (such as <code>tappend-map</code> and <code>tfilter-map</code>)
with non-composed implementations.</p>
<p> Another optimization would be to return whether or not a reducer
can return a reduced value, thus allowing <em>[collection]-reduce</em> to
avoid checking for reduced values, however this would break compatibility
with the sample implementation.</p>
<h1 id="acknowledgements">Acknowledgements</h1>
<p> First of all, this would not have been done without Rich Hickey, who
introduced transducers into Clojure. His talks were important for me
to grasp the basics of transducers. Then I would like to thank large
parts of the Clojure community for also struggling with
understanding transducers. The amount of material produced
explaining them in general, and Clojure's implementation
specifically, has been instrumental in letting me make this a
clean-room implementation.</p>
<p> In the same vein, I would like to direct a thank-you to Juanpe Bolivar, who
implemented pure transducers for C++ (in the Atria library) and did a
wonderful presentation about them.</p>
<p> I would also like to thank John Cowan, Duy Nguyen and Lassi Kortela for
their input during the SRFI process. </p>
<p>Lastly I would like to thank Arthur Gleckler, who showed interest in
my implementation of transducers and convinced me to make this SRFI.</p>
<h1 id="copyright">Copyright</h1>
<p> Copyright (C) Linus Björnstam (2019).</p>
<p> Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation files
(the “Software”), to deal in the Software without restriction,
including without limitation the rights to use, copy, modify, merge,
publish, distribute, sublicense, and/or sell copies of the Software,
and to permit persons to whom the Software is furnished to do so,
subject to the following conditions:</p>
<p> The above copyright notice and this permission notice (including
the next paragraph) shall be included in all copies or substantial
portions of the Software.</p>
<p> THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.</p>
<hr> <address>Editor: <a href="mailto:srfi-editors+at+srfi+dot+schemers+dot+org">Arthur A. Gleckler</a></address></body></html>