Changeset 33877 in project


Ignore:
Timestamp:
03/04/17 18:25:27 (7 months ago)
Author:
juergen
Message:

lazy-lists 0.9 with finite? instead of length slot

File:
1 edited

Legend:

Unmodified
Added
Removed
  • wiki/eggref/4/lazy-lists

    r31806 r33877  
    1010procedure calls with large list arguments. On the other hand such a
    1111chaining 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
     12demonstrated by purely functional languages like Miranda or Haskell.
     13
     14The traditional tools for the implementation of lazy evaluation consist
     15of the two Scheme primitives delay and force (cf. the classic "Structure
    1616and Interpretation of Computer Porgrams" by Abelson and Sussman, usually
    1717abbreveated "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
     18Heidkamp in his lazy-seq module, which in turn is meant to replace the
    1919stream datatype in SRFI-41. Moritz' approach is inspired by the Lisp
    2020dialect Clojure, which also motivated the beautiful macros in his
    2121clojurian 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.
     22lazy list in a record type, but to realize resulting record only as much
     23as needed.  This way a large (even infinite) list can be created
     24instantaneously without realizing it and it will be realized only if and
     25as much as used.
    2526
    2627This 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
     28addition: A boolean named finite? is stored in the record type and can
     29thus be referenced without realizing the resulting record. After all,
     30some operations like reverse are only meaningful for finite lists, so
     31one must know beforehand if a list is finite to avoid infinite loops.
     32
     33But knowing the finiteness of a list at the moment of its creation, lazy
    3334lists can replace ordinary lists as a datatype. And ordinary list
    3435operations can be replaced by lazy list operations. This is the reason
    3536for the other difference of this module with Moritz' lazy-seq, a
    3637cosmetic 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
     38as ordinary ones, only capitalized at the beginning. So accessors Car,
     39Cdr ... are the replacements of car, cdr etc. Some operators have a
    3940different argument order, thow, so that the clojurian chaining macro ->>
    4041works well. The consistent argument order is as follows: procedure
    41 arguments appear first, lazy list arguments last. For example (Ref n Lst)
     42arguments appear first, lazy list arguments last. For example (At n Lst)
    4243replaces (list-ref lst n), (Drop n Lst) replaces (list-tail lst n), etc.
     44But (List-ref Lst n) and (List-tail Lst n) is still there for
     45convenience, but discouraged.
    4346 
    44 Storing the length in the list record has another advantage: One can
    45 check the type and finiteness of lazy-list arguments at the start of a
    46 routine. One could use the assert for that, but that would mean to
    47 always do all checks provided you don't compile in unsafe mode, which
    48 makes all code unsafe. So I provided another macro instead, assume-in,
    49 which does any error-checking only if a special feature,
    50 assumptions-checked, is registerd.
     47Storing the finiteness in the list record type has another advantage:
     48One can check finiteness of a lazy list argument at the start of a
     49routine. One could use assert for that, but that would mean to always do
     50all checks provided you don't compile in unsafe mode, which makes all
     51code unsafe. So I provided another macro instead, assume-in, which does
     52any error-checking only if a special feature, assumptions-checked, is
     53registerd.
    5154
    5255==== lazy-lists
     
    6063==== make-lazy
    6164
    62 <procedure>(Make-lazy len thunk)</procedure>
    63 
    64 lazy constructor. len is either a not-negative fixnum or #f for infinite
    65 Lists
     65<procedure>(Make-lazy finite? thunk)</procedure>
     66
     67lazy constructor.
    6668
    6769==== Lazy
    6870
    69 <syntax>(Lazy len xpr . xprs)</syntax>
     71<syntax>(Lazy finite? xpr . xprs)</syntax>
    7072
    7173convenience wrapper to Make-lazy constructor, avoiding a thunk.
     
    110112
    111113checks if n is an admissible index for the lazy-list Lst.
     114Deprecated, makes finite Lists eager. Moreover traverses a List twice,
     115when used in a check
    112116
    113117==== Length
     
    121125<procedure>(Cons var Lst)</procedure>
    122126
    123 lazy version of cons
     127lazy version of cons.
     128Deprecated, use (Lazy finite? (cons var Lst)) instead
    124129
    125130==== Rest
     
    147152lazy version of car
    148153
    149 ==== Ref
    150 
    151 <procedure>(Ref n Lst)</procedure>
     154==== At
     155
     156<procedure>(At n Lst)</procedure>
    152157
    153158lazy version of list-ref with changed argument order, realizing the Lst
    154159argument upto n.
    155160
     161==== Ref
     162
     163<procedure>(Ref n Lst)</procedure>
     164
     165alias for At, deprecated.
     166
    156167==== Null?
    157168
     
    187198==== Fold-right*
    188199
    189 <procedure>(Fold-right* op base . Lsts)</procedure>
     200<procedure>(Fold-right* op base Lst . Lsts)</procedure>
    190201
    191202create a lazy list of right folds changing order or List items
     
    193204==== Fold-left*
    194205
    195 <procedure>(Fold-left* op base . Lsts)</procedure>
     206<procedure>(Fold-left* op base Lst . Lsts)</procedure>
    196207
    197208create a lazy list of left folds
     
    199210==== Fold-right
    200211
    201 <procedure>(Fold-right op base . Lsts)</procedure>
     212<procedure>(Fold-right op base Lst . Lsts)</procedure>
    202213
    203214lazy version of fold-right, one of the Lsts must be finite.
     
    205216==== Fold-left
    206217
    207 <procedure>(Fold-left op base . Lsts)</procedure>
     218<procedure>(Fold-left op base Lst . Lsts)</procedure>
    208219
    209220lazy version of fold-left, one of the Lsts must be finite.
     
    283294one to be appended.
    284295
     296==== Range
     297
     298<procedure>(Range [from] upto [step])</procedure>
     299
     300List of integers from (included) upto (excluded) with step
     301
    285302==== Iterate
    286303
    287 <procedure>(Iterate [n] proc x)</procedure>
    288 
    289 create finite List of Length n or infinite List by applying proc succesively to x
     304<procedure>(Iterate fn x [times])</procedure>
     305
     306create finite List of Length times or infinite List by applying fn succesively to x
    290307
    291308==== Repeatedly
    292309
    293 <procedure>(Repeatedly [n] thunk)</procedure>
    294 
    295 create finite List of Length n or infinite List of return values of thunk
     310<procedure>(Repeatedly thunk [times])</procedure>
     311
     312create finite List of Length times or infinite List of return values of thunk
    296313
    297314==== Repeat
    298315
    299 <procedure>(Repeat [n] x)</procedure>
    300 
    301 create finite List of Length n or infinite List of x
     316<procedure>(Repeat x [times])</procedure>
     317
     318create finite List of Length times or infinite List of x
    302319
    303320==== input->List
     
    493510
    494511lazy list of non negative integers
    495 
    496 ==== Interval
    497 
    498 <procedure>(Interval from upto)</procedure>
    499 
    500 List of integers from (included) upto (excluded)
    501512
    502513==== assume-in
     
    520531<enscript highlight=scheme>
    521532
    522 (require-library lazy-lists multi-methods)
    523 (import lazy-lists methods)
     533(require-library lazy-lists)
     534(import lazy-lists)
    524535
    525536(define (cons-right var lst)
     
    530541(define (Within eps Lst)
    531542  (let loop ((Lst Lst))
    532     (let ((a (Ref 0 Lst)) (b (Ref 1 Lst)))
     543    (let ((a (At 0 Lst)) (b (At 1 Lst)))
    533544      (if (< (abs (- a b)) eps)
    534545        b
     
    537548(define (Relative eps Lst)
    538549  (let loop ((Lst Lst))
    539     (let ((a (Ref 0 Lst)) (b (Ref 1 Lst)))
     550    (let ((a (At 0 Lst)) (b (At 1 Lst)))
    540551      (if (<= (abs (/ a b)) (* (abs b) eps))
    541552        b
     
    546557
    547558(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))))))
    550562
    551563(define (First-five) (List 0 1 2 3 4))
     
    563575(List->list (First-five)) ;-> '(0 1 2 3 4)
    564576(List->list (Take 5 (Cardinals))) ;-> '(0 1 2 3 4)
    565 (Length (Interval 2 10)) ;-> (- 10 2)
    566 (List->list (Interval 2 10)) ;-> '(2 3 4 5 6 7 8 9)
    567 (List->list (Interval 10 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)
    568580(receive (head index tail) (Split-with (cut < <> 3) (First-five))
    569         (cons (First tail) (List->list head))) ;-> '(3 0 1 2)
     581  (cons (First tail) (List->list head))) ;-> '(3 0 1 2)
    570582(receive (head index tail) (Split-with (cut < <> 5) (Take 10 (Cardinals)))
    571         (append (List->list tail) (List->list head))) ;-> '(5 6 7 8 9 0 1 2 3 4)
     583  (append (List->list tail) (List->list head))) ;-> '(5 6 7 8 9 0 1 2 3 4)
    572584(Index (cut = <> 2) (First-five)) ;-> 2
    573585(Index (cut = <> 20) (First-five)) ;-> 5
     
    598610(List->list (Filter odd? (First-five))) ;-> '(1 3)
    599611(Length (Filter odd? (Cardinals))) ;-> #f
    600 (Ref 20 (Sieve = (Zip (Cardinals) (Cardinals)))) ;-> 20
     612(At 20 (Sieve = (Zip (Cardinals) (Cardinals)))) ;-> 20
    601613(List->list (Sieve = (Zip (First-five) (First-five))))
    602614  ;-> '(0 1 2 3 4)
    603 (Ref 25 (Cardinals)) ;-> 25
    604 (Ref 2 (First-five)) ;-> 2
     615(At 25 (Cardinals)) ;-> 25
     616(At 2 (First-five)) ;-> 2
    605617(List->list (Take 3 (Repeat #f))) ;-> '(#f #f #f)
    606618(List->list (Take 3 (Repeatedly (lambda () 1))))
     
    618630(Length (Reverse (First-five))) ; -> 5
    619631(Length (Reverse* (Cardinals))) ; -> #f
    620 (List->list (Ref 5 (Reverse* (Cardinals)))) ; -> '(5 4 3 2 1 0)
     632(List->list (At 5 (Reverse* (Cardinals)))) ; -> '(5 4 3 2 1 0)
    621633(List->list (Take 10 (Cycle (First-five))))
    622634  ; -> '(0 1 2 3 4 0 1 2 3 4)
     
    636648(Fold-left cons '() (Take 5 (Cardinals)))
    637649  ; -> '(((((() . 0) . 1) . 2) . 3) . 4)
    638 (Ref 4 (Fold-left* cons '() (Cardinals)))
     650(At 4 (Fold-left* cons '() (Cardinals)))
    639651  ; -> '(((((() . 0) . 1) . 2) . 3) . 4)
    640652(Fold-right + 0 (Take 5 (Cardinals))) ; -> 10
     
    646658(Fold-right cons '(a b c) (First-five))
    647659  ; -> '(0 1 2 3 4 a b c)
    648 (Ref 4 (Fold-right* cons '() (Cardinals)))
     660(At 4 (Fold-right* cons '() (Cardinals)))
    649661  ; -> '(4 3 2 1 0)) ; note changed order
    650 (Ref 4 (Fold-right* cons-right '() (Cardinals)))
     662(At 4 (Fold-right* cons-right '() (Cardinals)))
    651663  ; -> '(0 1 2 3 4)
    652 (Ref 4 (Fold-right* cons '(a b c) (Cardinals)))
     664(At 4 (Fold-right* cons '(a b c) (Cardinals)))
    653665  ; -> '(4 3 2 1 0 a b c) ; note changed order
    654 (Ref 4 (Fold-right* cons-right '(a b c) (Cardinals)))
     666(At 4 (Fold-right* cons-right '(a b c) (Cardinals)))
    655667  ; -> '(a b c 0 1 2 3 4)
    656668(List->list (vector->List '#(0 1 2 3 4))) ; -> '(0 1 2 3 4)
     
    675687(Eqv? (Zip (First-five) (First-five))
    676688      (List 0 0 1 1 2 2 3 3 4 4)) ; -> #t
    677 (Ref 50 (Primes)) ; -> 233
     689(At 50 (Primes)) ; -> 233
    678690(Eqv? (Take 5 (Primes)) (List 2 3 5 7 11)) ; -> #t
    679691(Eqv? (Take 10 (Fibs)) (List  0 1 1 2 3 5 8 13 21 34)) ; -> #t
     
    681693(let ((eps 0.000001))
    682694  (< (abs (- (sqrt 2) (Within eps (Iterate (Newton 2) 2)))) eps)) ; -> #t
    683 (List->list (Sums (First-five))) ; -> '(0 1 3 6 10)
     695(List->list (Sums (Take 5 (Cardinals)))) ; -> '(0 1 3 6 10)
    684696
    685697</enscript>
     
    695707== Updated
    696708
    697 Nov 10, 2014
     709Mar 03, 2017
    698710
    699711== License
    700712
    701  Copyright (c) 2012-2014, Juergen Lorenz, Moritz Heidkamp
     713 Copyright (c) 2012-2017, Juergen Lorenz
    702714 All rights reserved.
    703715
     
    730742== Version History
    731743
     744; 0.9 : replaced length slot with finite? slot to keep lazyness of finite lists
    732745; 0.8.1 : fixed bug in documentation procedure lazy-lists
    733746; 0.8 : new procedures lazy-lists Unzip Remp Remove Remq Remv
Note: See TracChangeset for help on using the changeset viewer.