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 | <procedure>(lazy-lists [sym])</procedure> |
---|
60 | |
---|
61 | returns all available routines of the module when called without an |
---|
62 | argument, but when called with one of these routines as a symbol, |
---|
63 | returns 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 | |
---|
75 | lazy constructor |
---|
76 | |
---|
77 | ==== Lazy |
---|
78 | |
---|
79 | <syntax>(Lazy len xpr . xprs)</syntax> |
---|
80 | |
---|
81 | wrapper to make-lazy constructor |
---|
82 | |
---|
83 | ==== Nil |
---|
84 | |
---|
85 | empty lazy list |
---|
86 | |
---|
87 | ==== List? |
---|
88 | |
---|
89 | <procedure>(List? xpr)</procedure> |
---|
90 | |
---|
91 | <enscript highlight=scheme> |
---|
92 | (range (boolean? result)) |
---|
93 | </enscript> |
---|
94 | |
---|
95 | lazy 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 | |
---|
106 | lazy 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 | |
---|
117 | lazy 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 | |
---|
128 | lazy 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 | |
---|
139 | lazy 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 | |
---|
149 | lazy 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 | |
---|
159 | lazy 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 | |
---|
169 | lazy 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 | |
---|
180 | lazy 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 | |
---|
191 | interleave 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 | |
---|
201 | does 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 | |
---|
211 | does 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 | |
---|
222 | create 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 | |
---|
233 | create 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 | |
---|
243 | lazy 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 | |
---|
253 | lazy 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 | |
---|
264 | sieve 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 | |
---|
275 | split 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 | |
---|
286 | split 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 | |
---|
297 | transform 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 | |
---|
308 | transform 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 | |
---|
319 | sort 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 | |
---|
330 | merge 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 | |
---|
341 | create 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 | |
---|
352 | List 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 | |
---|
363 | lazy 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 | |
---|
374 | lazy 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 | |
---|
385 | create 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 | |
---|
396 | create 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 | |
---|
406 | create 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 | |
---|
417 | transform 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 | |
---|
427 | lazy 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 | |
---|
438 | lazy 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 | |
---|
449 | lazy 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 | |
---|
460 | lazy 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 | |
---|
471 | lazy 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 | |
---|
482 | lazy 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 | |
---|
493 | return #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 | |
---|
504 | lazy 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 | |
---|
515 | lazy 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 | |
---|
526 | lazy 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 | |
---|
537 | compare 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 | |
---|
548 | lazy 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 | |
---|
559 | lazy 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 | |
---|
570 | lazy 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 | |
---|
581 | Tail 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 | |
---|
592 | return 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 | |
---|
603 | Tail 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 | |
---|
614 | List 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 | |
---|
625 | lazy 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 | |
---|
636 | List 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 | |
---|
646 | lazy 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 | |
---|
657 | transform 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 | |
---|
668 | transform 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 | |
---|
679 | Is 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 | |
---|
689 | lazy 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 | |
---|
699 | lazy 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 | |
---|
710 | List 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 | |
---|
916 | Aug 1, 2012 |
---|
917 | |
---|
918 | == Updated |
---|
919 | |
---|
920 | Aug 2, 2012 |
---|
921 | |
---|
922 | == License |
---|
923 | |
---|
924 | Copyright (c) 2012, Juergen Lorenz |
---|
925 | All rights reserved. |
---|
926 | |
---|
927 | Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: |
---|
928 | |
---|
929 | Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. |
---|
930 | |
---|
931 | 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. |
---|
932 | |
---|
933 | 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. |
---|
934 | |
---|
935 | == Version History |
---|
936 | |
---|
937 | 0.1 : initial import |
---|
938 | |
---|