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

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

lazy-lists added

File size: 25.2 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
41argument 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 defences - 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<enscript highlight=scheme>
60(lazy-lists)
61(lazy-list 'List)
62</enscript>
63
64The first call returns all available routines, the second documentation
65and contract of the symbol List
66
67
68=== make-lazy
69
70<enscript highlight=scheme>
71(make-lazy len thunk)
72(domain (or (not len) (and (integer? len) (not (negative? len)))) (procedure? thunk) thunk returns either '(), a List or (cons val List))
73(range (%List? result) (= (%Length result) len))
74</enscript>
75
76lazy constructor
77
78=== Lazy
79
80<syntax>
81(Lazy len xpr . xprs)
82</syntax>
83
84wrapper to make-lazy constructor
85
86
87=== List?
88
89<enscript highlight=scheme>
90(List? xpr)
91(range (boolean? result))
92</enscript>
93
94lazy version of list?
95
96=== Length
97
98<enscript highlight=scheme>
99(Length seq)
100(domain (%List? seq))
101(range (or (not result) (and (integer? result) (not (negative? result)))))
102</enscript>
103
104lazy version of length
105
106=== Cons
107
108<enscript highlight=scheme>
109(Cons var seq)
110(domain (%List? seq))
111(range (%List? result) (or (not (%Length seq)) (= (%Length result) (+ (%Length seq) 1))))
112</enscript>
113
114lazy version of cons
115
116=== Rest
117
118<enscript highlight=scheme>
119(Rest seq)
120(domain (%List? seq) (not (%Null? seq)))
121(range (%List? result) (or (not (%Length seq)) (= (%Length result) (- (%Length seq) 1))))
122</enscript>
123
124lazy version of cdr
125
126=== Cdr
127
128<enscript highlight=scheme>
129(Cdr seq)
130(domain (%List? seq) (not (%Null? seq)))
131(range (%List? result) (or (not (%Length seq)) (= (%Length result) (- (%Length seq) 1))))
132</enscript>
133
134lazy version of cdr
135
136=== First
137
138<enscript highlight=scheme>
139(First seq)
140(domain (%List? seq) (not (%Null? seq)))
141</enscript>
142
143lazy version of car
144
145=== Car
146
147<enscript highlight=scheme>
148(Car seq)
149(domain (%List? seq) (not (%Null? seq)))
150</enscript>
151
152lazy version of car
153
154=== Ref
155
156<enscript highlight=scheme>
157(Ref n seq)
158(domain (%List? seq) (integer? n) (or (not (%Length seq)) (< -1 n (%Length seq))))
159</enscript>
160
161lazy version of list-ref with changed argument order
162
163=== Null?
164
165<enscript highlight=scheme>
166(Null? seq)
167(domain (%List? seq))
168(range (boolean? result))
169</enscript>
170
171lazy version of null?
172
173=== Zip
174
175<enscript highlight=scheme>
176(Zip seq1 seq2)
177(domain (%List? seq1) (%List? seq2))
178(range (%List? result) (if (and (%Length seq1) (%Length seq2)) (= (%Length result) (+ (%Length seq1) (%Length seq2))) (not (%Length result))))
179</enscript>
180
181interleave two lazy lists
182
183=== Some?
184
185<enscript highlight=scheme>
186(Some? ok? seq)
187(domain (%List? seq) (%Length seq) (procedure? ok?) "(ok? x)")
188</enscript>
189
190does some item of seq fulfill ok?
191
192=== Every?
193
194<enscript highlight=scheme>
195(Every? ok? seq)
196(domain (%List? seq) (%Length seq) (procedure? ok?) "(ok? x)")
197</enscript>
198
199does every item of seq fulfill ok?
200
201=== Fold-right*
202
203<enscript highlight=scheme>
204(Fold-right* op base . seqs)
205(domain (procedure? op) "(op b . ss)" ((list-of? %List?) seqs) (or (null? seqs) (all (lambda (x) (eqv? (%Length x) (%Length (car seqs)))) (cdr seqs))))
206(range (%List? result) (if (null? seqs) (not (%Length result)) (eqv? (%Length result) (%Length (car seqs)))))
207</enscript>
208
209create a lazy list of right folds changing order or List items
210
211=== Fold-left*
212
213<enscript highlight=scheme>
214(Fold-left* op base . seqs)
215(domain (procedure? op) "(op b . ss)" ((list-of? %List?) seqs) (or (null? seqs) (all (lambda (x) (eqv? (%Length x) (%Length (car seqs)))) (cdr seqs))))
216(range (%List? result) (if (null? seqs) (not (%Length result)) (eqv? (%Length result) (%Length (car seqs)))))
217</enscript>
218
219create a lazy list of left folds
220
221=== Fold-right
222
223<enscript highlight=scheme>
224(Fold-right op base seq . seqs)
225(domain (procedure? op) "(op b s . ss)" (%List? seq) ((list-of? %List?) seqs) (%Length seq) (all (lambda (x) (= (%Length x) (%Length seq))) seqs))
226</enscript>
227
228lazy version of fold-right
229
230=== Fold-left
231
232<enscript highlight=scheme>
233(Fold-left op base seq . seqs)
234(domain (procedure? op) "(op b s . ss)" (%List? seq) ((list-of? %List?) seqs) (%Length seq) (all (lambda (x) (= (%Length x) (%Length seq))) seqs))
235</enscript>
236
237lazy version of fold-left
238
239=== Sieve
240
241<enscript highlight=scheme>
242(Sieve =? seq)
243(domain (%List? seq) (procedure? =?) "(=? a b)")
244(range (%List? result) not two items =? (if (%Length seq) (<= (%Length result) (%Length seq)) (not (%Length result))))
245</enscript>
246
247sieve of Erathostenes with respect to =?
248
249=== Split-with
250
251<enscript highlight=scheme>
252(Split-with ok? seq)
253(domain (%List? seq) (%Length seq) (procedure? ok?) "(ok? x)")
254(range (with-results (head index tail) (%List? head) (%List? tail) (integer? index) (not (negative? index)) (<= (%Length head) (%Length seq)) (<= (%Length tail) (%Length seq))))
255</enscript>
256
257split a lazy list at first index fulfilling ok?
258
259=== Split-at
260
261<enscript highlight=scheme>
262(Split-at n seq)
263(domain (%List? seq) (integer? n) (not (negative? n)))
264(range (with-results (head tail) (%List? head) (%Length head) (<= (%Length head) n) (%List? tail) (if (%Length seq) (<= (%Length tail) (%Length seq)) (not (%Length tail)))))
265</enscript>
266
267split a List at fixed position
268
269=== List->vector
270
271<enscript highlight=scheme>
272(List->vector seq)
273(domain (%List? seq) (%Length seq))
274(range (vector? result) (eqv? (vector-length result) (%Length seq)))
275</enscript>
276
277transform a finite lazy list into a vector
278
279=== vector->List
280
281<enscript highlight=scheme>
282(vector->List vec)
283(domain (vector? vec))
284(range (%List? result) (eqv? (%Length result) (vector-length vec)))
285</enscript>
286
287transform a vector into a lazy list
288
289=== Sort
290
291<enscript highlight=scheme>
292(Sort <? seq)
293(domain (procedure? <?) "(<? a b)" (%List? seq) (%Length seq))
294(range (%List? result) "<? sorted" (eqv? (%Length result) (%Length seq)))
295</enscript>
296
297sort a finite lazy list with respect to <?
298
299=== Merge
300
301<enscript highlight=scheme>
302(Merge <? seq1 seq2)
303(domain (procedure? <?) "(<? a b)" (%List? seq1) (%Length seq1) <? sorted (%List? seq2) (%Length seq2) <? sorted)
304(range (%List? result) "<? sorted" (= (%Length result) (+ (%Length seq1) (%Length seq2))))
305</enscript>
306
307merge two sorted lazy lists with respect to <?
308
309=== Cycle
310
311<enscript highlight=scheme>
312(Cycle seq)
313(domain (%List? seq) (%Length seq))
314(range (%List? result) (not (%Length result)))
315</enscript>
316
317create infinite List by cycling finite List seq
318
319=== Reverse*
320
321<enscript highlight=scheme>
322(Reverse* seq)
323(domain (%List? seq))
324(range (%List? result) (eqv? (%Length result) (%Length seq)))
325</enscript>
326
327List of successive reversed subLists
328
329=== Reverse
330
331<enscript highlight=scheme>
332(Reverse seq)
333(domain (%List? seq) (%Length seq))
334(range (%List? result) (%Length result) (= (%Length result) (%Length seq)))
335</enscript>
336
337lazy version of reverse
338
339=== Append
340
341<enscript highlight=scheme>
342(Append . seqs)
343(domain ((list-of? %List?) seqs) (let ((lst (memv #f (map %Length seqs)))) (or (not lst) (<= (length lst) 1))))
344(range (%List? result) (or (not (%Length result)) (= (%Length result) (apply + (map %Length seqs)))))
345</enscript>
346
347lazy version of append
348
349=== Iterate
350
351<enscript highlight=scheme>
352(Iterate proc x)
353(domain (procedure? proc) "(proc x)")
354(range (%List? result) (not (%Length result)))
355</enscript>
356
357create infinite List by applying proc succesively to x
358
359=== Repeatedly
360
361<enscript highlight=scheme>
362(Repeatedly thunk)
363(domain (procedure? thunk))
364(range (%List? result) (not (%Length result)))
365</enscript>
366
367create infinite List of return values of thunk
368
369=== Repeat
370
371<enscript highlight=scheme>
372(Repeat x)
373(range (%List? result) (not (%Length result)))
374</enscript>
375
376create infinite List of x
377
378=== input->List
379
380<enscript highlight=scheme>
381(input->List port read-proc)
382(domain (input-port? port) (procedure? read-proc))
383(range (%List? result) (%Length result))
384</enscript>
385
386transform input port into List with read-proc
387
388=== For-each
389
390<enscript highlight=scheme>
391(For-each proc seq . seqs)
392(domain (%List? seq) ((list-of? %List?) seqs) (procedure? proc) "(proc arg . args)" (all (lambda (x) (eqv? (%Length x) (%Length seq))) seqs))
393</enscript>
394
395lazy version of for-each
396
397=== Filter
398
399<enscript highlight=scheme>
400(Filter ok? seq)
401(domain (%List? seq) (procedure? ok?) "(ok? x)")
402(range (%List? result) (or (not (%Length seq)) (<= (%Length result) (%Length seq))))
403</enscript>
404
405lazy version of filter
406
407=== Map
408
409<enscript highlight=scheme>
410(Map proc seq . seqs)
411(domain (%List? seq) ((list-of? %List?) seqs) (procedure? proc) "(proc arg . args)" (all (lambda (x) (eqv? (%Length x) (%Length seq))) seqs))
412(range (%List? result) (eqv? (%Length result) (%Length seq)))
413</enscript>
414
415lazy version of map
416
417=== Assoc
418
419<enscript highlight=scheme>
420(Assoc key aseq)
421(domain (%List? aseq) List of pairs (%Length aseq))
422(range (or (not result) (pair? result)))
423</enscript>
424
425lazy version of assoq
426
427=== Assv
428
429<enscript highlight=scheme>
430(Assv key aseq)
431(domain (%List? aseq) List of pairs (%Length aseq))
432(range (or (not result) (pair? result)))
433</enscript>
434
435lazy version of assv
436
437=== Assq
438
439<enscript highlight=scheme>
440(Assq key aseq)
441(domain (%List? aseq) List of pairs (%Length aseq))
442(range (or (not result) (pair? result)))
443</enscript>
444
445lazy version of assq
446
447=== Assp
448
449<enscript highlight=scheme>
450(Assp ok? aseq)
451(domain (%List? aseq) List of pairs (%Length aseq) (procedure? ok?) "(ok? x)")
452(range (or (not result) (pair? result)))
453</enscript>
454
455return #f or first pair, whose Car fulfills ok?
456
457=== Equal?
458
459<enscript highlight=scheme>
460(Equal? seq1 seq2)
461(domain (%List? seq1) (%List? seq2))
462(range (boolean? result))
463</enscript>
464
465lazy version of equal?
466
467=== Eqv?
468
469<enscript highlight=scheme>
470(Eqv? seq1 seq2)
471(domain (%List? seq1) (%List? seq2))
472(range (boolean? result))
473</enscript>
474
475lazy version of eqv?
476
477=== Eq?
478
479<enscript highlight=scheme>
480(Eq? seq1 seq2)
481(domain (%List? seq1) (%List? seq2))
482(range (boolean? result))
483</enscript>
484
485lazy version of eq?
486
487=== Equ?
488
489<enscript highlight=scheme>
490(Equ? =? seq1 seq2)
491(domain (%List? seq1) (%List? seq2) (procedure? =?) "(=? x y)")
492(range (boolean? result))
493</enscript>
494
495compare two Lists with predicate =?
496
497=== Member
498
499<enscript highlight=scheme>
500(Member var seq)
501(domain (%List? seq) (%Length seq))
502(range (%List? result) (<= (%Length result) (%Length seq)))
503</enscript>
504
505lazy version of member
506
507=== Memv
508
509<enscript highlight=scheme>
510(Memv var seq)
511(domain (%List? seq) (%Length seq))
512(range (%List? result) (<= (%Length result) (%Length seq)))
513</enscript>
514
515lazy version of memv
516
517=== Memq
518
519<enscript highlight=scheme>
520(Memq var seq)
521(domain (%List? seq) (%Length seq))
522(range (%List? result) (<= (%Length result) (%Length seq)))
523</enscript>
524
525lazy version of memq
526
527=== Memp
528
529<enscript highlight=scheme>
530(Memp ok? seq)
531(domain (%List? seq) (%Length seq) (procedure? ok?) (ok? x))
532(range (%List? result) (<= (%Length result) (%Length seq)))
533</enscript>
534
535Tail of items not fulfilling ok?
536
537=== Index
538
539<enscript highlight=scheme>
540(Index ok? seq)
541(domain (%List? seq) (%Length seq) (procedure? ok?) "(ok? x)")
542(range (integer? result) (not (negative? result)))
543</enscript>
544
545return index of first item fulfilling ok?
546
547=== Drop-upto
548
549<enscript highlight=scheme>
550(Drop-upto ok? seq)
551(domain (%List? seq) (%Length seq) (procedure? ok?) "(ok? x)")
552(range (%List? result) (<= (%Length result) (%Length seq)))
553</enscript>
554
555Tail of items not fulfilling ok?
556
557=== Take-upto
558
559<enscript highlight=scheme>
560(Take-upto ok? seq)
561(domain (%List? seq) (%Length seq) (procedure? ok?) "(ok? x)")
562(range (%List? result) (<= (%Length result) (%Length seq)))
563</enscript>
564
565List of head items fulfilling ok?
566
567=== Drop
568
569<enscript highlight=scheme>
570(Drop n seq)
571(domain (%List? seq) (integer? n) (not (negative? n)))
572(range (%List? result) (if (%Length seq) (= (%Length result) (max 0 (- (%Length seq) n))) (not (%Length result))))
573</enscript>
574
575lazy version of list-tail with changed argument order
576
577=== Take
578
579<enscript highlight=scheme>
580(Take n seq)
581(domain (%List? seq) (integer? n) (not (negative? n)))
582(range (%List? result) (%Length result) (if (%Length seq) (= (%Length result) (min n (%Length seq))) (= (%Length result) n)))
583</enscript>
584
585List of first n items of seq
586
587=== List
588
589<enscript highlight=scheme>
590(List . args)
591(range (%List? result) (eqv? (%Length result) (length args)))
592</enscript>
593
594lazy version of list
595
596=== list->List
597
598<enscript highlight=scheme>
599(list->List lst)
600(domain (list? lst))
601(range (%List? result) (eqv? (%Length result) (length lst)))
602</enscript>
603
604transform ordinary list into finite lazy list
605
606=== List->list
607
608<enscript highlight=scheme>
609(List->list seq)
610(domain (%List? seq) (%Length seq))
611(range (list? result))
612</enscript>
613
614transform finite lazy into ordinary list
615
616=== Realized?
617
618<enscript highlight=scheme>
619(Realized? seq)
620(domain (%List? seq))
621(range (boolean? result))
622</enscript>
623
624Is seq realized?
625
626=== Primes
627
628<enscript highlight=scheme>
629(Primes)
630(range (%List? result) (not (%Length result)))
631</enscript>
632
633lazy list of non prime numbers
634
635=== Cardinals
636
637<enscript highlight=scheme>
638(Cardinals)
639(range (%List? result) (not (%Length result)))
640</enscript>
641
642lazy list of non negative integers
643
644=== Interval
645
646<enscript highlight=scheme>
647(Interval from upto)
648(domain (integer? from) (integer? upto))
649(range (%List result) (= (%Length result) (abs (- upto from))))
650</enscript>
651
652List of integers from (included) upto (excluded)
653
654== Usage
655
656<enscript highlight=scheme>
657
658(use lazy-lists contracts)
659
660== Examples
661
662<enscript highlight=scheme>
663
664
665(require-library clojurian-syntax lazy-lists contracts)
666(import lazy-lists clojurian-syntax contracts)
667
668;;; (run xpr0 xpr1 ...)
669;;; -------------------
670(define (run . xprs)
671  (let loop ((xprs xprs))
672    (if (null? xprs)
673      (print "All tests passed!")
674      (if (car xprs)
675        (loop (cdr xprs))
676        (error 'run "#### Some test failed! ####")))))
677
678(define (cons-right var lst)
679  (if (null? lst)
680    (cons var lst)
681    (cons (car lst) (cons-right var (cdr lst)))))
682
683(define (Within eps seq)
684  (let loop ((seq seq))
685    (let ((a (Ref 0 seq)) (b (Ref 1 seq)))
686      (if (< (abs (- a b)) eps)
687        b
688        (loop (Rest seq))))))
689
690(define (Relative eps seq)
691  (let loop ((seq seq))
692    (let ((a (Ref 0 seq)) (b (Ref 1 seq)))
693      (if (<= (abs (/ a b)) (* (abs b) eps))
694        b
695        (loop (Rest seq))))))
696
697(define (Newton x) ; fixed point for square root
698  (lambda (a) (/ (+ a (/ x a)) 2)))
699
700(define (Sums seq) ; List of sums
701  (letrec ((sums (Cons 0 (Map + seq (Lazy (Length seq) sums)))))
702    (Rest sums)))
703
704(define (First-five) (List 0 1 2 3 4))
705(define (Fibs)
706  (Append (List 0 1) (Lazy #f (Map + (Rest (Fibs)) (Fibs)))))
707
708(define port (open-input-file "lazy-lists.scm"))
709(define input (input->List port read-line))
710
711(run
712  (= (Length (First-five)) 5)
713  (= (Length (Rest (First-five))) 4)
714  (->> (Cardinals) (Rest) (Length) (eq? #f))
715  (->> (Cardinals) (Take 5) (Length) (= 5))
716  (->> (Cardinals) (Length) (eq? #f))
717  (->> (Cardinals) (Drop 5) (Length) (eq? #f))
718  (->> (Cardinals) (Drop 5) (First) (= 5))
719  (->> (First-five) (List->list) (equal? '(0 1 2 3 4)))
720  (->> (Cardinals) (Take 5) (List->list) (equal? '(0 1 2 3 4)))
721  (->> (Interval 2 10) (Length) (= (- 10 2)))
722  (->> (Interval 2 10) (List->list) (equal? '(2 3 4 5 6 7 8 9)))
723  (->> (Interval 10 2) (List->list) (equal? '(10 9 8 7 6 5 4 3)))
724  (equal?
725    (receive (head index tail) (Split-with (cut = <> 3) (First-five))
726      (cons (First tail) (List->list head)))
727    '(3 0 1 2))
728  (equal?
729    (receive (head index tail) (Split-with (cut = <> 5) (Take 10 (Cardinals)))
730      (append (List->list tail) (List->list head)))
731    '(5 6 7 8 9 0 1 2 3 4))
732  (->> (First-five) (Index (cut = <> 2)) (= 2))
733  (->> (First-five) (Index (cut = <> 20)) (= 5))
734  (->> (Cardinals) (Take 10) (Take-upto (cut = <> 5)) (List->list)
735       (equal? '(0 1 2 3 4)))
736  (->> (Cardinals) (Take 10) (Take-upto (cut = <> 5)) (Length) (= 5))
737  (->> (Cardinals) (Take 10) (Drop-upto (cut = <> 5)) (Length) (= 5))
738  (->> (Cardinals) (Take 10) (Drop-upto (cut = <> 5)) (First) (= 5))
739  (->> (First-five) (Drop-upto (cut = <> 2)) (Length) (= 3))
740  (->> (First-five) (Drop-upto (cut = <> 2)) (First) (= 2))
741  (->> (First-five) (Memp odd?) (List->list) (equal? '(1 2 3 4)))
742  (->> (Cardinals) (Take 10) (Memv 5) (List->list) (equal? '(5 6 7 8 9)))
743  (->> (Cardinals) (Map (lambda (x) (list x x))) (Take 10) (Assv 5)
744       (equal? '(5 5)))
745  (->> (First-five) (Map (lambda (x) (list x x))) (Assv 10)
746       (eq? #f))
747  (->> (Cardinals) (Equal? (Cardinals)) (eq? #f))
748  (->> (Cardinals) (Equal? (First-five)) (eq? #f))
749  (->> (First-five) (Equal? (First-five)) (eq? #t))
750  (->> (Cardinals) (Take 10) (Length) (= 10))
751  (->> (Cardinals) (Drop 1) (Filter odd?) (Take 5) (List->list)
752       (equal? '(1 3 5 7 9)))
753  (->> (Cardinals) (Length) (eq? #f))
754  (->> (First-five) (Map add1) (List->list) (equal? '(1 2 3 4 5)))
755  (->> (Map + (First-five) (Take 5 (Cardinals))) (List->list)
756       (equal? '(0 2 4 6 8)))
757  (->> (Map + (Cardinals) (Cardinals)) (Length) (eq? #f))
758  (->> (Filter odd? (First-five)) (Length) (= 2))
759  (->> (Filter odd? (First-five)) (List->list) (equal? '(1 3)))
760  (->> (Filter odd? (Cardinals)) (Length) (eq? #f))
761  (->> (Zip (Cardinals) (Cardinals)) (Sieve =) (Ref 20) (= 20))
762  (->> (Zip (First-five) (First-five)) (Sieve =) (List->list)
763       (equal? '(0 1 2 3 4)))
764  (->> (Ref 25 (Cardinals)) (= 25))
765  (->> (Ref 2 (First-five)) (= 2))
766  (->> (Repeat #f) (Take 3) (List->list) (equal? '(#f #f #f)))
767  (->> (Repeatedly (lambda () 1))(Take 3)  (List->list)
768       (equal? '(1 1 1)))
769  (->> (Iterate add1 0) (Take 3) (List->list) (equal? '(0 1 2)))
770  (->> (Iterate add1 0) (Length) (eq? #f))
771  (->> (Append (First-five) (First-five)) (Length) (= 10))
772  (->> (Append (First-five) (First-five)) (List->list)
773       (equal? '(0 1 2 3 4 0 1 2 3 4)))
774  (->> (Append (First-five) (Cardinals)) (Take 12) (List->list)
775       (equal? '(0 1 2 3 4 0 1 2 3 4 5 6)))
776  (->> (Append (First-five) (Cardinals)) (Length) (eq? #f))
777  (->> (First-five) (Reverse) (List->list) (equal? '(4 3 2 1 0)))
778  (->> (Cardinals) (Take 5) (Reverse) (List->list) (equal? '(4 3 2 1 0)))
779  (->> (First-five) (Reverse) (Length) (= 5))
780  (->> (Cardinals) (Reverse*) (Length) (eq? #f))
781  (->> (Cardinals) (Reverse*) (Ref 5) (List->list) (equal? '(5 4 3 2 1 0)))
782  (->> (Cycle (First-five)) (Take 10) (List->list)
783       (equal? '(0 1 2 3 4 0 1 2 3 4)))
784  (->> (Cycle (First-five)) (Length) (eq? #f))
785  (->> (Sort < (First-five)) (List->list) (equal? '(0 1 2 3 4)))
786  (->> (Sort < (First-five)) (Length) (= 5))
787  (->> (Sort < (List 3 1 0 2 4)) (List->list) (equal? '(0 1 2 3 4)))
788  (equal?
789    (receive (head tail) (Split-at 5 (Cardinals))
790      (cons (First tail) (List->list head)))
791    '(5 0 1 2 3 4))
792  (equal?
793    (receive (head tail) (Split-at 15 (Take 5 (Cardinals)))
794      (append (List->list tail) (List->list head)))
795    '(0 1 2 3 4))
796  (->> (Cardinals) (Take 5) (Fold-left + 0) (= 10))
797  (->> (Fold-left + 0 (First-five) (First-five)) (= 20))
798  (->> (List 1 2 3 4) (Fold-left * 1) (= 24))
799  (->> (Cardinals) (Take 5) (Fold-left cons '())
800       (equal? '(((((() . 0) . 1) . 2) . 3) . 4)))
801  (->> (Cardinals) (Fold-left* cons '()) (Ref 4)
802       (equal? '(((((() . 0) . 1) . 2) . 3) . 4)))
803  (->> (Cardinals) (Take 5) (Fold-right + 0) (= 10))
804  (->> (Fold-right + 0 (First-five) (First-five)) (= 20))
805  (->> (First-five) (Fold-right cons '())
806       (equal? '(0 1 2 3 4))) ; list
807  (->> (First-five) (Fold-right cons '(a b c))
808       (equal? '(0 1 2 3 4 a b c))) ; append
809  (->> (Cardinals) (Fold-right* cons '()) (Ref 4)
810       (equal? '(4 3 2 1 0))) ; note changed order
811  (->> (Cardinals) (Fold-right* cons-right '()) (Ref 4)
812       (equal? '(0 1 2 3 4)))
813  (->> (Cardinals) (Fold-right* cons '(a b c)) (Ref 4)
814       (equal? '(4 3 2 1 0 a b c))) ; note changed order
815  (->> (Cardinals) (Fold-right* cons-right '(a b c)) (Ref 4)
816       (equal? '(a b c 0 1 2 3 4)))
817  (->> (vector->List '#(0 1 2 3 4)) (List->list) (equal? '(0 1 2 3 4)))
818  (->> (vector->List '#()) (Null?))
819  (->> (Take 5 (Cardinals)) (List->vector) (equal? '#(0 1 2 3 4)))
820  (->> (List->vector (First-five)) (equal? '#(0 1 2 3 4)))
821  (->> (List->vector Nil) (equal? '#()))
822  (->> (Filter odd? (Cardinals)) (Take 15) (Every? odd?)
823       (eq? #t))
824  (->> (Take 15 (Cardinals)) (Every? odd?)
825       (eq? #f))
826  (->> (Every? odd? Nil) (eq? #t))
827  (->> (Some? odd? Nil) (eq? #f))
828  (->> (Filter even? (Cardinals)) (Take 5) (Some? odd?)
829       (eq? #f))
830  (->> (Some? odd? (First-five)) (eq? #t))
831  (->> (Zip (Cardinals) (First-five)) (Length) (eq? #f))
832  (->> (Zip (First-five) (Cardinals)) (Length) (eq? #f))
833  (->> (Zip (Cardinals) (Cardinals)) (Length) (eq? #f))
834  (->> (Zip (Cardinals) (First-five)) (Take 14)
835       (Eqv? (List 0 0 1 1 2 2 3 3 4 4 5 6 7 8)))
836  (->> (Zip (Cardinals) (Cardinals)) (Take 14)
837       (Eqv? (List 0 0 1 1 2 2 3 3 4 4 5 5 6 6)))
838  (->> (Zip (First-five) (First-five)) (Length) (= 10))
839  (->> (Zip (First-five) (First-five))
840       (Eqv? (List 0 0 1 1 2 2 3 3 4 4)))
841  (->> (Primes) (Ref 50) (= 233))
842  (->> (Primes) (Take 5) (Eqv? (List 2 3 5 7 11)))
843  (->> (Fibs) (Take 10) (Eqv? (List  0 1 1 2 3 5 8 13 21 34)))
844  ;; compute square root
845  (let ((eps 0.000001))
846    (< (abs (- (sqrt 2) (Within eps (Iterate (Newton 2) 2)))) eps))
847  (->> (First-five) (Sums) (List->list) (equal? '(0 1 3 6 10)))
848  )
849
850</enscript>
851
852== Author
853
854[[/users/juergen-lorenz|Juergen Lorenz]]
855
856== Initial version
857
858Aug 1, 2012
859
860== Updated
861
862== License
863
864 Copyright (c) 2012, Juergen Lorenz
865 All rights reserved.
866
867Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
868
869Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
870
871Redistributions 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.
872
873THIS 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.
874
875== Version History
876
877 0.1 : initial import
878
Note: See TracBrowser for help on using the repository browser.