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

Last change on this file since 37410 was 37410, checked in by juergen, 17 months ago

biglists docu updated

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