source: project/wiki/eggref/4/lazy-lists @ 27160

Last change on this file since 27160 was 27160, checked in by juergen, 9 years ago

lazy-list docu fixed

File size: 26.8 KB
Line 
1[[tags: egg]]
2[[toc:]]
3
4== Lazy lists
5
6Lists in Scheme and Lisp are eager. Since the procedure calling regime
7in these languages is "Call by value", a list argument of a procedure
8call is completely constructed before the procedure is called. This is
9fine for small lists, but it excludes practically the chaining of
10procedure calls with large list arguments. On the other hand such a
11chaining is a tremendously powerful modularization technique, as
12demonstrated by purely functional languages like Haskell.
13
14The traditional tools for implementation of lazy evaluation consist of
15the two Scheme primitives delay and force (cf. the classic "Structure
16and Interpretation of Computer Porgrams" by Abelson and Sussman, usually
17abbreveated "SICP"). But there is a better method as shown by Moritz
18Heidkamp in his lazy-seq Module, which in turn is meant to replace the
19stream datatype in SRFI-41. Moritz' approach is inspired by the Lisp
20dialect Clojure, which also motivated the beautiful macros in his
21clojurian module. The fundamental idea is to store the structure of a
22lazy list in a record, but to realize this list only as much as needed.
23This way a large (even infinite) list can be created instantaneously
24without realizing it and will be realized only if and as much as used.
25
26This module is based on Heidkamp's implementation with one essential
27addition: The length of the list is stored in the record and can thus be
28referenced without realizing the whole list. After all, some operations
29like reverse are only meaningful for finite lists, so one must know
30beforehand if a list is finite to avoid infinite loops.
31
32But knowing the length of a list at the moment of its creation, lazy
33lists can replace ordinary lists as a datatype. And ordinary list
34operations can be replaced by lazy list operations. This is the reason
35for the other difference of this module with Moritz' lazy-seq, a
36cosmetic difference: Lazy list operations are named with the same name
37as ordinary ones, only capitalized at the beginning. So Cons, Car, Cdr
38... are the replacements of cons, car, cdr etc. Some operators have a
39different argument order, thow, so that the clojurian chaining macro ->>
40works well. The consistent argument order is as follows: procedure
41arguments appear first, lazy list arguments last. For example (Ref n seq)
42replaces (list-ref seq n), (Drop n seq) replaces (list-tail seq n), etc.
43 
44Storing the length in the list record has another advantage: I can and
45will use my own contracts module to guard the implementation of the
46routines by contracts, i.e. pre- and postconditions. This allows to
47implement the routines proper without any defenses - this is done in the
48module %lazy-lists - and wrap each call with the contract in the
49lazy-lists module. In other words, both modules have exactly the same
50interface (with one exception: the documentation procedure lazy-lists in
51the latter). The routines of the former are imported into the latter
52with the prefix %, so that they can be used there without contracts.
53
54Remember, that modules written in the design-by-contract style have
55their documentation included, namely the equally named procedure
56
57==== lazy-lists
58
59<procedure>(lazy-lists [sym])</procedure>
60
61returns all available routines of the module when called without an
62argument, but when called with one of these routines as a symbol,
63returns its contract and documentation string.
64
65==== make-lazy
66
67<procedure>(make-lazy len thunk)</procedure>
68
69<enscript highlight=scheme>
70(domain (or (not len) (and (integer? len) (not (negative? len))))
71(procedure? thunk) "thunk returns either '(), a List or (cons val List)")
72(range (%List? result) (= (%Length result) len))
73</enscript>
74
75lazy constructor
76
77==== Lazy
78
79<syntax>(Lazy len xpr . xprs)</syntax>
80
81wrapper to make-lazy constructor
82
83==== Nil
84
85empty lazy list
86
87==== List?
88
89<procedure>(List? xpr)</procedure>
90
91<enscript highlight=scheme>
92(range (boolean? result))
93</enscript>
94
95lazy version of list?
96
97==== Length
98
99<procedure>(Length seq)</procedure>
100
101<enscript highlight=scheme>
102(domain (%List? seq))
103(range (or (not result) (and (integer? result) (not (negative? result)))))
104</enscript>
105
106lazy version of length
107
108==== Cons
109
110<procedure>(Cons var seq)</procedure>
111
112<enscript highlight=scheme>
113(domain (%List? seq))
114(range (%List? result) (or (not (%Length seq)) (= (%Length result) (+ (%Length seq) 1))))
115</enscript>
116
117lazy version of cons
118
119==== Rest
120
121<procedure>(Rest seq)</procedure>
122
123<enscript highlight=scheme>
124(domain (%List? seq) (not (%Null? seq)))
125(range (%List? result) (or (not (%Length seq)) (= (%Length result) (- (%Length seq) 1))))
126</enscript>
127
128lazy version of cdr
129
130==== Cdr
131
132<procedure>(Cdr seq)</procedure>
133
134<enscript highlight=scheme>
135(domain (%List? seq) (not (%Null? seq)))
136(range (%List? result) (or (not (%Length seq)) (= (%Length result) (- (%Length seq) 1))))
137</enscript>
138
139lazy version of cdr
140
141==== First
142
143<procedure>(First seq)</procedure>
144
145<enscript highlight=scheme>
146(domain (%List? seq) (not (%Null? seq)))
147</enscript>
148
149lazy version of car
150
151==== Car
152
153<procedure>(Car seq)</procedure>
154
155<enscript highlight=scheme>
156(domain (%List? seq) (not (%Null? seq)))
157</enscript>
158
159lazy version of car
160
161==== Ref
162
163<procedure>(Ref n seq)</procedure>
164
165<enscript highlight=scheme>
166(domain (%List? seq) (integer? n) (or (not (%Length seq)) (< -1 n (%Length seq))))
167</enscript>
168
169lazy version of list-ref with changed argument order
170
171==== Null?
172
173<procedure>(Null? seq)</procedure>
174
175<enscript highlight=scheme>
176(domain (%List? seq))
177(range (boolean? result))
178</enscript>
179
180lazy version of null?
181
182==== Zip
183
184<procedure>(Zip seq1 seq2)</procedure>
185
186<enscript highlight=scheme>
187(domain (%List? seq1) (%List? seq2))
188(range (%List? result) (if (and (%Length seq1) (%Length seq2)) (= (%Length result) (+ (%Length seq1) (%Length seq2))) (not (%Length result))))
189</enscript>
190
191interleave two lazy lists
192
193==== Some?
194
195<procedure>(Some? ok? seq)</procedure>
196
197<enscript highlight=scheme>
198(domain (%List? seq) (%Length seq) (procedure? ok?) "(ok? x)")
199</enscript>
200
201does some item of seq fulfill ok?
202
203==== Every?
204
205<procedure>(Every? ok? seq)</procedure>
206
207<enscript highlight=scheme>
208(domain (%List? seq) (%Length seq) (procedure? ok?) "(ok? x)")
209</enscript>
210
211does every item of seq fulfill ok?
212
213==== Fold-right*
214
215<procedure>(Fold-right* op base . seqs)</procedure>
216
217<enscript highlight=scheme>
218(domain (procedure? op) "(op b . ss)" ((list-of? %List?) seqs) (or (null? seqs) (all (lambda (x) (eqv? (%Length x) (%Length (car seqs)))) (cdr seqs))))
219(range (%List? result) (if (null? seqs) (not (%Length result)) (eqv? (%Length result) (%Length (car seqs)))))
220</enscript>
221
222create a lazy list of right folds changing order or List items
223
224==== Fold-left*
225
226<procedure>(Fold-left* op base . seqs)</procedure>
227
228<enscript highlight=scheme>
229(domain (procedure? op) "(op b . ss)" ((list-of? %List?) seqs) (or (null? seqs) (all (lambda (x) (eqv? (%Length x) (%Length (car seqs)))) (cdr seqs))))
230(range (%List? result) (if (null? seqs) (not (%Length result)) (eqv? (%Length result) (%Length (car seqs)))))
231</enscript>
232
233create a lazy list of left folds
234
235==== Fold-right
236
237<procedure>(Fold-right op base seq . seqs)</procedure>
238
239<enscript highlight=scheme>
240(domain (procedure? op) "(op b s . ss)" (%List? seq) ((list-of? %List?) seqs) (%Length seq) (all (lambda (x) (= (%Length x) (%Length seq))) seqs))
241</enscript>
242
243lazy version of fold-right
244
245==== Fold-left
246
247<procedure>(Fold-left op base seq . seqs)</procedure>
248
249<enscript highlight=scheme>
250(domain (procedure? op) "(op b s . ss)" (%List? seq) ((list-of? %List?) seqs) (%Length seq) (all (lambda (x) (= (%Length x) (%Length seq))) seqs))
251</enscript>
252
253lazy version of fold-left
254
255==== Sieve
256
257<procedure>(Sieve =? seq)</procedure>
258
259<enscript highlight=scheme>
260(domain (%List? seq) (procedure? =?) "(=? a b)")
261(range (%List? result) "not two items =?" (if (%Length seq) (<= (%Length result) (%Length seq)) (not (%Length result))))
262</enscript>
263
264sieve of Erathostenes with respect to =?
265
266==== Split-with
267
268<procedure>(Split-with ok? seq)</procedure>
269
270<enscript highlight=scheme>
271(domain (%List? seq) (%Length seq) (procedure? ok?) "(ok? x)")
272(range (with-results (head index tail) (%List? head) (%List? tail) (integer? index) (not (negative? index)) (<= (%Length head) (%Length seq)) (<= (%Length tail) (%Length seq))))
273</enscript>
274
275split a lazy list at first index fulfilling ok?
276
277==== Split-at
278
279<procedure>(Split-at n seq)</procedure>
280
281<enscript highlight=scheme>
282(domain (%List? seq) (integer? n) (not (negative? n)))
283(range (with-results (head tail) (%List? head) (%Length head) (<= (%Length head) n) (%List? tail) (if (%Length seq) (<= (%Length tail) (%Length seq)) (not (%Length tail)))))
284</enscript>
285
286split a List at fixed position
287
288==== List->vector
289
290<procedure>(List->vector seq)</procedure>
291
292<enscript highlight=scheme>
293(domain (%List? seq) (%Length seq))
294(range (vector? result) (eqv? (vector-length result) (%Length seq)))
295</enscript>
296
297transform a finite lazy list into a vector
298
299==== vector->List
300
301<procedure>(vector->List vec)</procedure>
302
303<enscript highlight=scheme>
304(domain (vector? vec))
305(range (%List? result) (eqv? (%Length result) (vector-length vec)))
306</enscript>
307
308transform a vector into a lazy list
309
310==== Sort
311
312<procedure>(Sort <? seq)</procedure>
313
314<enscript highlight=scheme>
315(domain (procedure? <?) "(<? a b)" (%List? seq) (%Length seq))
316(range (%List? result) "<? sorted" (eqv? (%Length result) (%Length seq)))
317</enscript>
318
319sort a finite lazy list with respect to <?
320
321==== Merge
322
323<procedure>(Merge <? seq1 seq2)</procedure>
324
325<enscript highlight=scheme>
326(domain (procedure? <?) "(<? a b)" (%List? seq1) (%Length seq1) <? sorted (%List? seq2) (%Length seq2) <? sorted)
327(range (%List? result) "<? sorted" (= (%Length result) (+ (%Length seq1) (%Length seq2))))
328</enscript>
329
330merge two sorted lazy lists with respect to <?
331
332==== Cycle
333
334<procedure>(Cycle seq)</procedure>
335
336<enscript highlight=scheme>
337(domain (%List? seq) (%Length seq))
338(range (%List? result) (not (%Length result)))
339</enscript>
340
341create infinite List by cycling finite List seq
342
343==== Reverse*
344
345<procedure>(Reverse* seq)</procedure>
346
347<enscript highlight=scheme>
348(domain (%List? seq))
349(range (%List? result) (eqv? (%Length result) (%Length seq)))
350</enscript>
351
352List of successive reversed subLists
353
354==== Reverse
355
356<procedure>(Reverse seq)</procedure>
357
358<enscript highlight=scheme>
359(domain (%List? seq) (%Length seq))
360(range (%List? result) (%Length result) (= (%Length result) (%Length seq)))
361</enscript>
362
363lazy version of reverse
364
365==== Append
366
367<procedure>(Append . seqs)</procedure>
368
369<enscript highlight=scheme>
370(domain ((list-of? %List?) seqs) (let ((lst (memv #f (map %Length seqs)))) (or (not lst) (<= (length lst) 1))))
371(range (%List? result) (or (not (%Length result)) (= (%Length result) (apply + (map %Length seqs)))))
372</enscript>
373
374lazy version of append
375
376==== Iterate
377
378<procedure>(Iterate proc x)</procedure>
379
380<enscript highlight=scheme>
381(domain (procedure? proc) "(proc x)")
382(range (%List? result) (not (%Length result)))
383</enscript>
384
385create infinite List by applying proc succesively to x
386
387==== Repeatedly
388
389<procedure>(Repeatedly thunk)</procedure>
390
391<enscript highlight=scheme>
392(domain (procedure? thunk))
393(range (%List? result) (not (%Length result)))
394</enscript>
395
396create infinite List of return values of thunk
397
398==== Repeat
399
400<procedure>(Repeat x)</procedure>
401
402<enscript highlight=scheme>
403(range (%List? result) (not (%Length result)))
404</enscript>
405
406create infinite List of x
407
408==== input->List
409
410<procedure>(input->List port read-proc)</procedure>
411
412<enscript highlight=scheme>
413(domain (input-port? port) (procedure? read-proc))
414(range (%List? result) (%Length result))
415</enscript>
416
417transform input port into List with read-proc
418
419==== For-each
420
421<procedure>(For-each proc seq . seqs)</procedure>
422
423<enscript highlight=scheme>
424(domain (%List? seq) ((list-of? %List?) seqs) (procedure? proc) "(proc arg . args)" (all (lambda (x) (eqv? (%Length x) (%Length seq))) seqs))
425</enscript>
426
427lazy version of for-each
428
429==== Filter
430
431<procedure>(Filter ok? seq)</procedure>
432
433<enscript highlight=scheme>
434(domain (%List? seq) (procedure? ok?) "(ok? x)")
435(range (%List? result) (or (not (%Length seq)) (<= (%Length result) (%Length seq))))
436</enscript>
437
438lazy version of filter
439
440==== Map
441
442<procedure>(Map proc seq . seqs)</procedure>
443
444<enscript highlight=scheme>
445(domain (%List? seq) ((list-of? %List?) seqs) (procedure? proc) "(proc arg . args)" (all (lambda (x) (eqv? (%Length x) (%Length seq))) seqs))
446(range (%List? result) (eqv? (%Length result) (%Length seq)))
447</enscript>
448
449lazy version of map
450
451==== Assoc
452
453<procedure>(Assoc key aseq)</procedure>
454
455<enscript highlight=scheme>
456(domain (%List? aseq) "List of pairs" (%Length aseq))
457(range (or (not result) (pair? result)))
458</enscript>
459
460lazy version of assoq
461
462==== Assv
463
464<procedure>(Assv key aseq)</procedure>
465
466<enscript highlight=scheme>
467(domain (%List? aseq) "List of pairs" (%Length aseq))
468(range (or (not result) (pair? result)))
469</enscript>
470
471lazy version of assv
472
473==== Assq
474
475<procedure>(Assq key aseq)</procedure>
476
477<enscript highlight=scheme>
478(domain (%List? aseq) "List of pairs" (%Length aseq))
479(range (or (not result) (pair? result)))
480</enscript>
481
482lazy version of assq
483
484==== Assp
485
486<procedure>(Assp ok? aseq)</procedure>
487
488<enscript highlight=scheme>
489(domain (%List? aseq) "List of pairs" (%Length aseq) (procedure? ok?) "(ok? x)")
490(range (or (not result) (pair? result)))
491</enscript>
492
493return #f or first pair, whose Car fulfills ok?
494
495==== Equal?
496
497<procedure>(Equal? seq1 seq2)</procedure>
498
499<enscript highlight=scheme>
500(domain (%List? seq1) (%List? seq2))
501(range (boolean? result))
502</enscript>
503
504lazy version of equal?
505
506==== Eqv?
507
508<procedure>(Eqv? seq1 seq2)</procedure>
509
510<enscript highlight=scheme>
511(domain (%List? seq1) (%List? seq2))
512(range (boolean? result))
513</enscript>
514
515lazy version of eqv?
516
517==== Eq?
518
519<procedure>(Eq? seq1 seq2)</procedure>
520
521<enscript highlight=scheme>
522(domain (%List? seq1) (%List? seq2))
523(range (boolean? result))
524</enscript>
525
526lazy version of eq?
527
528==== Equ?
529
530<procedure>(Equ? =? seq1 seq2)</procedure>
531
532<enscript highlight=scheme>
533(domain (%List? seq1) (%List? seq2) (procedure? =?) "(=? x y)")
534(range (boolean? result))
535</enscript>
536
537compare two Lists with predicate =?
538
539==== Member
540
541<procedure>(Member var seq)</procedure>
542
543<enscript highlight=scheme>
544(domain (%List? seq) (%Length seq))
545(range (%List? result) (<= (%Length result) (%Length seq)))
546</enscript>
547
548lazy version of member
549
550==== Memv
551
552<procedure>(Memv var seq)</procedure>
553
554<enscript highlight=scheme>
555(domain (%List? seq) (%Length seq))
556(range (%List? result) (<= (%Length result) (%Length seq)))
557</enscript>
558
559lazy version of memv
560
561==== Memq
562
563<procedure>(Memq var seq)</procedure>
564
565<enscript highlight=scheme>
566(domain (%List? seq) (%Length seq))
567(range (%List? result) (<= (%Length result) (%Length seq)))
568</enscript>
569
570lazy version of memq
571
572==== Memp
573
574<procedure>(Memp ok? seq)</procedure>
575
576<enscript highlight=scheme>
577(domain (%List? seq) (%Length seq) (procedure? ok?) (ok? x))
578(range (%List? result) (<= (%Length result) (%Length seq)))
579</enscript>
580
581Tail of items not fulfilling ok?
582
583==== Index
584
585<procedure>(Index ok? seq)</procedure>
586
587<enscript highlight=scheme>
588(domain (%List? seq) (%Length seq) (procedure? ok?) "(ok? x)")
589(range (integer? result) (not (negative? result)))
590</enscript>
591
592return index of first item fulfilling ok?
593
594==== Drop-upto
595
596<procedure>(Drop-upto ok? seq)</procedure>
597
598<enscript highlight=scheme>
599(domain (%List? seq) (%Length seq) (procedure? ok?) "(ok? x)")
600(range (%List? result) (<= (%Length result) (%Length seq)))
601</enscript>
602
603Tail of items not fulfilling ok?
604
605==== Take-upto
606
607<procedure>(Take-upto ok? seq)</procedure>
608
609<enscript highlight=scheme>
610(domain (%List? seq) (%Length seq) (procedure? ok?) "(ok? x)")
611(range (%List? result) (<= (%Length result) (%Length seq)))
612</enscript>
613
614List of head items fulfilling ok?
615
616==== Drop
617
618<procedure>(Drop n seq)</procedure>
619
620<enscript highlight=scheme>
621(domain (%List? seq) (integer? n) (not (negative? n)))
622(range (%List? result) (if (%Length seq) (= (%Length result) (max 0 (- (%Length seq) n))) (not (%Length result))))
623</enscript>
624
625lazy version of list-tail with changed argument order
626
627==== Take
628
629<procedure>(Take n seq)</procedure>
630
631<enscript highlight=scheme>
632(domain (%List? seq) (integer? n) (not (negative? n)))
633(range (%List? result) (%Length result) (if (%Length seq) (= (%Length result) (min n (%Length seq))) (= (%Length result) n)))
634</enscript>
635
636List of first n items of seq
637
638==== List
639
640<procedure>(List . args)</procedure>
641
642<enscript highlight=scheme>
643(range (%List? result) (eqv? (%Length result) (length args)))
644</enscript>
645
646lazy version of list
647
648==== list->List
649
650<procedure>(list->List lst)</procedure>
651
652<enscript highlight=scheme>
653(domain (list? lst))
654(range (%List? result) (eqv? (%Length result) (length lst)))
655</enscript>
656
657transform ordinary list into finite lazy list
658
659==== List->list
660
661<procedure>(List->list seq)</procedure>
662
663<enscript highlight=scheme>
664(domain (%List? seq) (%Length seq))
665(range (list? result))
666</enscript>
667
668transform finite lazy into ordinary list
669
670==== Realized?
671
672<procedure>(Realized? seq)</procedure>
673
674<enscript highlight=scheme>
675(domain (%List? seq))
676(range (boolean? result))
677</enscript>
678
679Is seq realized?
680
681==== Primes
682
683<procedure>(Primes)</procedure>
684
685<enscript highlight=scheme>
686(range (%List? result) (not (%Length result)))
687</enscript>
688
689lazy list of non prime numbers
690
691==== Cardinals
692
693<procedure>(Cardinals)</procedure>
694
695<enscript highlight=scheme>
696(range (%List? result) (not (%Length result)))
697</enscript>
698
699lazy list of non negative integers
700
701==== Interval
702
703<procedure>(Interval from upto)</procedure>
704
705<enscript highlight=scheme>
706(domain (integer? from) (integer? upto))
707(range (%List result) (= (%Length result) (abs (- upto from))))
708</enscript>
709
710List of integers from (included) upto (excluded)
711
712== Usage
713
714<enscript highlight=scheme>
715(use lazy-lists contracts)
716</enscript>
717
718== Examples
719
720<enscript highlight=scheme>
721
722
723(require-library clojurian-syntax lazy-lists contracts)
724(import lazy-lists clojurian-syntax contracts)
725
726;;; (run xpr0 xpr1 ...)
727;;; -------------------
728(define (run . xprs)
729  (let loop ((xprs xprs))
730    (if (null? xprs)
731      (print "All tests passed!")
732      (if (car xprs)
733        (loop (cdr xprs))
734        (error 'run "#### Some test failed! ####")))))
735
736(define (cons-right var lst)
737  (if (null? lst)
738    (cons var lst)
739    (cons (car lst) (cons-right var (cdr lst)))))
740
741(define (Within eps seq)
742  (let loop ((seq seq))
743    (let ((a (Ref 0 seq)) (b (Ref 1 seq)))
744      (if (< (abs (- a b)) eps)
745        b
746        (loop (Rest seq))))))
747
748(define (Relative eps seq)
749  (let loop ((seq seq))
750    (let ((a (Ref 0 seq)) (b (Ref 1 seq)))
751      (if (<= (abs (/ a b)) (* (abs b) eps))
752        b
753        (loop (Rest seq))))))
754
755(define (Newton x) ; fixed point for square root
756  (lambda (a) (/ (+ a (/ x a)) 2)))
757
758(define (Sums seq) ; List of sums
759  (letrec ((sums (Cons 0 (Map + seq (Lazy (Length seq) sums)))))
760    (Rest sums)))
761
762(define (First-five) (List 0 1 2 3 4))
763(define (Fibs)
764  (Append (List 0 1) (Lazy #f (Map + (Rest (Fibs)) (Fibs)))))
765
766(define port (open-input-file "lazy-lists.scm"))
767(define input (input->List port read-line))
768
769(run
770  (= (Length (First-five)) 5)
771  (= (Length (Rest (First-five))) 4)
772  (->> (Cardinals) (Rest) (Length) (eq? #f))
773  (->> (Cardinals) (Take 5) (Length) (= 5))
774  (->> (Cardinals) (Length) (eq? #f))
775  (->> (Cardinals) (Drop 5) (Length) (eq? #f))
776  (->> (Cardinals) (Drop 5) (First) (= 5))
777  (->> (First-five) (List->list) (equal? '(0 1 2 3 4)))
778  (->> (Cardinals) (Take 5) (List->list) (equal? '(0 1 2 3 4)))
779  (->> (Interval 2 10) (Length) (= (- 10 2)))
780  (->> (Interval 2 10) (List->list) (equal? '(2 3 4 5 6 7 8 9)))
781  (->> (Interval 10 2) (List->list) (equal? '(10 9 8 7 6 5 4 3)))
782  (equal?
783    (receive (head index tail) (Split-with (cut = <> 3) (First-five))
784      (cons (First tail) (List->list head)))
785    '(3 0 1 2))
786  (equal?
787    (receive (head index tail) (Split-with (cut = <> 5) (Take 10 (Cardinals)))
788      (append (List->list tail) (List->list head)))
789    '(5 6 7 8 9 0 1 2 3 4))
790  (->> (First-five) (Index (cut = <> 2)) (= 2))
791  (->> (First-five) (Index (cut = <> 20)) (= 5))
792  (->> (Cardinals) (Take 10) (Take-upto (cut = <> 5)) (List->list)
793       (equal? '(0 1 2 3 4)))
794  (->> (Cardinals) (Take 10) (Take-upto (cut = <> 5)) (Length) (= 5))
795  (->> (Cardinals) (Take 10) (Drop-upto (cut = <> 5)) (Length) (= 5))
796  (->> (Cardinals) (Take 10) (Drop-upto (cut = <> 5)) (First) (= 5))
797  (->> (First-five) (Drop-upto (cut = <> 2)) (Length) (= 3))
798  (->> (First-five) (Drop-upto (cut = <> 2)) (First) (= 2))
799  (->> (First-five) (Memp odd?) (List->list) (equal? '(1 2 3 4)))
800  (->> (Cardinals) (Take 10) (Memv 5) (List->list) (equal? '(5 6 7 8 9)))
801  (->> (Cardinals) (Map (lambda (x) (list x x))) (Take 10) (Assv 5)
802       (equal? '(5 5)))
803  (->> (First-five) (Map (lambda (x) (list x x))) (Assv 10)
804       (eq? #f))
805  (->> (Cardinals) (Equal? (Cardinals)) (eq? #f))
806  (->> (Cardinals) (Equal? (First-five)) (eq? #f))
807  (->> (First-five) (Equal? (First-five)) (eq? #t))
808  (->> (Cardinals) (Take 10) (Length) (= 10))
809  (->> (Cardinals) (Drop 1) (Filter odd?) (Take 5) (List->list)
810       (equal? '(1 3 5 7 9)))
811  (->> (Cardinals) (Length) (eq? #f))
812  (->> (First-five) (Map add1) (List->list) (equal? '(1 2 3 4 5)))
813  (->> (Map + (First-five) (Take 5 (Cardinals))) (List->list)
814       (equal? '(0 2 4 6 8)))
815  (->> (Map + (Cardinals) (Cardinals)) (Length) (eq? #f))
816  (->> (Filter odd? (First-five)) (Length) (= 2))
817  (->> (Filter odd? (First-five)) (List->list) (equal? '(1 3)))
818  (->> (Filter odd? (Cardinals)) (Length) (eq? #f))
819  (->> (Zip (Cardinals) (Cardinals)) (Sieve =) (Ref 20) (= 20))
820  (->> (Zip (First-five) (First-five)) (Sieve =) (List->list)
821       (equal? '(0 1 2 3 4)))
822  (->> (Ref 25 (Cardinals)) (= 25))
823  (->> (Ref 2 (First-five)) (= 2))
824  (->> (Repeat #f) (Take 3) (List->list) (equal? '(#f #f #f)))
825  (->> (Repeatedly (lambda () 1))(Take 3)  (List->list)
826       (equal? '(1 1 1)))
827  (->> (Iterate add1 0) (Take 3) (List->list) (equal? '(0 1 2)))
828  (->> (Iterate add1 0) (Length) (eq? #f))
829  (->> (Append (First-five) (First-five)) (Length) (= 10))
830  (->> (Append (First-five) (First-five)) (List->list)
831       (equal? '(0 1 2 3 4 0 1 2 3 4)))
832  (->> (Append (First-five) (Cardinals)) (Take 12) (List->list)
833       (equal? '(0 1 2 3 4 0 1 2 3 4 5 6)))
834  (->> (Append (First-five) (Cardinals)) (Length) (eq? #f))
835  (->> (First-five) (Reverse) (List->list) (equal? '(4 3 2 1 0)))
836  (->> (Cardinals) (Take 5) (Reverse) (List->list) (equal? '(4 3 2 1 0)))
837  (->> (First-five) (Reverse) (Length) (= 5))
838  (->> (Cardinals) (Reverse*) (Length) (eq? #f))
839  (->> (Cardinals) (Reverse*) (Ref 5) (List->list) (equal? '(5 4 3 2 1 0)))
840  (->> (Cycle (First-five)) (Take 10) (List->list)
841       (equal? '(0 1 2 3 4 0 1 2 3 4)))
842  (->> (Cycle (First-five)) (Length) (eq? #f))
843  (->> (Sort < (First-five)) (List->list) (equal? '(0 1 2 3 4)))
844  (->> (Sort < (First-five)) (Length) (= 5))
845  (->> (Sort < (List 3 1 0 2 4)) (List->list) (equal? '(0 1 2 3 4)))
846  (equal?
847    (receive (head tail) (Split-at 5 (Cardinals))
848      (cons (First tail) (List->list head)))
849    '(5 0 1 2 3 4))
850  (equal?
851    (receive (head tail) (Split-at 15 (Take 5 (Cardinals)))
852      (append (List->list tail) (List->list head)))
853    '(0 1 2 3 4))
854  (->> (Cardinals) (Take 5) (Fold-left + 0) (= 10))
855  (->> (Fold-left + 0 (First-five) (First-five)) (= 20))
856  (->> (List 1 2 3 4) (Fold-left * 1) (= 24))
857  (->> (Cardinals) (Take 5) (Fold-left cons '())
858       (equal? '(((((() . 0) . 1) . 2) . 3) . 4)))
859  (->> (Cardinals) (Fold-left* cons '()) (Ref 4)
860       (equal? '(((((() . 0) . 1) . 2) . 3) . 4)))
861  (->> (Cardinals) (Take 5) (Fold-right + 0) (= 10))
862  (->> (Fold-right + 0 (First-five) (First-five)) (= 20))
863  (->> (First-five) (Fold-right cons '())
864       (equal? '(0 1 2 3 4))) ; list
865  (->> (First-five) (Fold-right cons '(a b c))
866       (equal? '(0 1 2 3 4 a b c))) ; append
867  (->> (Cardinals) (Fold-right* cons '()) (Ref 4)
868       (equal? '(4 3 2 1 0))) ; note changed order
869  (->> (Cardinals) (Fold-right* cons-right '()) (Ref 4)
870       (equal? '(0 1 2 3 4)))
871  (->> (Cardinals) (Fold-right* cons '(a b c)) (Ref 4)
872       (equal? '(4 3 2 1 0 a b c))) ; note changed order
873  (->> (Cardinals) (Fold-right* cons-right '(a b c)) (Ref 4)
874       (equal? '(a b c 0 1 2 3 4)))
875  (->> (vector->List '#(0 1 2 3 4)) (List->list) (equal? '(0 1 2 3 4)))
876  (->> (vector->List '#()) (Null?))
877  (->> (Take 5 (Cardinals)) (List->vector) (equal? '#(0 1 2 3 4)))
878  (->> (List->vector (First-five)) (equal? '#(0 1 2 3 4)))
879  (->> (List->vector Nil) (equal? '#()))
880  (->> (Filter odd? (Cardinals)) (Take 15) (Every? odd?)
881       (eq? #t))
882  (->> (Take 15 (Cardinals)) (Every? odd?)
883       (eq? #f))
884  (->> (Every? odd? Nil) (eq? #t))
885  (->> (Some? odd? Nil) (eq? #f))
886  (->> (Filter even? (Cardinals)) (Take 5) (Some? odd?)
887       (eq? #f))
888  (->> (Some? odd? (First-five)) (eq? #t))
889  (->> (Zip (Cardinals) (First-five)) (Length) (eq? #f))
890  (->> (Zip (First-five) (Cardinals)) (Length) (eq? #f))
891  (->> (Zip (Cardinals) (Cardinals)) (Length) (eq? #f))
892  (->> (Zip (Cardinals) (First-five)) (Take 14)
893       (Eqv? (List 0 0 1 1 2 2 3 3 4 4 5 6 7 8)))
894  (->> (Zip (Cardinals) (Cardinals)) (Take 14)
895       (Eqv? (List 0 0 1 1 2 2 3 3 4 4 5 5 6 6)))
896  (->> (Zip (First-five) (First-five)) (Length) (= 10))
897  (->> (Zip (First-five) (First-five))
898       (Eqv? (List 0 0 1 1 2 2 3 3 4 4)))
899  (->> (Primes) (Ref 50) (= 233))
900  (->> (Primes) (Take 5) (Eqv? (List 2 3 5 7 11)))
901  (->> (Fibs) (Take 10) (Eqv? (List  0 1 1 2 3 5 8 13 21 34)))
902  ;; compute square root
903  (let ((eps 0.000001))
904    (< (abs (- (sqrt 2) (Within eps (Iterate (Newton 2) 2)))) eps))
905  (->> (First-five) (Sums) (List->list) (equal? '(0 1 3 6 10)))
906  )
907
908</enscript>
909
910== Author
911
912[[/users/juergen-lorenz|Juergen Lorenz]]
913
914== Initial version
915
916Aug 1, 2012
917
918== Updated
919
920Aug 2, 2012
921
922== License
923
924 Copyright (c) 2012, Juergen Lorenz
925 All rights reserved.
926
927Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
928
929Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
930
931Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.  Neither the name of the author nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
932
933THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
934
935== Version History
936
937 0.1 : initial import
938
Note: See TracBrowser for help on using the repository browser.