1 | [[tags: egg]] |
---|
2 | [[toc:]] |
---|
3 | |
---|
4 | == Lazy lists |
---|
5 | |
---|
6 | Lists in Scheme and Lisp are eager. Since the procedure calling regime |
---|
7 | in these languages is "Call by value", a list argument of a procedure |
---|
8 | call is completely constructed before the procedure is called. This is |
---|
9 | fine for small lists, but it excludes practically the chaining of |
---|
10 | procedure calls with large list arguments. On the other hand such a |
---|
11 | chaining is a tremendously powerful modularization technique, as |
---|
12 | demonstrated by purely functional languages like Haskell. |
---|
13 | |
---|
14 | The traditional tools for implementation of lazy evaluation consist of |
---|
15 | the two Scheme primitives delay and force (cf. the classic "Structure |
---|
16 | and Interpretation of Computer Porgrams" by Abelson and Sussman, usually |
---|
17 | abbreveated "SICP"). But there is a better method as shown by Moritz |
---|
18 | Heidkamp in his lazy-seq Module, which in turn is meant to replace the |
---|
19 | stream datatype in SRFI-41. Moritz' approach is inspired by the Lisp |
---|
20 | dialect Clojure, which also motivated the beautiful macros in his |
---|
21 | clojurian module. The fundamental idea is to store the structure of a |
---|
22 | lazy list in a record, but to realize this list only as much as needed. |
---|
23 | This way a large (even infinite) list can be created instantaneously |
---|
24 | without realizing it and will be realized only if and as much as used. |
---|
25 | |
---|
26 | This module is based on Heidkamp's implementation with one essential |
---|
27 | addition: The length of the list is stored in the record and can thus be |
---|
28 | referenced without realizing the whole list. After all, some operations |
---|
29 | like reverse are only meaningful for finite lists, so one must know |
---|
30 | beforehand if a list is finite to avoid infinite loops. |
---|
31 | |
---|
32 | But knowing the length of a list at the moment of its creation, lazy |
---|
33 | lists can replace ordinary lists as a datatype. And ordinary list |
---|
34 | operations can be replaced by lazy list operations. This is the reason |
---|
35 | for the other difference of this module with Moritz' lazy-seq, a |
---|
36 | cosmetic difference: Lazy list operations are named with the same name |
---|
37 | as ordinary ones, only capitalized at the beginning. So Cons, Car, Cdr |
---|
38 | ... are the replacements of cons, car, cdr etc. Some operators have a |
---|
39 | different argument order, thow, so that the clojurian chaining macro ->> |
---|
40 | works well. The consistent argument order is as follows: procedure |
---|
41 | argument appear first, lazy list arguments last. For example (Ref n seq) |
---|
42 | replaces (list-ref seq n), (Drop n seq) replaces (list-tail seq n), etc. |
---|
43 | |
---|
44 | Storing the length in the list record has another advantage: I can and |
---|
45 | will use my own contracts module to guard the implementation of the |
---|
46 | routines by contracts, i.e. pre- and postconditions. This allows to |
---|
47 | implement the routines proper without any defences - this is done in the |
---|
48 | module %lazy-lists - and wrap each call with the contract in the |
---|
49 | lazy-lists module. In other words, both modules have exactly the same |
---|
50 | interface (with one exception: the documentation procedure lazy-lists in |
---|
51 | the latter). The routines of the former are imported into the latter |
---|
52 | with the prefix %, so that they can be used there without contracts. |
---|
53 | |
---|
54 | Remember, that modules written in the design-by-contract style have |
---|
55 | their 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 | |
---|
64 | The first call returns all available routines, the second documentation |
---|
65 | and 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 | |
---|
76 | lazy constructor |
---|
77 | |
---|
78 | === Lazy |
---|
79 | |
---|
80 | <syntax> |
---|
81 | (Lazy len xpr . xprs) |
---|
82 | </syntax> |
---|
83 | |
---|
84 | wrapper to make-lazy constructor |
---|
85 | |
---|
86 | |
---|
87 | === List? |
---|
88 | |
---|
89 | <enscript highlight=scheme> |
---|
90 | (List? xpr) |
---|
91 | (range (boolean? result)) |
---|
92 | </enscript> |
---|
93 | |
---|
94 | lazy 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 | |
---|
104 | lazy 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 | |
---|
114 | lazy 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 | |
---|
124 | lazy 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 | |
---|
134 | lazy version of cdr |
---|
135 | |
---|
136 | === First |
---|
137 | |
---|
138 | <enscript highlight=scheme> |
---|
139 | (First seq) |
---|
140 | (domain (%List? seq) (not (%Null? seq))) |
---|
141 | </enscript> |
---|
142 | |
---|
143 | lazy version of car |
---|
144 | |
---|
145 | === Car |
---|
146 | |
---|
147 | <enscript highlight=scheme> |
---|
148 | (Car seq) |
---|
149 | (domain (%List? seq) (not (%Null? seq))) |
---|
150 | </enscript> |
---|
151 | |
---|
152 | lazy 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 | |
---|
161 | lazy 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 | |
---|
171 | lazy 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 | |
---|
181 | interleave 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 | |
---|
190 | does 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 | |
---|
199 | does 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 | |
---|
209 | create 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 | |
---|
219 | create 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 | |
---|
228 | lazy 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 | |
---|
237 | lazy 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 | |
---|
247 | sieve 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 | |
---|
257 | split 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 | |
---|
267 | split 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 | |
---|
277 | transform 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 | |
---|
287 | transform 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 | |
---|
297 | sort 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 | |
---|
307 | merge 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 | |
---|
317 | create 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 | |
---|
327 | List 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 | |
---|
337 | lazy 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 | |
---|
347 | lazy 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 | |
---|
357 | create 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 | |
---|
367 | create 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 | |
---|
376 | create 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 | |
---|
386 | transform 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 | |
---|
395 | lazy 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 | |
---|
405 | lazy 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 | |
---|
415 | lazy 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 | |
---|
425 | lazy 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 | |
---|
435 | lazy 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 | |
---|
445 | lazy 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 | |
---|
455 | return #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 | |
---|
465 | lazy 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 | |
---|
475 | lazy 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 | |
---|
485 | lazy 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 | |
---|
495 | compare 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 | |
---|
505 | lazy 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 | |
---|
515 | lazy 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 | |
---|
525 | lazy 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 | |
---|
535 | Tail 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 | |
---|
545 | return 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 | |
---|
555 | Tail 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 | |
---|
565 | List 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 | |
---|
575 | lazy 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 | |
---|
585 | List 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 | |
---|
594 | lazy 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 | |
---|
604 | transform 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 | |
---|
614 | transform 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 | |
---|
624 | Is seq realized? |
---|
625 | |
---|
626 | === Primes |
---|
627 | |
---|
628 | <enscript highlight=scheme> |
---|
629 | (Primes) |
---|
630 | (range (%List? result) (not (%Length result))) |
---|
631 | </enscript> |
---|
632 | |
---|
633 | lazy 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 | |
---|
642 | lazy 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 | |
---|
652 | List 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 | |
---|
858 | Aug 1, 2012 |
---|
859 | |
---|
860 | == Updated |
---|
861 | |
---|
862 | == License |
---|
863 | |
---|
864 | Copyright (c) 2012, Juergen Lorenz |
---|
865 | All rights reserved. |
---|
866 | |
---|
867 | Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: |
---|
868 | |
---|
869 | Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. |
---|
870 | |
---|
871 | Redistributions 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 | |
---|
873 | THIS 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 | |
---|