Changeset 33877 in project
 Timestamp:
 03/04/17 18:25:27 (9 months ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

wiki/eggref/4/lazylists
r31806 r33877 10 10 procedure calls with large list arguments. On the other hand such a 11 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 of15 the two Scheme primitives delay and force (cf. the classic "Structure12 demonstrated by purely functional languages like Miranda or Haskell. 13 14 The traditional tools for the implementation of lazy evaluation consist 15 of the two Scheme primitives delay and force (cf. the classic "Structure 16 16 and Interpretation of Computer Porgrams" by Abelson and Sussman, usually 17 17 abbreveated "SICP"). But there is a better method as shown by Moritz 18 Heidkamp in his lazyseq Module, which in turn is meant to replace the18 Heidkamp in his lazyseq module, which in turn is meant to replace the 19 19 stream datatype in SRFI41. Moritz' approach is inspired by the Lisp 20 20 dialect Clojure, which also motivated the beautiful macros in his 21 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 it will be realized only if and as much as used. 22 lazy list in a record type, but to realize resulting record only as much 23 as needed. This way a large (even infinite) list can be created 24 instantaneously without realizing it and it will be realized only if and 25 as much as used. 25 26 26 27 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 be28 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 lengthof a list at the moment of its creation, lazy28 addition: A boolean named finite? is stored in the record type and can 29 thus be referenced without realizing the resulting record. After all, 30 some operations like reverse are only meaningful for finite lists, so 31 one must know beforehand if a list is finite to avoid infinite loops. 32 33 But knowing the finiteness of a list at the moment of its creation, lazy 33 34 lists can replace ordinary lists as a datatype. And ordinary list 34 35 operations can be replaced by lazy list operations. This is the reason 35 36 for the other difference of this module with Moritz' lazyseq, a 36 37 cosmetic difference: Lazy list operations are named with the same name 37 as ordinary ones, only capitalized at the beginning. So Cons, Car, Cdr38 ... are the replacements of cons,car, cdr etc. Some operators have a38 as ordinary ones, only capitalized at the beginning. So accessors Car, 39 Cdr ... are the replacements of car, cdr etc. Some operators have a 39 40 different argument order, thow, so that the clojurian chaining macro >> 40 41 works well. The consistent argument order is as follows: procedure 41 arguments appear first, lazy list arguments last. For example ( Refn Lst)42 arguments appear first, lazy list arguments last. For example (At n Lst) 42 43 replaces (listref lst n), (Drop n Lst) replaces (listtail lst n), etc. 44 But (Listref Lst n) and (Listtail Lst n) is still there for 45 convenience, but discouraged. 43 46 44 Storing the length in the list record has another advantage: One can45 check the type and finiteness of lazylist argumentsat the start of a46 routine. One could use the assert for that, but that would mean to47 al ways do all checks provided you don't compile in unsafe mode, which48 makes all code unsafe. So I provided another macro instead, assumein, 49 which does any errorchecking only if a special feature, 50 assumptionschecked, isregisterd.47 Storing the finiteness in the list record type has another advantage: 48 One can check finiteness of a lazy list argument at the start of a 49 routine. One could use assert for that, but that would mean to always do 50 all checks provided you don't compile in unsafe mode, which makes all 51 code unsafe. So I provided another macro instead, assumein, which does 52 any errorchecking only if a special feature, assumptionschecked, is 53 registerd. 51 54 52 55 ==== lazylists … … 60 63 ==== makelazy 61 64 62 <procedure>(Makelazy len thunk)</procedure> 63 64 lazy constructor. len is either a notnegative fixnum or #f for infinite 65 Lists 65 <procedure>(Makelazy finite? thunk)</procedure> 66 67 lazy constructor. 66 68 67 69 ==== Lazy 68 70 69 <syntax>(Lazy lenxpr . xprs)</syntax>71 <syntax>(Lazy finite? xpr . xprs)</syntax> 70 72 71 73 convenience wrapper to Makelazy constructor, avoiding a thunk. … … 110 112 111 113 checks if n is an admissible index for the lazylist Lst. 114 Deprecated, makes finite Lists eager. Moreover traverses a List twice, 115 when used in a check 112 116 113 117 ==== Length … … 121 125 <procedure>(Cons var Lst)</procedure> 122 126 123 lazy version of cons 127 lazy version of cons. 128 Deprecated, use (Lazy finite? (cons var Lst)) instead 124 129 125 130 ==== Rest … … 147 152 lazy version of car 148 153 149 ==== Ref150 151 <procedure>( Refn Lst)</procedure>154 ==== At 155 156 <procedure>(At n Lst)</procedure> 152 157 153 158 lazy version of listref with changed argument order, realizing the Lst 154 159 argument upto n. 155 160 161 ==== Ref 162 163 <procedure>(Ref n Lst)</procedure> 164 165 alias for At, deprecated. 166 156 167 ==== Null? 157 168 … … 187 198 ==== Foldright* 188 199 189 <procedure>(Foldright* op base . Lsts)</procedure>200 <procedure>(Foldright* op base Lst . Lsts)</procedure> 190 201 191 202 create a lazy list of right folds changing order or List items … … 193 204 ==== Foldleft* 194 205 195 <procedure>(Foldleft* op base . Lsts)</procedure>206 <procedure>(Foldleft* op base Lst . Lsts)</procedure> 196 207 197 208 create a lazy list of left folds … … 199 210 ==== Foldright 200 211 201 <procedure>(Foldright op base . Lsts)</procedure>212 <procedure>(Foldright op base Lst . Lsts)</procedure> 202 213 203 214 lazy version of foldright, one of the Lsts must be finite. … … 205 216 ==== Foldleft 206 217 207 <procedure>(Foldleft op base . Lsts)</procedure>218 <procedure>(Foldleft op base Lst . Lsts)</procedure> 208 219 209 220 lazy version of foldleft, one of the Lsts must be finite. … … 283 294 one to be appended. 284 295 296 ==== Range 297 298 <procedure>(Range [from] upto [step])</procedure> 299 300 List of integers from (included) upto (excluded) with step 301 285 302 ==== Iterate 286 303 287 <procedure>(Iterate [n] proc x)</procedure>288 289 create finite List of Length n or infinite List by applying procsuccesively to x304 <procedure>(Iterate fn x [times])</procedure> 305 306 create finite List of Length times or infinite List by applying fn succesively to x 290 307 291 308 ==== Repeatedly 292 309 293 <procedure>(Repeatedly [n] thunk)</procedure>294 295 create finite List of Length nor infinite List of return values of thunk310 <procedure>(Repeatedly thunk [times])</procedure> 311 312 create finite List of Length times or infinite List of return values of thunk 296 313 297 314 ==== Repeat 298 315 299 <procedure>(Repeat [n] x)</procedure>300 301 create finite List of Length nor infinite List of x316 <procedure>(Repeat x [times])</procedure> 317 318 create finite List of Length times or infinite List of x 302 319 303 320 ==== input>List … … 493 510 494 511 lazy list of non negative integers 495 496 ==== Interval497 498 <procedure>(Interval from upto)</procedure>499 500 List of integers from (included) upto (excluded)501 512 502 513 ==== assumein … … 520 531 <enscript highlight=scheme> 521 532 522 (requirelibrary lazylists multimethods)523 (import lazylists methods)533 (requirelibrary lazylists) 534 (import lazylists) 524 535 525 536 (define (consright var lst) … … 530 541 (define (Within eps Lst) 531 542 (let loop ((Lst Lst)) 532 (let ((a ( Ref 0 Lst)) (b (Ref1 Lst)))543 (let ((a (At 0 Lst)) (b (At 1 Lst))) 533 544 (if (< (abs ( a b)) eps) 534 545 b … … 537 548 (define (Relative eps Lst) 538 549 (let loop ((Lst Lst)) 539 (let ((a ( Ref 0 Lst)) (b (Ref1 Lst)))550 (let ((a (At 0 Lst)) (b (At 1 Lst))) 540 551 (if (<= (abs (/ a b)) (* (abs b) eps)) 541 552 b … … 546 557 547 558 (define (Sums Lst) ; List of sums 548 (letrec ((sums (Cons 0 (Map + Lst (Lazy (Length Lst) sums))))) 549 (Rest sums))) 559 (let loop ((n 1)) 560 (Lazy #f (cons (apply + (List>list (Take n Lst))) 561 (loop (fx+ n 1)))))) 550 562 551 563 (define (Firstfive) (List 0 1 2 3 4)) … … 563 575 (List>list (Firstfive)) ;> '(0 1 2 3 4) 564 576 (List>list (Take 5 (Cardinals))) ;> '(0 1 2 3 4) 565 (Length ( Interval2 10)) ;> ( 10 2)566 (List>list ( Interval2 10)) ;> '(2 3 4 5 6 7 8 9)567 (List>list ( Interval10 2)) ;> '(10 9 8 7 6 5 4 3)577 (Length (Range 2 10)) ;> ( 10 2) 578 (List>list (Range 2 10)) ;> '(2 3 4 5 6 7 8 9) 579 (List>list (Range 10 2)) ;> '(10 9 8 7 6 5 4 3) 568 580 (receive (head index tail) (Splitwith (cut < <> 3) (Firstfive)) 569 581 (cons (First tail) (List>list head))) ;> '(3 0 1 2) 570 582 (receive (head index tail) (Splitwith (cut < <> 5) (Take 10 (Cardinals))) 571 583 (append (List>list tail) (List>list head))) ;> '(5 6 7 8 9 0 1 2 3 4) 572 584 (Index (cut = <> 2) (Firstfive)) ;> 2 573 585 (Index (cut = <> 20) (Firstfive)) ;> 5 … … 598 610 (List>list (Filter odd? (Firstfive))) ;> '(1 3) 599 611 (Length (Filter odd? (Cardinals))) ;> #f 600 ( Ref20 (Sieve = (Zip (Cardinals) (Cardinals)))) ;> 20612 (At 20 (Sieve = (Zip (Cardinals) (Cardinals)))) ;> 20 601 613 (List>list (Sieve = (Zip (Firstfive) (Firstfive)))) 602 614 ;> '(0 1 2 3 4) 603 ( Ref25 (Cardinals)) ;> 25604 ( Ref2 (Firstfive)) ;> 2615 (At 25 (Cardinals)) ;> 25 616 (At 2 (Firstfive)) ;> 2 605 617 (List>list (Take 3 (Repeat #f))) ;> '(#f #f #f) 606 618 (List>list (Take 3 (Repeatedly (lambda () 1)))) … … 618 630 (Length (Reverse (Firstfive))) ; > 5 619 631 (Length (Reverse* (Cardinals))) ; > #f 620 (List>list ( Ref5 (Reverse* (Cardinals)))) ; > '(5 4 3 2 1 0)632 (List>list (At 5 (Reverse* (Cardinals)))) ; > '(5 4 3 2 1 0) 621 633 (List>list (Take 10 (Cycle (Firstfive)))) 622 634 ; > '(0 1 2 3 4 0 1 2 3 4) … … 636 648 (Foldleft cons '() (Take 5 (Cardinals))) 637 649 ; > '(((((() . 0) . 1) . 2) . 3) . 4) 638 ( Ref4 (Foldleft* cons '() (Cardinals)))650 (At 4 (Foldleft* cons '() (Cardinals))) 639 651 ; > '(((((() . 0) . 1) . 2) . 3) . 4) 640 652 (Foldright + 0 (Take 5 (Cardinals))) ; > 10 … … 646 658 (Foldright cons '(a b c) (Firstfive)) 647 659 ; > '(0 1 2 3 4 a b c) 648 ( Ref4 (Foldright* cons '() (Cardinals)))660 (At 4 (Foldright* cons '() (Cardinals))) 649 661 ; > '(4 3 2 1 0)) ; note changed order 650 ( Ref4 (Foldright* consright '() (Cardinals)))662 (At 4 (Foldright* consright '() (Cardinals))) 651 663 ; > '(0 1 2 3 4) 652 ( Ref4 (Foldright* cons '(a b c) (Cardinals)))664 (At 4 (Foldright* cons '(a b c) (Cardinals))) 653 665 ; > '(4 3 2 1 0 a b c) ; note changed order 654 ( Ref4 (Foldright* consright '(a b c) (Cardinals)))666 (At 4 (Foldright* consright '(a b c) (Cardinals))) 655 667 ; > '(a b c 0 1 2 3 4) 656 668 (List>list (vector>List '#(0 1 2 3 4))) ; > '(0 1 2 3 4) … … 675 687 (Eqv? (Zip (Firstfive) (Firstfive)) 676 688 (List 0 0 1 1 2 2 3 3 4 4)) ; > #t 677 ( Ref50 (Primes)) ; > 233689 (At 50 (Primes)) ; > 233 678 690 (Eqv? (Take 5 (Primes)) (List 2 3 5 7 11)) ; > #t 679 691 (Eqv? (Take 10 (Fibs)) (List 0 1 1 2 3 5 8 13 21 34)) ; > #t … … 681 693 (let ((eps 0.000001)) 682 694 (< (abs ( (sqrt 2) (Within eps (Iterate (Newton 2) 2)))) eps)) ; > #t 683 (List>list (Sums ( Firstfive))) ; > '(0 1 3 6 10)695 (List>list (Sums (Take 5 (Cardinals)))) ; > '(0 1 3 6 10) 684 696 685 697 </enscript> … … 695 707 == Updated 696 708 697 Nov 10, 2014 709 Mar 03, 2017 698 710 699 711 == License 700 712 701 Copyright (c) 2012201 4, Juergen Lorenz, Moritz Heidkamp713 Copyright (c) 20122017, Juergen Lorenz 702 714 All rights reserved. 703 715 … … 730 742 == Version History 731 743 744 ; 0.9 : replaced length slot with finite? slot to keep lazyness of finite lists 732 745 ; 0.8.1 : fixed bug in documentation procedure lazylists 733 746 ; 0.8 : new procedures lazylists Unzip Remp Remove Remq Remv
Note: See TracChangeset
for help on using the changeset viewer.