source: project/wiki/eggref/5/biglists @ 38175

Last change on this file since 38175 was 38175, checked in by juergen, 9 months ago

biglists 0.4: dependency on bindings removed

File size: 15.0 KB
Line 
1[[tags: egg]]
2[[toc:]]
3
4== Eager and lazy lists united
5
6This is an attempt to unify eager and lazy list. To use this egg you
7should carefully note the following
8
9=== Rationale
10
11* All routines start uppercase.
12
13Hence they don't interfere with ordinary list routines.
14
15* The order of arguments is consistent.
16
17Procedure arguments first, list arguments last.
18For example, there is no List-ref routine, use At instead.
19
20* Most routines are defined in curried and uncurried form.
21
22So, curried versions can be used in Map and friends.
23The documentation shows both signatures, but explains only the
24uncurried form.
25
26* Biglists are either eager or lazy.
27
28* Lazy biglists are either finite or infinite.
29
30* All biglists are basically constructed with the macro Cons.
31
32This macro has two arguments for eager biglists, and an additional third
33argument, finite?, for lazy biglists.
34
35* The empty lazy biglist is the eos objects.
36
37* The emppy eager biglist is '(), as usual.
38
39* There are no Car and Cdr routines, but First and Rest instead.
40
41They behave differently: First returns eos at the empty biglist, and Rest
42returns itself at the empty biglist.
43Hence At can access even finite biglists at any position, it would
44simply return eos past the length of finite biglists.
45
46* List comprehensions work as well for biglists.
47
48This is provided by the Collect macro, inspired by Clojure's For macro.
49
50=== Documentation
51
52Note, that the signatures of curried and uncurried versions are listed,
53but only the uncurried ones are described.
54
55==== biglists
56
57<procedure>(biglists)</procedure>
58<procedure>(biglists sym)</procedure>
59
60The first call returns the list of exported symbols, the second
61documentation for the exported symbol sym.
62
63==== Append
64
65<procedure>(Append xs . xss)</procedure>
66
67appends all argument lists, provided all but the last
68are finite
69
70==== Assoc
71
72<procedure>(Assoc key)</procedure>
73<procedure>(Assoc key xs)</procedure>
74
75returns the biglist, whose First or car is Equal? to key
76
77==== Assp
78
79<procedure>(Assp ok?)</procedure>
80<procedure>(Assp ok? xs)</procedure>
81
82returns the biglist, whose First or car passes ok?
83
84==== Assq
85
86<procedure>(Assq key)</procedure>
87<procedure>(Assq key xs)</procedure>
88
89returns the biglist, whose First or car is Eq? to key
90
91==== Assv
92
93<procedure>(Assv key)</procedure>
94<procedure>(Assv key xs)</procedure>
95
96returns the biglist, whose First or car is Eqv? to key
97
98==== At
99
100<procedure>(At k)</procedure>
101<procedure>(At k xs)</procedure>
102
103returns the kth item of xs
104
105==== BigList?
106
107<procedure>(BigList? xpr)</procedure>
108
109type predicate
110
111==== BigList->list
112
113<procedure>(BigList->list xs)</procedure>
114<procedure>(BigList->list k xs)</procedure>
115
116transforms a possibly infinite biglist xs into a list
117
118==== Cons
119
120<macro>(Cons x y finite?)</macro>
121<macro>(Cons x y)</macro>
122
123returns either a lazy or an eager biglist
124
125==== Cycle
126
127<procedure>(Cycle xs)</procedure>
128
129returns an infinite biglist by appending the finite
130biglist xs over and over
131
132==== Cycle-times
133
134<procedure>(Cycle k xs)</procedure>
135
136returns a finite biglist by appending the finite
137biglist xs k times
138
139==== Drop
140
141<procedure>(Drop k)</procedure>
142<procedure>(Drop k xs)</procedure>
143
144drops the first k items of xs
145
146==== Drop-while
147
148<procedure>(Drop-while ok?)</procedure>
149<procedure>(Drop-while ok? xs)</procedure>
150
151returns the xs whith those front items x removed
152which pass ok?
153
154==== Drop-until
155
156<procedure>(Drop-until ok?)</procedure>
157<procedure>(Drop-until ok? xs)</procedure>
158
159returns the xs whith those front items x removed
160which don't pass ok?
161
162==== Eager?
163
164<procedure>(Eager? xpr)</procedure>
165
166is xpr an eager biglist, i.e. a normal list?
167
168==== Eq?
169
170<procedure>(Eq? xs ys)</procedure>
171
172returns #t if both lists have same length
173and corresponding items are eq?
174
175==== Eqp?
176
177<procedure>(Eqp? =?)</procedure>
178<procedure>(Eqp? =? xs ys)</procedure>
179
180returns #t if both lists have same length
181and corresponding items are =?
182
183==== Equal?
184
185<procedure>(Equal? xs ys)</procedure>
186
187returns #t if both lists have same length
188and corresponding items are equal?
189
190==== Eqv?
191
192<procedure>(Eqv? xs ys)</procedure>
193
194returns #t if both lists have same length
195and corresponding items are eqv?
196
197==== Every?
198
199<procedure>(Every? ok?)</procedure>
200<procedure>(Every? ok? xs)</procedure>
201
202returns #t if every item of the finite biglist xs
203passes the ok? test
204
205==== Filter
206
207<procedure>(Filter ok?)</procedure>
208<procedure>(Filter ok? xs)</procedure>
209
210removes all items from the biglist xs which
211do not pass the ok? test
212
213==== Fold-left
214
215<procedure>(Fold-left op init)</procedure>
216<procedure>(Fold-left op init . xss)</procedure>
217
218folds the finite biglists xss from the left
219
220==== Fold-left0
221
222<procedure>(Fold-left0 op)</procedure>
223<procedure>(Fold-left0 op . xss)</procedure>
224
225folds the finite biglists<procedure>(map Rest xss) from the left
226with init<procedure>(map First xss)</procedure>
227
228==== Fold-right
229
230<procedure>(Fold-right op init)</procedure>
231<procedure>(Fold-right op init . xss)</procedure>
232
233folds the finite biglists xss from the right
234
235==== Fold-right0
236
237<procedure>(Fold-right0 op)</procedure>
238<procedure>(Fold-right0 op . xss)</procedure>
239
240folds the finite biglists<procedure>(map Rest xss) from the right
241with init<procedure>(map First xss)</procedure>
242
243==== Collect
244
245<macro>(Collect item-xpr (var xs ok-xpr ...) (var1 xs1 ok-xpr1 ...) ...)</macro>
246
247creates a new list by binding var to each element
248of the list xs in sequence, and if it passes the checks,
249ok-xpr ..., inserts the value of item-xpr into the result list.
250The qualifieres, (var xs ok-xpr ...), are processed
251sequentially from left to right, so that filters of a
252qualifier have access to the variables of qualifiers
253to its left.
254
255==== For-each
256
257<procedure>(For-each fn)</procedure>
258<procedure>(For-each fn . xss)</procedure>
259
260applies the procedure fn to each list of items
261of xss at each commeon index
262
263==== First
264
265<procedure>(First xs)</procedure>
266
267returns the front item of xs, which might be eos,
268if xs is empty
269
270==== Index
271
272<procedure>(Index ok?)</procedure>
273<procedure>(Index ok? xs)</procedure>
274
275returns the index of the first item of the biglist xs,
276which passes the ok? test
277
278==== Iterate
279
280<procedure>(Iterate fn)</procedure>
281<procedure>(Iterate fn x)</procedure>
282
283returns an infinite list by iteratively
284applying fn to x
285
286==== Iterate-times
287
288<procedure>(Iterate-times fn times)</procedure>
289<procedure>(Iterate-times fn times x)</procedure>
290
291returns a finite list of lentgh times by
292iteratively applying fn to x
293
294==== Iterate-until
295
296<procedure>(Iterate-until fn ok?)</procedure>
297<procedure>(Iterate-until fn ok? x)</procedure>
298
299returns a finite list by iteratively applying
300fn to x until ok? returns #t on the result
301
302==== Iterate-while
303
304<procedure>(Iterate-while fn ok?)</procedure>
305
306returns a finite list by iteratively applying
307fn to x as long as ok? returns #t on the result
308
309==== Lazy?
310
311<procedure>(Lazy? xpr)</procedure>
312
313is xpr a lazy biglist?
314
315==== Length
316
317<procedure>(Length xs)</procedure>
318
319retuns the length of a finite biglist or #f
320of an infinite one
321
322==== List
323
324<procedure>(List . args)</procedure>
325
326creates a lazy finite biglist with items args
327
328==== List?
329
330<procedure>(List? xpr)</procedure>
331
332is xpr a finite biglist?
333
334==== List-of?
335
336<procedure>(List-of? . oks?)</procedure>
337<procedure>(List-of? k . oks?)</procedure>
338
339returs a predicate on a biglist, which checks,
340if every item<procedure>(or Take k item) is a finite biglist
341
342==== Map
343
344<procedure>(Map fn)</procedure>
345<procedure>(Map fn . xss)</procedure>
346
347maps every list of of items at fixed index of xss
348with function fn
349
350==== Member
351
352<procedure>(Member x)</procedure>
353<procedure>(Member x xs)</procedure>
354
355returns the first tail af the biglist xs
356whose first item is equal? to x
357
358==== Memp
359
360<procedure>(Memp ok?)</procedure>
361<procedure>(Memp ok? xs)</procedure>
362
363returns the first tail af the biglist xs
364which passes the ok? test
365
366==== Memq
367
368<procedure>(Memq x)</procedure>
369<procedure>(Memq x xs)</procedure>
370
371returns the first tail af the biglist xs
372whose first item is eqv? to x
373
374==== Memv
375
376<procedure>(Memv x)</procedure>
377<procedure>(Memv x xs)</procedure>
378
379returns the first tail af the biglist xs
380whose first item is eqv? to x
381
382==== Merge
383
384<procedure>(Merge <? xs ys)</procedure>
385
386merges two finite finite biglists xs and ys,
387both lazy or both eager, with respect to <?
388
389==== Null?
390
391<procedure>(Null? xs)</procedure>
392
393is the biglist xs empty?
394
395==== Print
396
397<procedure>(Print k xs)</procedure>
398<procedure>(Print xs)</procedure>
399
400print the items of a finite biglist,
401or the first k items of an infinite one
402
403==== Range
404
405<procedure>(Range upto)</procedure>
406<procedure>(Range from upto)</procedure>
407<procedure>(Range from upto step)</procedure>
408
409creates a list of numbers with given limits
410from defaults to 0
411step defaults to 1
412the list is infinite, if utpo is #f
413
414==== Read-forever
415
416<procedure>(Read-forever)</procedure>
417
418creates an infinite biglist of prompted
419read procedures
420
421==== Remove
422
423<procedure>(Remove x)</procedure>
424<procedure>(Remove x xs)</procedure>
425
426removes all items of the biglist xs, which
427are equal? to x
428
429==== Remp
430
431<procedure>(Remp ok?)</procedure>
432<procedure>(Remp ok? xs)</procedure>
433
434removes all items of the biglist xs, which
435pass the ok? test
436
437==== Remq
438
439<procedure>(Remp x)</procedure>
440<procedure>(Remp x xs)</procedure>
441
442removes all items of the biglist xs, which
443are eq? to x
444
445==== Remv
446
447<procedure>(Remp x)</procedure>
448<procedure>(Remp x xs)</procedure>
449
450removes all items of the biglist xs, which
451are eqv? to x
452
453==== Repeat
454
455<procedure>(Repeat x)</procedure>
456
457returns an infinite biglist with all items x
458
459==== Repeat-times
460
461<procedure>(Repeat-times k x)</procedure>
462
463returns a finite biglist of length k with all items x
464
465==== Rest
466
467<procedure>(Rest xs)</procedure>
468
469returns the rest of the biglist except the front item
470which might be xs itself, if empty
471
472==== Reverse
473
474<procedure>(Reverse xs)</procedure>
475<procedure>(Reversee xs ys)</procedure>
476
477Append the reverse of xs to ys
478xs must be finite
479
480==== Reverse*
481
482<procedure>(Reverse* xs)</procedure>
483
484retrurns the list of reverses of
485of all finite takes
486
487==== Scan-left
488
489<procedure>(Scan-left op init)</procedure>
490<procedure>(Scan-left op init . xss)</procedure>
491
492returns a biglist, whose item at index k
493is the left fold of (map (Take k) xss)
494
495==== Scan-right
496
497<procedure>(Scan-right op init)</procedure>
498<procedure>(Scan-right op init . xss)</procedure>
499
500returns a biglist, whose item at index k
501is the right fold of (map (Take k) xss)
502
503==== Some?
504
505<procedure>(Some? ok?)</procedure>
506<procedure>(Some? ok? xs)</procedure>
507
508returns #t if some item of the finite biglist xs
509passes the ok? test
510
511==== Sort
512
513<procedure>(Sort <?)</procedure>
514<procedure>(Sort <? xs)</procedure>
515
516sorts the finite biglist xs with respect to <?
517
518==== Sorted?
519
520<procedure>(Sorted? <?)</procedure>
521<procedure>(Sorted? <? xs)</procedure>
522
523is the biglist xs finite and sorted?
524
525==== Take
526
527<procedure>(Take k)</procedure>
528<procedure>(Take k xs)</procedure>
529
530returns the finite biglist of the first
531k items of the biglist xs
532
533==== Take-until
534
535<procedure>(Take-until ok?)</procedure>
536<procedure>(Take-until ok? xs)</procedure>
537
538returns the finite biglist of the first
539items of the biglist xs, which do not pass
540the ok? test
541
542==== Take-while
543
544<procedure>(Take-while ok?)</procedure>
545<procedure>(Take-while ok? xs)</procedure>
546
547returns the finite biglist of the first
548items of the biglist xs, which do pass
549the ok? test
550
551==== Unzip
552
553<procedure>(Unzip xs)</procedure>
554
555returns two values, the sublists of biglist xs
556of even or uneven index
557
558==== Zip
559
560<procedure>(Zip xs ys)</procedure>
561
562merges the biglists xs and ys by alternatively
563Consing (First xs) or (First ys) to the result
564biglist. Works for unfinite biglists as well.
565
566==== eos
567
568end-of-sequence indicator
569
570=== Dependencies
571
572None
573
574=== Examples
575
576<enscript highlight=scheme>
577
578(import biglists)
579
580(define ones (Cons 1 ones #f))
581
582(First eos) ;-> eos
583
584(At 2 '(0 1 2 3 4)) ;-> 2
585
586(At 3 (List 0 1 2 3 4) ;-> 3
587
588(List? (List 0 1 2 3 4) ;-> #t
589
590(List? '(0 1 2 3 4)) ;-> #t
591
592(BigList->list (Take 4 integers)) ;-> '(0 1 2 3)
593
594(First (Drop 4 integers)) ;-> 4
595
596(BigList->list (Reverse (List 0 1 2 3))) ;-> '(3 2 1 0)
597
598(Fold-right + 0 (List 1 2 3)) ;-> 6
599
600(Fold-left + 0 '(1 2 3)) ;-> 6
601
602(Length  (Scan-right + 0 four four)) ;-> 4
603
604(BigList->list 12 (Zip (List 0 1 2 3) integers))
605  ;-> '(0 0 1 1 2 2 3 3 4 5 6 7)
606
607(BigList->list 10 (nth-value 0 (Unzip integers)))
608  ;-> '(0 2 4 6 8 10 12 14 16 18)
609
610(BigList->list 10 (nth-value 1 (Unzip integers)))
611  ;-> '(1 3 5 7 9 11 13 15 17 19)
612
613(Merge <= '(0 1 2 3 4) '(0 1 2 3 4))
614  ;-> '(0 0 1 1 2 2 3 3 4 4)
615
616(BigList->list (Sort <= (Append (List 0 1 2 3) (List 0 1 2 3))))
617  ;-> '(0 0 1 1 2 2 3 3)
618
619(BigList->list 10 (Memv 3 integers))
620  ;-> '(3 4 5 6 7 8 9 10 11 12)
621
622(BigList->list (Assp odd? (List (List 0 5) (List 1 6) (List 2 7))))
623  ;-> '(1 6)
624
625(BigList->list 5 (Range #f)) ;-> '(0 1 2 3 4)
626
627(BigList->list (Iterate-times add1 5 1))
628  ;-> '(1 2 3 4 5)
629
630(BigList->list (Collect (add1 x) (x (List 0 1 2 3)))) ;  map
631  ;-> '(1 2 3 4))
632
633(BigList->list (Collect x (x (List 0 1 2 3 4 5 6) (odd? x)))) ; filter
634  ;-> '(1 3 5))
635
636(BigList->list (Collect (* 10 n)
637                    (n (List 0 1 2 3 4 5 6) (positive? n) (even? n))))
638  ;-> '(20 40 60))
639
640(BigList->list (Collect (list c k)
641                    (c (List 'A 'B 'C)) ;lazy
642                    (k '(1 2 3 4)))) ;eager
643  ;-> '((A 1) (A 2) (A 3) (A 4)
644  ;     (B 1) (B 2) (B 3) (B 4)
645  ;     (C 1) (C 2) (C 3) (C 4))
646
647(Collect (list c k)
648     (c '(A B C)) ;eager
649     (k (List 1 2 3 4))) ;lazy
650  ;-> '((A 1) (A 2) (A 3) (A 4)
651  ;     (B 1) (B 2) (B 3) (B 4)
652  ;     (C 1) (C 2) (C 3) (C 4))
653
654</enscript>
655
656== Last update
657
658Jul 05, 2019
659
660== Author
661
662[[/users/juergen-lorenz|Juergen Lorenz]]
663
664== License
665
666 Copyright (c) 2014-2019, Juergen Lorenz
667 All rights reserved.
668
669 Redistribution and use in source and binary forms, with or without
670 modification, are permitted provided that the following conditions are
671 met:
672 
673 Redistributions of source code must retain the above copyright
674 notice, this list of conditions and the following disclaimer.
675 
676 Redistributions in binary form must reproduce the above copyright
677 notice, this list of conditions and the following disclaimer in the
678 documentation and/or other materials provided with the distribution.
679 Neither the name of the author nor the names of its contributors may be
680 used to endorse or promote products derived from this software without
681 specific prior written permission.
682   
683 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
684 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
685 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
686 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
687 HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
688 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
689 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
690 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
691 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
692 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
693 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
694
695== Version History
696
697; 0.4 : dependency on bindings removed
698; 0.3 : For macro renamed Collect
699; 0.2 : syntax of For changed
700; 0.1.2 : some typos corrected
701; 0.1 : initial import
702
703
704
Note: See TracBrowser for help on using the repository browser.