forked from scheme-requests-for-implementation/srfi-116
-
Notifications
You must be signed in to change notification settings - Fork 0
/
srfi-116-1.1.html
2403 lines (2092 loc) · 105 KB
/
srfi-116-1.1.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
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0//EN" "http://www.w3.org/TR/REC-html40/strict.dtd">
<html lang="en-US"><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"/>
<!-- This commented out text is for the brittle SRFI tools -->
<!--
</head>
<body>
<H1>Title</H1>
Immutable List Library
<H1>Author</H1>
John Cowan
<H1>Status</H1>
This SRFI is currently in ``draft'' status.
-->
<title>SRFI 116: Immutable List Library</title>
<!-- Should have a media=all to get, for example, printing to work.
== But my Netscape will completely ignore the tag if I do that.
-->
<style type="text/css">
/* A little general layout hackery for headers and the title. */
body { margin-left: +7%;
font-family: "Helvetica", sans-serif;
}
/* Netscape workaround: */
td, th { font-family: "Helvetica", sans-serif; }
code, pre { font-family: "courier new", "courier"; }
h1 { margin-left: -5%; }
h1, h2 { clear: both; }
h1, h2, h3, h4, h5, h6 { color: blue }
div.title-text { font-size: large; font-weight: bold; }
div.indent { margin-left: 2em; } /* General indentation */
pre.code-example { margin-left: 2em; } /* Indent code examples. */
/* This stuff is for definition lists of defined procedures.
** A proc-def2 is used when you want a stack of procs to go
** with one <dd> ... </dd> body. In this case, make the first
** proc a proc-def1, following ones proc-defi's, and the last one
** a proc-defn.
**
** Unfortunately, Netscape has huge bugs with respect to style
** sheets and dl list rendering. We have to set truly random
** values here to get the rendering to come out. The proper values
** are in the following style sheet, for Internet Explorer.
** In the following settings, the *comments* say what the
** setting *really* causes Netscape to do.
**
** Ugh. Professional coders sacrifice their self-respect,
** that others may live.
*/
/* m-t ignored; m-b sets top margin space. */
dt.proc-def1 { margin-top: 0ex; margin-bottom: 3ex; }
dt.proc-defi { margin-top: 0ex; margin-bottom: 0ex; }
dt.proc-defn { margin-top: 0ex; margin-bottom: 0ex; }
/* m-t works weird depending on whether or not the last line
** of the previous entry was a pre. Set to zero.
*/
dt.proc-def { margin-top: 0ex; margin-bottom: 3ex; }
/* m-b sets space between dd and dt; m-t ignored. */
dd.proc-def { margin-bottom: 0.5ex; margin-top: 0ex; }
/* Boldface the name of a procedure when it's being defined. */
code.proc-def { font-weight: bold; font-size: 110%}
/* For the index of procedures.
** Same hackery as for dt.proc-def, above.
*/
/* m-b sets space between dd and dt; m-t ignored. */
dd.proc-index { margin-bottom: 0ex; margin-top: 0ex; }
/* What the fuck? */
pre.proc-index { margin-top: -2ex; }
/* Pull the table of contents back flush with the margin.
** Both NS and IE screw this up in different ways.
*/
#toc-table { margin-top: -2ex; margin-left: -5%; }
/* Spread out bibliographic lists. */
/* More Netscape-specific lossage; see the following stylesheet
** for the proper values (used by IE).
*/
dt.biblio { margin-bottom: 1ex; }
/* Links to draft copies (e.g., not at the official SRFI site)
** are colored in red, so people will use them during the
** development process and kill them when the document's done.
*/
a.draft { color: red; }
</style>
<style type="text/css" media="all">
/* Nastiness: Here, I'm using a bug to work around a bug.
** Netscape rendering bugs mean you need bogus dt and dd
** margin settings — settings which screw up IE's proper rendering.
** Fortunately, Netscape has *another* bug: it will ignore this
** media=all style sheet. So I am placing the (proper) IE values
** here. Perhaps, one day, when these rendering bugs are fixed,
** this gross hackery can be removed.
*/
dt.proc-def1 { margin-top: 3ex; margin-bottom: 0ex; }
dt.proc-defi { margin-top: 0ex; margin-bottom: 0ex; }
dt.proc-defn { margin-top: 0ex; margin-bottom: 0.5ex; }
dt.proc-def { margin-top: 3ex; margin-bottom: 0.5ex; }
pre { margin-top: 1ex; }
dd.proc-def { margin-bottom: 2ex; margin-top: 0.5ex; }
/* For the index of procedures.
** Same hackery as for dt.proc-def, above.
*/
dd.proc-index { margin-top: 0ex; }
pre.proc-index { margin-top: 0ex; }
/* Spread out bibliographic lists. */
dt.biblio { margin-top: 3ex; margin-bottom: 0ex; }
dd.biblio { margin-bottom: 1ex; }
</style>
</head>
<body>
<!--========================================================================-->
<h1>Title</h1><div class="title-text">
Immutable List Library
</div>
<!--========================================================================-->
<h1>Author</h1>
John Cowan
<address>
<a href="http://www.ccil.org/~cowan">http://www.ccil.org/~cowan</a><br/>
<a href="mailto:[email protected]">[email protected]</a>
</address>
<!--========================================================================-->
<h1>Status</h1>
<p>
To see an explanation of
each status that a SRFI can hold, see <a
href="http://srfi.schemers.org/srfi-process.html">here</a>.
To provide input on this SRFI, please
<a href="mailto:srfi minus 116 at srfi dot schemers dot org">mail to
<code><srfi minus 116 at srfi dot schemers dot org></code></a>. See
<a href="../../srfi-list-subscribe.html">instructions here</a> to
subscribe to the list. You can access previous messages via
<a href="mail-archive/maillist.html">the archive of the mailing list</a>.
</p><ul>
<li>Received: <a href="http://srfi.schemers.org/srfi-116/srfi-116-1.1.html">2013/05/31</a></li>
</ul>
<!--========================================================================-->
<h1>Table of contents</h1>
<ul id="toc-table">
<li><a href="#Abstract">Abstract</a>
</li><li><a href="#Rationale">Rationale</a>
</li><li><a href="#ProcedureIndex">Procedure index</a>
</li><li><a href="#GeneralDiscussion">General discussion</a></li>
<ul>
<li><a href="#ImproperIlists">Improper ilists</a>
</li></ul>
<li><a href="#Quotation">Quotation</a></li>
<li><a href="#TheProcedures">The procedures</a>
<ul>
<li><a href="#Constructors">Constructors</a>
</li><li><a href="#Predicates">Predicates</a>
</li><li><a href="#Selectors">Selectors</a>
</li><li><a href="#Miscellaneous">Miscellaneous: length, append, reverse, zip & count</a>
</li><li><a href="#FoldUnfoldMap">Fold, unfold, and map</a>
</li><li><a href="#FilteringPartitioning">Filtering & partitioning</a>
</li><li><a href="#Searching">Searching</a>
</li><li><a href="#Deletion">Deletion</a>
</li><li><a href="#ImmutableassociationLists">Immutable association lists</a>
</li><li><a href="#Replacers">Replacers</a>
</li><li><a href="#Conversion">Conversion</a>
</li><li><a href="#ProcedureApplication">Procedure application</a>
</li><li><a href="#Comparators">Comparators</a>
</li></ul>
</li><li><a href="#SampleImplementation">Sample Implementation</a>
</li><li><a href="#Acknowledgements">Acknowledgements</a>
</li><li><a href="#ReferencesLinks">References & links</a>
</li><li><a href="#Copyright">Copyright</a>
</li></ul>
<!--========================================================================-->
<h1><a name="Abstract">Abstract</a></h1>
<p>
Scheme currently does not provide immutable pairs corresponding to its existing mutable pairs, although most uses of pairs do not exploit their mutability. The <a href="http://www.racket-lang.org">Racket</a> system takes the radical approach of making Scheme's pairs immutable, and providing a minimal library of mutable pairs with procedures named <code>mpair?, mcons, mcar, mcdr, set-mcar!, set-mcdr!</code>. This SRFI takes the opposite approach of leaving Scheme's pairs unchanged and providing a full set of routines for creating and dealing with immutable pairs. The sample implementation is portable (to systems with SRFI 9) and efficient.</p>
<h1><a name="Rationale">Rationale</a></h1>
<p>The first question about this library is why it should exist at all. Why not simply eliminate mutability from Scheme's ordinary pairs and use a version of SRFI-1 that treats the linear-update procedures (with <code>!</code>) as identical to their functional counterparts, as Racket does? The main answer is that this approach breaks R<sup>5</sup>RS and R<sup>7</sup>RS-small. All the data structures in these versions of Scheme are inherently mutable, and portable code is allowed to depend on that property.</p>
<p>R<sup>6</sup>RS segregates <code>set-car!</code> and <code>set-cdr!</code> into a separate library, thus allowing implementations to provide immutable Scheme pairs if this library is not (transitively) imported into a program, and mutable ones if it is. However, it is not possible to write portable R<sup>6</sup>RS programs that differentiate between mutable and immutable pairs, for example by using immutable pairs most of the time and mutable pairs where necessary.</p>
<p>Because of the Liskov Substitution Principle, it is not possible to treat mutable pairs as either a subtype or a supertype of mutable ones; they must be distinct, and if operations are to apply to both, they can do so only by <em>ad hoc</em> polymorphism of the kind that Scheme traditionally avoids for several reasons, including clarity, efficiency, and flexibility. This proposal, therefore, treats mutable and immutable pairs separately, while allowing easy conversion from one to the other.</p>
<p>
Rather than attempting to design this library from scratch, I have chosen the conservative option of modifying <a href="http://srfi.schemers.org/srfi-1/srfi-1.html">SRFI 1</a>. Consequently, most of the rationale given in that document applies to this one as well. I have made the following changes:</p>
<ul><li>Removed all linear-update procedures ending in <code>!</code></li>
<li>Removed all references to circular lists (there will be a future SRFI for immutable bidirectional cycles).</li>
<li>Removed the O(n<sup>2</sup>) lists-as-sets procedures (there will be a future SRFI supporting O(log n) immutable sets).</li>
<li>Inserted an <code>i</code> at a judicious place in each identifier, usually at the beginning. However, because "icons" means something else in both ordinary English and computer jargon, the basic constructor and its immediate relatives are named <code>ipair</code>, <code>xipair</code> and <code>ipair*</code> instead.</li>
<li>Added procedures for conversion between ordinary and immutable pairs, lists, and trees.</li>
<li>Added an analogue of <code>apply</code> for applying a procedure to an immutable list of arguments.</li>
<li>Added SRFI 114 comparators for immutable pairs, lists, and dotted lists.</li></ul>
<p>
Note: In the prose, immutable pairs and lists are known as ipairs and ilists throughout.
</p>
<!--========================================================================-->
<h1><a name="ProcedureIndex">Procedure Index</a></h1>
<p>
Here is a short list of the procedures provided by this SRFI. To interpret the examples, pretend that they are executed on a Scheme that prints immutable pairs and lists with the syntax of mutable ones. Although it may be reasonable for <code>display</code> to work this way, <code>write</code> should not.
</p><div class="indent">
<dl>
<dt class="proc-index"> Constructors
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#ipair">ipair</a> <a href="#ilist">ilist</a>
<a href="#xipair">xipair</a> <a href="#ipair*">ipair*</a> <a href="#make-ilist">make-ilist</a> <a href="#ilist-tabulate">ilist-tabulate</a>
<a href="#ilist-copy">ilist-copy</a> <a href="#iiota">iiota</a>
</pre>
</dd><dt class="proc-index"> Predicates
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#ipair-p">ipair?</a>
<a href="#proper-ilist-p">proper-ilist?</a>/<a href="#ilist-p">ilist?</a> <a href="#dotted-ilist-p">dotted-ilist?</a>
<a href="#not-ipair-p">not-ipair?</a> <a href="#null-ilist-p">null-ilist?</a>
<a href="#ilist=">ilist=</a>
</pre>
</dd><dt class="proc-index"> Selectors
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#icar">icar</a> <a href="#icdr">icdr</a> ... <a href="#icddadr">icddadr</a> <a href="#icddddr">icddddr</a> <a href="#ilist-ref">ilist-ref</a>
<a href="#ifirst">ifirst</a> <a href="#isecond">isecond</a> <a href="#ithird">ithird</a> <a href="#ifourth">ifourth</a> <a href="#ififth">ififth</a> <a href="#isixth">isixth</a> <a href="#iseventh">iseventh</a> <a href="#ieighth">ieighth</a> <a href="#ininth">ininth</a> <a href="#itenth">itenth</a>
<a href="#icar+icdr">icar+icdr</a>
<a href="#itake">itake</a> <a href="#idrop">idrop</a>/<a href="#ilist-tail">ilist-tail</a>
<a href="#itake-right">itake-right</a> <a href="#idrop-right">idrop-right</a>
<a href="#isplit-at">isplit-at</a>
<a href="#ilast">ilast</a> <a href="#last-ipair">last-ipair</a>
</pre>
</dd><dt class="proc-index"> Miscellaneous: length, append, concatenate, reverse, zip & count
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#ilength">ilength</a>
<a href="#iappend">iappend</a> <a href="#iconcatenate">iconcatenate</a> <a href="#ireverse">ireverse</a> <a href="#iappend-reverse">iappend-reverse</a>
<a href="#izip">izip</a> <a href="#iunzip1">iunzip1</a> <a href="#iunzip2">iunzip2</a> <a href="#iunzip3">iunzip3</a> <a href="#iunzip4">iunzip4</a> <a href="#iunzip5">iunzip5</a>
<a href="#icount">icount</a>
</pre>
</dd><dt class="proc-index"> Fold, unfold & map
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#imap">imap</a> <a href="#ifor-each">ifor-each</a>
<a href="#ifold">ifold</a> <a href="#iunfold">iunfold</a> <a href="#ipair-fold">ipair-fold</a> <a href="#ireduce">ireduce</a>
<a href="#ifold-right">ifold-right</a> <a href="#iunfold-right">iunfold-right</a> <a href="#ipair-fold-right">ipair-fold-right</a> <a href="#ireduce-right">ireduce-right</a>
<a href="#iappend-map">iappend-map</a>
<a href="#ipair-for-each">ipair-for-each</a> <a href="#ifilter-map">ifilter-map</a> <a href="#imap-in-order">imap-in-order</a>
</pre>
</dd><dt class="proc-index"> Filtering & partitioning
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#ifilter">ifilter</a> <a href="#ipartition">ipartition</a> <a href="#iremove">iremove</a>
</pre>
</dd><dt class="proc-index"> Searching
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#imember">imember</a> <a href="#imemq">imemq</a> <a href="#imemv">imemv</a>
<a href="#ifind">ifind</a> <a href="#ifind-tail">ifind-tail</a>
<a href="#iany">iany</a> <a href="#ievery">ievery</a>
<a href="#ilist-index">ilist-index</a>
<a href="#itake-while">itake-while</a> <a href="#idrop-while">idrop-while</a>
<a href="#ispan">ispan</a> <a href="#ibreak">ibreak</a>
</pre>
</dd><dt class="proc-index"> Deleting
</dt><dd class="proc-index">
<pre class="proc-inde x"><a href="#idelete">idelete</a> <a href="#idelete-duplicates">idelete-duplicates</a>
</pre>
</dd><dt class="proc-index"> Immutable association lists
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#iassoc">iassoc</a> <a href="#iassq">iassq</a> <a href="#iassv">iassv</a>
<a href="#ialist-cons">ialist-cons</a>
<a href="#ialist-delete">ialist-delete</a>
</pre>
</dd><dt class="proc-index"> Replacement
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#replace-icar">replace-icar</a> <a href="#replace-icdr">replace-icdr</a>
</pre>
</dd><dt class="proc-index"> Conversion
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#pair->ipair">pair->ipair</a> <a href="#ipair->pair">ipair->pair</a>
<a href="#list->ilist">list->ilist</a> <a href="#ilist->list">ilist->list</a>
<a href="#tree->itree">tree->itree</a> <a href="#itree->tree">itree->tree</a>
<a href="#gtree->itree">gtree->itree</a> <a href="#gtree->tree">gtree->tree</a>
</pre>
</dd><dt class="proc-index"> Procedure application
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#iapply">iapply</a>
</pre>
</dd><dt class="proc-index"> Comparators
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#ipair-comparator">ipair-comparator</a> <a href="#ilist-comparator">ilist-comparator</a>
<a href="#make-ilist-comparator">make-ilist-comparator</a> <a href="#make-improper-ilist-comparator">make-improper-ilist-comparator</a>
<a href="#make-icar-comparator">make-icar-comparator</a> <a href="#make-icdr-comparator">make-icdr-comparator</a>
</pre>
</dd></dl>
</div>
<!--========================================================================-->
<h1><a name="GeneralDiscussion">General discussion</a></h1>
<p>
A set of general criteria guided the design of the SRFI-1 library that underlies this library.
They are reproduced here.
</p><p>
List-filtering procedures such as <code>ifilter</code> or <code>idelete</code> do not disorder
lists. Elements appear in the answer list in the same order as they appear in
the argument list. This constrains implementation, but seems like a desirable
feature, since in many uses of lists, order matters. (In particular,
disordering an association list is definitely a bad idea.)
</p><p>
Contrariwise, although the sample implementations of the list-filtering
procedures share longest common tails between argument and answer lists,
it is not part of the spec.
</p><p>
Because ilists are an inherently sequential data structure (unlike, say,
vectors), inspection procedures such as <code>ifind</code>, <code>ifind-tail</code>, <code>ifor-each</code>, <code>iany</code>
and <code>ievery</code> commit to a left-to-right traversal order of their argument list.
</p><p>
However, constructors, such as <code><code>ilist-tabulate</code></code> and the mapping
procedures (<code>iappend-map</code>, <code>ipair-for-each</code>, <code>ifilter-map</code>,
<code>imap-in-order</code>), do <em>not</em> specify the dynamic order in which their procedural
argument is applied to its various values.
</p><p>
Predicates return useful true values wherever possible. Thus <code>iany</code> must return
the true value produced by its predicate, and <code>ievery</code> returns the final true
value produced by applying its predicate argument to the last element of its
argument list.
</p><p>
No special status is accorded Scheme's built-in equality predicate.
Any functionality provided in terms of <code>eq?</code>, <code>eqv?</code>, <code>equal?</code> is also
available using a client-provided equality predicate.
</p><p>
These procedures are <em>not</em> generic as between ordinary pairs/lists and immutable pairs/lists;
they are specific to immutable lists. Like Olin, I prefer to keep the library simple and focused.
However, there are a few conversions between mutable and immutable lists provided.
<!--========================================================================-->
</p>
<!--========================================================================-->
<h2><a name="ImproperIlists">Improper Lists</a></h2>
<p>
Scheme does not properly have a list type, just as C does not have a string
type. Rather, Scheme has a binary-tuple type, from which one can build binary
trees. There is an <em>interpretation</em> of Scheme values that allows one to
treat these trees as lists. The same interpretation is applied to immutable pairs.
</p><p>Because the empty list, written as <code>()</code>, is already immutable, it is shared between mutable and immutable lists as the termination marker. It is the only Scheme object that is both a mutable list and an immutable list.
</p><p>Users should note that dotted lists, whether mutable or immutable, are not commonly
used, and are considered by many Scheme programmers to be an ugly artifact of
Scheme's lack of a true list type.
Dotted ilists are <em>not</em> fully supported by this SRFI. Most procedures are
defined only on proper ilists — that is, <code>()</code>-terminated ilists. The
procedures that will also handle dotted ilists are specifically
marked. While this design decision restricts the domain of possible arguments
one can pass to these procedures, it has the benefit of allowing the
procedures to catch the error cases where programmers inadvertently pass
scalar values to an ilist procedure by accident,
<em>e.g.</em>, by switching the arguments to a procedure call.</p>
<h1><a name="Quotation">Quotation</a></h1>
<p>
The syntax keyword <code>iq</code> is analogous to <code>quote</code>.
It takes an arbitrary number of literals and constructs an ilist from them,
with any pairs in the literals converted to ipairs. It is useful
for providing constant ipair-based objects. Note that pairs within literal vectors will
not be converted. Unfortunately, there is no ilist analogue of <code>'</code>,
so we save keystrokes by using <code>iq</code> rather than <code>iquote</code>
and omitting the top-level parentheses.</p>
<!--========================================================================-->
<h1><a name="TheProcedures">The procedures</a></h1>
<p>
The templates given below obey the following conventions for procedure formals:
</p><table>
<tbody><tr valign="baseline"><th align="left"> <var>ilist</var>
</th><td> A proper (<code>()</code>-terminated) ilist
</td></tr><tr valign="baseline"><th align="left"> <var>dilist</var>
</th><td> A proper or dotted ilist
</td></tr><tr valign="baseline"><th align="left"> <var>ipair</var>
</th><td> An immutable pair
</td></tr><tr valign="baseline">
<th align="left"> <var>x</var>, <var>y</var>, <var>d</var>, <var>a</var>
</th><td> Any value
</td></tr><tr valign="baseline"><th align="left"> <var>object</var>, <var>value</var>
</th><td> Any value
</td></tr><tr valign="baseline"><th align="left"> <var>n</var>, <var>i</var>
</th><td> A natural number (an integer >= 0)
</td></tr><tr valign="baseline"><th align="left"> <var>proc</var>
</th><td> A procedure
</td></tr><tr valign="baseline"><th align="left"> <var>pred</var>
</th><td> A procedure whose return value is treated as a boolean
</td></tr><tr valign="baseline"><th align="left"> <var>=</var>
</th><td> A boolean procedure taking two arguments
</td></tr></tbody></table>
<p>
It is an error to pass a dotted ilist to a procedure not
defined to accept such an argument.
<!--========================================================================-->
</p><h2><a name="Constructors">Constructors</a></h2>
<p>
</p><dl>
<!--
==== ipair
============================================================================-->
<dt class="proc-def">
<a name="ipair"></a>
<code class="proc-def">ipair</code> <var>a d -> ipair</var>
</dt><dd class="proc-def">
The primitive constructor. Returns a newly allocated ipair whose icar is
<var>a</var> and whose icdr is <var>d</var>.
The ipair is guaranteed to be different (in the sense of <code>eqv?</code>)
from every existing object.
<pre class="code-example">(ipair 'a '()) => (a)
(ipair (iq a) (iq b c d)) => ((a) b c d)
(ipair "a" (iq b c)) => ("a" b c)
(ipair 'a 3) => (a . 3)
(ipair (iq a b) 'c) => ((a b ) . c)
</pre>
<!--
==== ilist
============================================================================-->
</dd><dt class="proc-def">
<a name="ilist"></a>
<code class="proc-def">ilist</code> <var>object ... -> ilist</var>
</dt><dd class="proc-def">
Returns a newly allocated ilist of its arguments.
<pre class="code-example">(ilist 'a (+ 3 4) 'c) => (a 7 c)
(ilist) => ()
</pre>
<!--
==== xipair
============================================================================-->
</dd><dt class="proc-def">
<a name="xipair"></a>
<code class="proc-def">xipair</code> <var>d a -> ipair</var>
</dt><dd class="proc-def">
<pre>(lambda (d a) (ipair a d))
</pre>
Of utility only as a value to be conveniently passed to higher-order
procedures.
<pre class="code-example">(xipair (iq b c) 'a) => (a b c)
</pre>
The name stands for "eXchanged Immutable PAIR."
<!--
==== ipair*
============================================================================-->
<a name="ipair*"></a>
</dd><dt class="proc-def"><code class="proc-def">ipair*</code><var> elt<sub>1</sub> elt<sub>2</sub> ... -> object</var>
</dt><dd class="proc-def">
Like <code>ilist</code>,
but the last argument provides the tail of the constructed ilist,
returning
<div class="indent"><code>
(ipair <var>elt<sub>1</sub></var> (ipair <var>elt<sub>2</sub></var> (ipair ... <var>elt<sub>n</sub></var>)))
</code></div>
<pre class="code-example">(ipair* 1 2 3 4) => (1 2 3 . 4)
(ipair* 1) => 1
</pre>
<!--
==== make-ilist
============================================================================-->
<a name="make-ilist"></a>
</dd><dt class="proc-def"> <code class="proc-def">make-ilist</code> <var>n [fill] -> ilist</var>
</dt><dd class="proc-def">
Returns an <var>n</var>-element ilist,
whose elements are all the value <var>fill</var>.
If the <var>fill</var> argument is not given, the elements of the ilist may
be arbitrary values.
<pre class="code-example">(make-ilist 4 'c) => (c c c c)
</pre>
<!--
==== ilist-tabulate
============================================================================-->
<a name="ilist-tabulate"></a>
</dd><dt class="proc-def"><code class="proc-def">ilist-tabulate</code><var> n init-proc -> ilist</var>
</dt><dd class="proc-def">
Returns an <var>n</var>-element ilist. Element <var>i</var> of the ilist, where 0 <= <var>i</var> < <var>n</var>,
is produced by <code>(<var>init-proc</var> <var>i</var>)</code>. No guarantee is made about the dynamic
order in which <var>init-proc</var> is applied to these indices.
<pre class="code-example">(ilist-tabulate 4 values) => (0 1 2 3)
</pre>
<!--
==== ilist-copy
============================================================================-->
<a name="ilist-copy"></a>
</dd><dt class="proc-def"><code class="proc-def">ilist-copy</code><var> dilist -> dilist</var>
</dt><dd class="proc-def">
Copies the spine of the argument, including the ilist tail.
<!--
==== iiota
============================================================================-->
<a name="iiota"></a>
</dd><dt class="proc-def"><code class="proc-def">iiota</code><var> count [start step] -> ilist</var>
</dt><dd class="proc-def">
Returns an ilist containing the elements
<pre class="code-example">(<var>start</var> <var>start</var>+<var>step</var> ... <var>start</var>+(<var>count</var>-1)*<var>step</var>)
</pre>
The <var>start</var> and <var>step</var> parameters default to 0 and 1, respectively.
This procedure takes its name from the APL primitive.
<pre class="code-example">(iiota 5) => (0 1 2 3 4)
(iiota 5 0 -0.1) => (0 -0.1 -0.2 -0.3 -0.4)
</pre>
</dd></dl>
<!--========================================================================-->
<h2><a name="Predicates">Predicates</a></h2>
<dl>
<!--
==== proper-ilist?
==== ilist?
============================================================================-->
<dt class="proc-def1">
<code class="proc-def">proper-ilist?</code><var> x -> boolean</var>
<a name="proper-ilist-p"></a>
</dt><dt class="proc-defn">
<code class="proc-def">ilist?</code><var> x -> boolean</var>
<a name="ilist-p"></a>
</dt><dd class="proc-def">
These identifiers are bound either to the same procedure, or to procedures of equivalent behavior. In either case, true is returned iff <var>x</var> is a proper ilist — a <code>()</code>-terminated ilist.
<p>
More carefully: The empty list is a proper ilist. An ipair whose icdr is a
proper ilist is also a proper ilist. Everything else is a dotted ilist. This includes
non-ipair, non-() values (<em>e.g.</em> symbols, numbers, mutable pairs),
which are considered to be dotted ilists of length 0.
</p>
<!--
==== dotted-ilist?
============================================================================-->
<a name="dotted-ilist-p"></a>
</dd><dt class="proc-def"><code class="proc-def">dotted-ilist?</code><var> x -> boolean</var>
</dt><dd class="proc-def">
True if <var>x</var> is a finite, non-nil-terminated ilist. That is, there exists
an <var>n</var> >= 0 such that icdr<sup><var>n</var></sup>(<var>x</var>) is neither an ipair nor ().
This includes
non-ipair, non-() values (<em>e.g.</em> symbols, numbers),
which are considered to be dotted ilists of length 0.
<pre>(dotted-ilist? <var>x</var>) = (not (proper-ilist? <var>x</var>))
</pre>
<!--
==== ipair?
============================================================================-->
<a name="ipair-p"></a>
</dd><dt class="proc-def"><code class="proc-def">ipair?</code><var> object -> boolean</var>
</dt><dd class="proc-def">
Returns #t if <var>object</var> is an ipair; otherwise, #f.
<pre class="code-example">(ipair? (ipair 'a 'b)) => #t
(ipair? (iq a b c)) => #t
(ipair? '()) => #f
(ipair? '#(a b)) => #f
(ipair? 7) => #f
(ipair? 'a) => #f
</pre>
<!--
==== null-ilist?
============================================================================-->
<a name="null-ilist-p"></a>
</dd><dt class="proc-def"><code class="proc-def">null-ilist?</code><var> ilist -> boolean</var>
</dt><dd class="proc-def">
<var>Ilist</var> is a proper ilist. This procedure returns true if
the argument is the empty list (), and false otherwise. It is an
error to pass this procedure a value which is not a proper ilist.
This procedure is recommended as the termination condition for
ilist-processing procedures that are not defined on dotted ilists.
<!--
==== not-ipair?
============================================================================-->
</dd><dt class="proc-def">
<a name="not-ipair-p"></a>
<code class="proc-def">not-ipair?</code><var> x -> boolean</var>
</dt><dd class="proc-def">
<pre>(lambda (x) (not (ipair? x)))</pre>
Provided as a procedure as it can be useful as the termination condition
for ilist-processing procedures that wish to handle all ilists,
both proper and dotted.
<!--
==== ilist=
============================================================================-->
</dd><dt class="proc-def">
<a name="list="></a>
<code class="proc-def">ilist=</code><var> elt= ilist<sub>1</sub> ... -> boolean</var>
</dt><dd class="proc-def">
Determines ilist equality, given an element-equality procedure.
Proper ilist <var>A</var> equals proper ilist <var>B</var>
if they are of the same length,
and their corresponding elements are equal,
as determined by <var>elt=</var>.
If the element-comparison procedure's first argument is
from <var>ilist<sub>i</sub></var>,
then its second argument is from <var>ilist<sub>i+1</sub></var>,
<em>i.e.</em> it is always called as
<code>(<var>elt=</var> <var>a</var> <var>b</var>)</code>
for <var>a</var> an element of ilist <var>A</var>,
and <var>b</var> an element of ilist <var>B</var>.
<p>
In the <var>n</var>-ary case,
every <var>ilist<sub>i</sub></var> is compared to
<var>ilist<sub>i+1</sub></var>
(as opposed, for example, to comparing
<var>ilist<sub>1</sub></var> to <var>ilist<sub>i</sub></var>,
for <var>i</var>>1).
If there are no ilist arguments at all,
<code>ilist=</code> simply returns true.
</p><p>
It is an error to apply <code>ilist=</code> to anything except proper ilists.
It
cannot reasonably be extended to dotted ilists, as it provides no way to
specify an equality procedure for comparing the ilist terminators.
</p><p>
Note that the dynamic order in which the <var>elt=</var> procedure is
applied to pairs of elements is not specified.
For example, if <code>ilist=</code> is applied
to three ilists, <var>A</var>, <var>B</var>, and <var>C</var>,
it may first completely compare <var>A</var> to <var>B</var>,
then compare <var>B</var> to <var>C</var>,
or it may compare the first elements of <var>A</var> and <var>B</var>,
then the first elements of <var>B</var> and <var>C</var>,
then the second elements of <var>A</var> and <var>B</var>, and so forth.
</p><p>
The equality procedure must be consistent with <code>eq?</code>.
That is, it must be the case that
</p><div class="indent">
<code>(eq? <var>x</var> <var>y</var>)</code> => <code>(<var>elt=</var> <var>x</var> <var>y</var>)</code>.
</div>
Note that this implies that two ilists which are <code>eq?</code>
are always <code>ilist=</code>, as well; implementations may exploit this
fact to "short-cut" the element-by-element comparisons.
<pre class="code-example">(ilist= eq?) => #t ; Trivial cases
(ilist= eq? (iq a)) => #t
</pre>
</dd></dl>
<!--========================================================================-->
<h2><a name="Selectors">Selectors</a></h2>
<dl>
<!--
==== icar icdr
============================================================================-->
<a name="icar"></a>
<a name="icdr"></a>
<dt class="proc-def1"><code class="proc-def">icar</code><var> ipair -> value</var>
</dt><dt class="proc-defn"><code class="proc-def">icdr</code><var> ipair -> value</var>
</dt><dd class="proc-def">
These procedures return the contents of the icar and icdr field of their
argument, respectively.
Note that it is an error to apply them to the empty ilist.
<pre class="code-example">(icar (iq a b c)) => a (icdr (iq a b c)) => (b c)
(icar (iq (a) b c d)) => (a) (icdr (iq (a) b c d)) => (b c d)
(icar (ipair 1 2)) => 1 (icdr (ipair 1 2)) => 2
(icar '()) => *error* (icdr '()) => *error*
</pre>
<!--
==== icaar icadr ... icdddar icddddr
============================================================================-->
<a name="icaar"></a>
<a name="icadr"></a>
<a name="icdddar"></a>
<a name="icddddr"></a>
</dd><dt class="proc-def1"><code class="proc-def">icaar</code><var> ipair -> value</var>
</dt><dt class="proc-defi"><code class="proc-def">icadr</code><var> ipair -> value</var>
</dt><dt class="proc-defi"><code class="proc-def">:</code>
</dt><dt class="proc-defi"><code class="proc-def">icdddar</code><var> ipair -> value</var>
</dt><dt class="proc-defn"><code class="proc-def">icddddr</code><var> ipair -> value</var>
</dt><dd class="proc-def">
These procedures are compositions of <code>icar</code> and <code>icdr</code>,
where for example <code>icaddr</code> could be defined by
<pre class="code-example">
(define icaddr (lambda (x) (icar (icdr (icdr x))))).
</pre>
Arbitrary compositions, up to four deep, are provided. There are
twenty-eight of these procedures in all.
<!--
==== ilist-ref
============================================================================-->
<a name="ilist-ref"></a>
</dd><dt class="proc-def"><code class="proc-def">ilist-ref</code><var> ilist i -> value</var>
</dt><dd class="proc-def">
Returns the <var>i</var><sup>th</sup> element of <var>ilist</var>.
(This is the same as the icar of
<code>(idrop <var>ilist</var> <var>i</var>)</code>.)
It is an error if <var>i</var> >= <var>n</var>,
where <var>n</var> is the length of <var>ilist</var>.
<pre class="code-example">
(ilist-ref (iq a b c d) 2) => c
</pre>
<!--
==== itenth
==== ininth
==== ieighth
==== iseventh
==== isixth
==== ififth
==== ifourth
==== ithird
==== isecond
==== ifirst
============================================================================-->
</dd><dt class="proc-def1">
<a name="ifirst"></a>
<code class="proc-def">ifirst </code><var>ipair -> object </var>
</dt><dt class="proc-defi">
<a name="isecond"></a>
<code class="proc-def">isecond </code><var>ipair -> object </var>
</dt><dt class="proc-defi">
<a name="ithird"></a>
<code class="proc-def">ithird </code><var>ipair -> object </var>
</dt><dt class="proc-defi">
<a name="ifourth"></a>
<code class="proc-def">ifourth </code><var>ipair -> object </var>
</dt><dt class="proc-defi">
<a name="ififth"></a>
<code class="proc-def">ififth </code><var>ipair -> object </var>
</dt><dt class="proc-defi">
<a name="isixth"></a>
<code class="proc-def">isixth </code><var>ipair -> object </var>
</dt><dt class="proc-defi">
<a name="iseventh"></a>
<code class="proc-def">iseventh </code><var>ipair -> object </var>
</dt><dt class="proc-defi">
<a name="ieighth"></a>
<code class="proc-def">ieighth </code><var>ipair -> object </var>
</dt><dt class="proc-defi">
<a name="ininth"></a>
<code class="proc-def">ininth </code><var>ipair -> object </var>
</dt><dt class="proc-defn">
<a name="itenth"></a>
<code class="proc-def">itenth </code><var>ipair -> object </var>
</dt><dd class="proc-def">
Synonyms for <code>car</code>, <code>cadr</code>, <code>caddr</code>, ...
<pre class="code-example">(ithird '(a b c d e)) => c
</pre>
<!--
==== icar+icdr
============================================================================-->
</dd><dt class="proc-def">
<a name="icar+icdr"></a>
<code class="proc-def">icar+icdr</code><var> ipair -> [x y]</var>
</dt><dd class="proc-def">
The fundamental ipair deconstructor:
<pre class="code-example">(lambda (p) (values (icar p) (icdr p)))
</pre>
This can, of course, be implemented more efficiently by a compiler.
<!--
==== idrop
==== itake
============================================================================-->
</dd><dt class="proc-def1">
<a name="itake"></a>
<code class="proc-def">itake</code><var> x i -> ilist</var>
</dt><dt class="proc-defi">
<a name="idrop"></a>
<code class="proc-def">idrop</code><var> x i -> object</var>
</dt><dt class="proc-defn">
<a name="idrop"></a>
<code class="proc-def">ilist-tail</code><var> x i -> object</var>
</dt><dd class="proc-def">
<code>itake</code> returns the first <var>i</var> elements of ilist <var>x</var>.<br/>
<code>idrop</code> returns all but the first <var>i</var> elements of ilist <var>x</var>.<br/>
<code>ilist-tail</code> is either the same procedure as <code>idrop</code> or else a procedure with the same behavior.
<pre class="code-example">(itake (iq a b c d e) 2) => (a b)
(idrop (iq a b c d e) 2) => (c d e)
</pre>
<var>x</var> may be any value — a proper or dotted ilist:
<pre class="code-example">(itake (ipair 1 (ipair 2 (ipair 3 'd))) => (1 2)
(idrop (ipair 1 (ipair 2 (ipair 3 'd))) 2) => (3 . d)
(itake (ipair 1 (ipair 2 (ipair 3 'd))) 3) => (1 2 3)
(idrop (ipair 1 (ipair 2 (ipair 3 'd))) 3) => d
</pre>
For a legal <var>i</var>, <code>itake</code> and <code>idrop</code> partition the ilist in a manner which
can be inverted with <code>iappend</code>:
<pre class="code-example">(iappend (itake <var>x</var> <var>i</var>) (idrop <var>x</var> <var>i</var>)) = <var>x</var>
</pre>
<code>idrop</code> is exactly equivalent to performing <var>i</var> icdr operations on <var>x</var>;
the returned value shares a common tail with <var>x</var>.
<!--
==== idrop-right
==== itake-right
============================================================================-->
</dd><dt class="proc-def1">
<a name="itake-right"></a>
<code class="proc-def">itake-right</code><var> dilist i -> object</var>
</dt><dt class="proc-defn">
<a name="idrop-right"></a>
<code class="proc-def">idrop-right</code><var> dilist i -> ilist</var>
</dt><dd class="proc-def">
<code>itake-right</code> returns the last <var>i</var> elements of <var>dilist</var>.<br/>
<code>idrop-right</code> returns all but the last <var>i</var> elements of <var>dilist</var>.
<pre class="code-example">(itake-right (iq a b c d e) 2) => (d e)
(idrop-right (iq a b c d e) 2) => (a b c)
</pre>
The returned ilist may share a common tail with the argument ilist.
<p>
<var>dilist</var> may be any ilist, either proper or dotted:
</p><pre class="code-example">(itake-right (iq ipair 1 (ipair 2 (ipair 3 'd))) 2) => (2 3 . d)
(idrop-right (ipair 1 (ipair 2 (ipair 3 'd))) 2) => (1)
(itake-right (ipair 1 (ipair 2 (ipair 3 'd))) 0) => d
(idrop-right (ipair 1 (ipair 2 (ipair 3 'd))) 0) => (1 2 3)
</pre>
For a legal <var>i</var>, <code>itake-right</code> and <code>idrop-right</code> partition the ilist in a manner
which can be inverted with <code>iappend</code>:
<pre class="code-example">(iappend (itake <var>dilist</var> <var>i</var>) (idrop <var>dilist</var> <var>i</var>)) = <var>dilist</var>
</pre>
<code>itake-right</code>'s return value is guaranteed to share a common tail with <var>dilist</var>.
<!--
==== isplit-at
============================================================================-->
</dd><dt class="proc-def">
<a name="isplit-at"></a>
<code class="proc-def">isplit-at </code><var> x i -> [ilist object]</var>
</dt><dd class="proc-def">
<code>isplit-at</code> splits the ilist <var>x</var>
at index <var>i</var>, returning an ilist of the
first <var>i</var> elements, and the remaining tail. It is equivalent
to
<pre class="code-example">(values (itake x i) (idrop x i))
</pre>
<!--
==== last-ipair
==== ilast
============================================================================-->
</dd><dt class="proc-def1">
<a name="ilast"></a>
<code class="proc-def">ilast</code><var> ipair -> object</var>
</dt><dt class="proc-defn">
<a name="last-ipair"></a>
<code class="proc-def">last-ipair</code><var> ipair -> ipair</var>
</dt><dd class="proc-def">
Returns the last element of the non-empty, possibly dotted, ilist <var>ipair</var>.
<code>last-ipair</code> returns the last ipair in the non-empty
ilist <var>pair</var>.
<pre class="code-example">(ilast (iq a b c)) => c
(last-ipair (iq a b c)) => (c)
</pre>
</dd></dl>
<!--========================================================================-->
<h2><a name="Miscellaneous">Miscellaneous: length, append, concatenate, reverse, zip & count</a></h2>
<dl>
<!--
==== ilength
============================================================================-->
<dt class="proc-def">
<a name="ilength"></a>
<code class="proc-def">ilength </code><var>ilist -> integer</var>
</dt><dd class="proc-def">
Returns the length of its argument.
It is an error to pass a value to <code>ilength</code> which is not a proper
ilist (<code>()</code>-terminated).<p>
The length of a proper ilist is a non-negative integer <var>n</var> such that <code>icdr</code>
applied <var>n</var> times to the ilist produces the empty list.
<!--
==== iappend
============================================================================-->
</p></dd><dt class="proc-def">
<a name="iappend"></a>
<code class="proc-def">iappend </code><var> ilist<sub>1</sub> ... -> ilist</var>
</dt><dd class="proc-def">
Returns an ilist consisting of the elements
of <var>ilist<sub>1</sub></var>
followed by the elements of the other ilist parameters.
<pre class="code-example">(iappend (iq x) (iq y)) => (x y)
(iappend (iq a) (iq b c d)) => (a b c d)
(iappend (iq a (b)) (iq (c))) => (a (b) (c))
</pre>
The resulting ilist is always newly allocated, except that it
shares structure with the final <var>ilist<sub>i</sub></var> argument.
This last argument may be any value at all;
an improper ilist results if it is not
a proper ilist. All other arguments must be proper ilists.
<pre class="code-example">(iappend (iq a b) (ipair 'c 'd)) => (a b c . d)
(iappend '() 'a) => a
(iappend (iq x y)) => (x y)
(iappend) => ()
</pre>
<!--
==== iconcatenate
============================================================================-->
</dd><dt class="proc-def">
<a name="iconcatenate"></a>
<code class="proc-def">iconcatenate </code><var> ilist-of-ilists -> value</var>
</dt><dd class="proc-def">
Appends the elements of its argument together.
That is, <code>iconcatenate</code> returns
<pre class="code-example">(iapply iappend ilist-of-ilists)
</pre>
or, equivalently,
<pre class="code-example">(ireduce-right iappend '() ilist-of-ilists)
</pre>
<p>
Note that some Scheme implementations do not support passing more than a
certain number (<em>e.g.</em>, 64) of arguments to an n-ary procedure.
In these implementations, the <code>(iapply iappend ...)</code> idiom
would fail when applied to long lists,
but <code>iconcatenate</code> would continue to function properly.
</p><p>
As with <code>iappend</code>,
the last element of the input list may be any value at all.
<!--
==== ireverse
============================================================================-->
</p></dd><dt class="proc-def">
<a name="ireverse"></a>