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

Last change on this file since 37761 was 37761, checked in by juergen, 16 months ago

biglists, pseudolists, list-comprehensiond: doku updated

File size: 15.3 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 Collect macro, inspired by Clojure's 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==== Collect
248
249<macro>(Collect item-xpr (var xs ok-xpr ...) (var1 xs1 ok-xpr1 ...) ...)</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-xpr ..., inserts the value of item-xpr into the result list.
254The qualifieres, (var xs ok-xpr ...), 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,
272if xs is empty
273
274==== Index
275
276<procedure>(Index ok?)</procedure>
277<procedure>(Index ok? xs)</procedure>
278
279returns the index of the first item of the biglist xs,
280which passes the ok? test
281
282==== Iterate
283
284<procedure>(Iterate fn)</procedure>
285<procedure>(Iterate fn x)</procedure>
286
287returns an infinite list by iteratively
288applying fn to x
289
290==== Iterate-times
291
292<procedure>(Iterate-times fn times)</procedure>
293<procedure>(Iterate-times fn times x)</procedure>
294
295returns a finite list of lentgh times by
296iteratively applying fn to x
297
298==== Iterate-until
299
300<procedure>(Iterate-until fn ok?)</procedure>
301<procedure>(Iterate-until fn ok? x)</procedure>
302
303returns a finite list by iteratively applying
304fn to x until ok? returns #t on the result
305
306==== Iterate-while
307
308<procedure>(Iterate-while fn ok?)</procedure>
309
310returns a finite list by iteratively applying
311fn to x as long as ok? returns #t on the result
312
313==== Lazy?
314
315<procedure>(Lazy? xpr)</procedure>
316
317is xpr a lazy biglist?
318
319==== Length
320
321<procedure>(Length xs)</procedure>
322
323retuns the length of a finite biglist or #f
324of an infinite one
325
326==== List
327
328<procedure>(List . args)</procedure>
329
330creates a lazy finite biglist with items args
331
332==== List?
333
334<procedure>(List? xpr)</procedure>
335
336is xpr a finite biglist?
337
338==== List-of?
339
340<procedure>(List-of? . oks?)</procedure>
341<procedure>(List-of? k . oks?)</procedure>
342
343returs a predicate on a biglist, which checks,
344if every item<procedure>(or Take k item) is a finite biglist
345
346==== Map
347
348<procedure>(Map fn)</procedure>
349<procedure>(Map fn . xss)</procedure>
350
351maps every list of of items at fixed index of xss
352with function fn
353
354==== Member
355
356<procedure>(Member x)</procedure>
357<procedure>(Member x xs)</procedure>
358
359returns the first tail af the biglist xs
360whose first item is equal? to x
361
362==== Memp
363
364<procedure>(Memp ok?)</procedure>
365<procedure>(Memp ok? xs)</procedure>
366
367returns the first tail af the biglist xs
368which passes the ok? test
369
370==== Memq
371
372<procedure>(Memq x)</procedure>
373<procedure>(Memq x xs)</procedure>
374
375returns the first tail af the biglist xs
376whose first item is eqv? to x
377
378==== Memv
379
380<procedure>(Memv x)</procedure>
381<procedure>(Memv x xs)</procedure>
382
383returns the first tail af the biglist xs
384whose first item is eqv? to x
385
386==== Merge
387
388<procedure>(Merge <? xs ys)</procedure>
389
390merges two finite finite biglists xs and ys,
391both lazy or both eager, with respect to <?
392
393==== Null?
394
395<procedure>(Null? xs)</procedure>
396
397is the biglist xs empty?
398
399==== Print
400
401<procedure>(Print k xs)</procedure>
402<procedure>(Print xs)</procedure>
403
404print the items of a finite biglist,
405or the first k items of an infinite one
406
407==== Range
408
409<procedure>(Range upto)</procedure>
410<procedure>(Range from upto)</procedure>
411<procedure>(Range from upto step)</procedure>
412
413creates a list of numbers with given limits
414from defaults to 0
415step defaults to 1
416the list is infinite, if utpo is #f
417
418==== Read-forever
419
420<procedure>(Read-forever)</procedure>
421
422creates an infinite biglist of prompted
423read procedures
424
425==== Remove
426
427<procedure>(Remove x)</procedure>
428<procedure>(Remove x xs)</procedure>
429
430removes all items of the biglist xs, which
431are equal? to x
432
433==== Remp
434
435<procedure>(Remp ok?)</procedure>
436<procedure>(Remp ok? xs)</procedure>
437
438removes all items of the biglist xs, which
439pass the ok? test
440
441==== Remq
442
443<procedure>(Remp x)</procedure>
444<procedure>(Remp x xs)</procedure>
445
446removes all items of the biglist xs, which
447are eq? to x
448
449==== Remv
450
451<procedure>(Remp x)</procedure>
452<procedure>(Remp x xs)</procedure>
453
454removes all items of the biglist xs, which
455are eqv? to x
456
457==== Repeat
458
459<procedure>(Repeat x)</procedure>
460
461returns an infinite biglist with all items x
462
463==== Repeat-times
464
465<procedure>(Repeat-times k x)</procedure>
466
467returns a finite biglist of length k with all items x
468
469==== Rest
470
471<procedure>(Rest xs)</procedure>
472
473returns the rest of the biglist except the front item
474which might be xs itself, if empty
475
476==== Reverse
477
478<procedure>(Reverse xs)</procedure>
479<procedure>(Reversee xs ys)</procedure>
480
481Append the reverse of xs to ys
482xs must be finite
483
484==== Reverse*
485
486<procedure>(Reverse* xs)</procedure>
487
488retrurns the list of reverses of
489of all finite takes
490
491==== Scan-left
492
493<procedure>(Scan-left op init)</procedure>
494<procedure>(Scan-left op init . xss)</procedure>
495
496returns a biglist, whose item at index k
497is the left fold of (map (Take k) xss)
498
499==== Scan-right
500
501<procedure>(Scan-right op init)</procedure>
502<procedure>(Scan-right op init . xss)</procedure>
503
504returns a biglist, whose item at index k
505is the right fold of (map (Take k) xss)
506
507==== Some?
508
509<procedure>(Some? ok?)</procedure>
510<procedure>(Some? ok? xs)</procedure>
511
512returns #t if some item of the finite biglist xs
513passes the ok? test
514
515==== Sort
516
517<procedure>(Sort <?)</procedure>
518<procedure>(Sort <? xs)</procedure>
519
520sorts the finite biglist xs with respect to <?
521
522==== Sorted?
523
524<procedure>(Sorted? <?)</procedure>
525<procedure>(Sorted? <? xs)</procedure>
526
527is the biglist xs finite and sorted?
528
529==== Take
530
531<procedure>(Take k)</procedure>
532<procedure>(Take k xs)</procedure>
533
534returns the finite biglist of the first
535k items of the biglist xs
536
537==== Take-until
538
539<procedure>(Take-until ok?)</procedure>
540<procedure>(Take-until ok? xs)</procedure>
541
542returns the finite biglist of the first
543items of the biglist xs, which do not pass
544the ok? test
545
546==== Take-while
547
548<procedure>(Take-while ok?)</procedure>
549<procedure>(Take-while ok? xs)</procedure>
550
551returns the finite biglist of the first
552items of the biglist xs, which do pass
553the ok? test
554
555==== Unzip
556
557<procedure>(Unzip xs)</procedure>
558
559returns two values, the sublists of biglist xs
560of even or uneven index
561
562==== Zip
563
564<procedure>(Zip xs ys)</procedure>
565
566merges the biglists xs and ys by alternatively
567Consing (First xs) or (First ys) to the result
568biglist. Works for unfinite biglists as well.
569
570==== eos
571
572end-of-sequence indicator
573
574=== Dependencies
575
576bindings
577
578=== Examples
579
580<enscript highlight=scheme>
581
582(import biglists bindings)
583
584(define ones (Cons 1 ones #f))
585
586(First eos) ;-> eos
587
588(At 2 '(0 1 2 3 4)) ;-> 2
589
590(At 3 (List 0 1 2 3 4) ;-> 3
591
592(List? (List 0 1 2 3 4) ;-> #t
593
594(List? '(0 1 2 3 4)) ;-> #t
595
596(BigList->list (Take 4 integers)) ;-> '(0 1 2 3)
597
598(First (Drop 4 integers)) ;-> 4
599
600(BigList->list (Reverse (List 0 1 2 3))) ;-> '(3 2 1 0)
601
602(Fold-right + 0 (List 1 2 3)) ;-> 6
603
604(Fold-left + 0 '(1 2 3)) ;-> 6
605
606(Length  (Scan-right + 0 four four)) ;-> 4
607
608(BigList->list 12 (Zip (List 0 1 2 3) integers))
609  ;-> '(0 0 1 1 2 2 3 3 4 5 6 7)
610
611(BigList->list 10 (nth-value 0 (Unzip integers)))
612  ;-> '(0 2 4 6 8 10 12 14 16 18)
613
614(BigList->list 10 (nth-value 1 (Unzip integers)))
615  ;-> '(1 3 5 7 9 11 13 15 17 19)
616
617(Merge <= '(0 1 2 3 4) '(0 1 2 3 4))
618  ;-> '(0 0 1 1 2 2 3 3 4 4)
619
620(BigList->list (Sort <= (Append (List 0 1 2 3) (List 0 1 2 3))))
621  ;-> '(0 0 1 1 2 2 3 3)
622
623(BigList->list 10 (Memv 3 integers))
624  ;-> '(3 4 5 6 7 8 9 10 11 12)
625
626(BigList->list (Assp odd? (List (List 0 5) (List 1 6) (List 2 7))))
627  ;-> '(1 6)
628
629(BigList->list 5 (Range #f)) ;-> '(0 1 2 3 4)
630
631(BigList->list (Iterate-times add1 5 1))
632  ;-> '(1 2 3 4 5)
633
634(bind (x . xs) integers (list x (BigList->list 5 xs)))
635  ;-> '(0 (1 2 3 4 5))
636
637(bind (x (y . ys) z) (List 1 integers 3)
638  (list x y z (BigList->list 5 ys)))
639  ;-> '(1 0 3 (1 2 3 4 5))
640
641(BigList->list (Collect (add1 x) (x (List 0 1 2 3)))) ;  map
642  ;-> '(1 2 3 4))
643
644(BigList->list (Collect x (x (List 0 1 2 3 4 5 6) (odd? x)))) ; filter
645  ;-> '(1 3 5))
646
647(BigList->list (Collect (* 10 n)
648                    (n (List 0 1 2 3 4 5 6) (positive? n) (even? n))))
649  ;-> '(20 40 60))
650
651(BigList->list (Collect (list c k)
652                    (c (List 'A 'B 'C)) ;lazy
653                    (k '(1 2 3 4)))) ;eager
654  ;-> '((A 1) (A 2) (A 3) (A 4)
655  ;     (B 1) (B 2) (B 3) (B 4)
656  ;     (C 1) (C 2) (C 3) (C 4))
657
658(Collect (list c k)
659     (c '(A B C)) ;eager
660     (k (List 1 2 3 4))) ;lazy
661  ;-> '((A 1) (A 2) (A 3) (A 4)
662  ;     (B 1) (B 2) (B 3) (B 4)
663  ;     (C 1) (C 2) (C 3) (C 4))
664
665</enscript>
666
667== Last update
668
669Jul 05, 2019
670
671== Author
672
673[[/users/juergen-lorenz|Juergen Lorenz]]
674
675== License
676
677 Copyright (c) 2014-2019, Juergen Lorenz
678 All rights reserved.
679
680 Redistribution and use in source and binary forms, with or without
681 modification, are permitted provided that the following conditions are
682 met:
683 
684 Redistributions of source code must retain the above copyright
685 notice, this list of conditions and the following disclaimer.
686 
687 Redistributions in binary form must reproduce the above copyright
688 notice, this list of conditions and the following disclaimer in the
689 documentation and/or other materials provided with the distribution.
690 Neither the name of the author nor the names of its contributors may be
691 used to endorse or promote products derived from this software without
692 specific prior written permission.
693   
694 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
695 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
696 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
697 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
698 HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
699 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
700 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
701 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
702 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
703 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
704 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
705
706== Version History
707
708; 0.3 : For macro renamed Collect
709; 0.2 : syntax of For changed
710; 0.1.2 : some typos corrected
711; 0.1 : initial import
712
713
714
Note: See TracBrowser for help on using the repository browser.