Changeset 31338 in project


Ignore:
Timestamp:
09/06/14 16:00:32 (5 years ago)
Author:
juergen
Message:

typed-lists 2.0 with additional modules and changed symbol names

File:
1 edited

Legend:

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

    r31265 r31338  
    55== Rationale
    66
    7 Scheme lists are mutable and untyped. The list types produced with
    8 this library are immutable and typed.
     7Scheme lists are mutable and untyped. The list types produced with the
     8functors of this library are immutable and -- in the general case --
     9typed.
    910
    1011Concerning mutability, Scheme's authors, G. J. Sussman and G. L. Steele jr.
     
    4142one version of the functor value is used.
    4243
    43 Hence, this library implements a functor, typed-lists, depending on a
    44 module parameter which must supply two exports, named equ? and type?.
    45 The resulting code -- when applied to a concrete module which implements
    46 these two routines -- defines immutable typed lists.
     44Hence, this library implements a functor, list-functor, depending on a
     45module parameter which must supply two exports, named equ? and item?,
     46checking the list item's type and equality of its items.  The resulting
     47code -- when applied to a concrete module which implements these two
     48routines -- defines immutable typed lists.
    4749
    4850Note, that these typed lists don't pass the list? predicate. They
     
    5052cases from the datatype module.
    5153
    52 As an application of the typed-lists functor, this library defines
    53 another functor, typed-sets, which depends on a second module, being
    54 generated by the typed-lists functor, which generates immutable typed sets,
    55 being implemented as equivalence classes of immutable typed lists.
    56 
    57 === typed-lists
     54As an application of the list-functor, this library defines another
     55functor, set-functor, which depends on a second module, being generated
     56by the list-functor, which generates immutable typed sets, being
     57implemented as equivalence classes of immutable typed lists.
     58
     59Two untyped modules, immutable-lists and sets, are also supplied as
     60instantiation of the two functors. They are untyped because the item
     61predicate is simply (lambda (x) #t), i.e. everything passes this test.
     62But note, that for compiling these modules we needed to supply two
     63patches, since the functor implementation is still buggy: In the Chicken
     64generated import modules the abstract module parameters must be replaced
     65by the concrete module arguments.
     66
     67=== list-functor
    5868
    5969the first functor's name, generating immutable typed lists when applied
    60 to a module which provides the proper type? and equ? symbols.
    61 
    62 === typed-sets
    63 
    64 the second functor's name, generating immutable typed sets when applied
    65 to two modules, the first one providing the proper type? and equ?
    66 symbols, the second being generated by invoking typed-lists with the
    67 first module.
    68 
    69 === Usage of typed-lists
     70to a module which provides the proper item? and equ? symbols.
     71
     72==== Usage
    7073
    7174<enscript highlight=scheme>
    72 (require-library datatype)
    73 (import typed-lists datatype)
     75(require-library typed-lists datatype)
     76(import list-functor datatype)
    7477
    7578;; define argument module
    76 (module vals (type? equ?)
     79(module vals (item? equ?)
    7780  (import scheme)
    78   (define type? ...)
     81  (define item? ...)
    7982  (define equ? ...))
    8083
    8184;; apply functor
    82 (module val-lists = (typed-lists vals))
     85(module val-lists = (list-functor vals))
    8386
    8487;; import the functor
    85 (import val-lists)
     88(import (prefix val-lists val-))
    8689
    8790;; now use the generated routines
    8891</enscript>
    8992
    90 === Generated functions of the list datatype
    91 
    92 Most of the names start with a list- prefix and work the same as the
    93 equally named ordinary Scheme routines without that prefix.
    94 
    95 Note the order of arguments: typed lists are consistently the last ones
    96 and named tlst.
    97 
    98 ==== list-null
    99 <procedure>(list-null)</procedure>
     93=== Functions generated by list-functor
     94
     95In this version of the library, we've changed all exported symbol names.
     96The first reason is consistency, the second -- more important -- is that
     97some of the old names contained the symbol typed, which didn't fit well
     98to the untyped example module immutable-lists.
     99Now, all symbols start with the ilist- prefix, in particular the analoga
     100to most of the classical list procedures.
     101
     102Note the order of arguments: the lists generated by this functor are
     103consistently the last ones.
     104
     105==== ilist-null
     106<procedure>(ilist-null)</procedure>
    100107the fundamental datatype-constructor of an empty typed list.
    101108
    102 ==== list-cons
    103 <procedure>(list-cons item tlst)</procedure>
     109==== ilist-cons
     110<procedure>(ilist-cons item ilst)</procedure>
    104111the fundamental datatype-constructor consing an item to a tlist while
    105 checking, if it passes the type? test, one of the two routines exported by
     112checking, if it passes the item? test, one of the two routines exported by
    106113the argument module of the functor.
    107114
    108 ==== typed-lists
    109 <procedure>(typed-lists [sym])</procedure>
     115==== ilists
     116<procedure>(ilists [sym])</procedure>
    110117documentation procedure.
    111118
    112 ==== typed-list?
    113 <procedure>(typed-list? xpr)</procedure>
     119==== ilist?
     120<procedure>(ilist? xpr)</procedure>
    114121type predicate.
    115122
    116 ==== typed-list
    117 <procedure>(typed-list . args)</procedure>
    118 constructor. All args must pass type?.
    119 
    120 ==== untyped-list->typed-list
    121 <procedure>(untyped-list->typed-list lst)</procedure>
     123==== ilist
     124<procedure>(ilist . args)</procedure>
     125constructor. All args must pass item?.
     126
     127==== ilist->ilist
     128<procedure>(ilist->ilist lst)</procedure>
    122129another constructor.
    123130
    124131==== repeat
    125 <procedure>(list-repeat n x)</procedure>
    126 constructs a typed list of length n with items all x of type?.
    127 
    128 ==== list-iterate
    129 <procedure>(list-iterate n fn x)</procedure>
     132<procedure>(ilist-repeat n x)</procedure>
     133constructs a typed list of length n with items all x of item?.
     134
     135==== ilist-iterate
     136<procedure>(ilist-iterate n fn x)</procedure>
    130137constructs a typed list of length n by successively applying fn to x.
    131 fn must map type? items to type? itesm.
    132 
    133 ==== list-iterate-while
    134 <procedure>(list-iterate-while ok? fn x)</procedure>
     138fn must map item? items to item? itesm.
     139
     140==== ilist-iterate-while
     141<procedure>(ilist-iterate-while ok? fn x)</procedure>
    135142constructs a typed list by successively applying fn to x as long as ok?
    136143returns #t.
    137 fn must map type? items to type? itesm.
    138 
    139 ==== list-iterate-until
    140 <procedure>(list-iterate-until ok? fn x)</procedure>
     144fn must map item? items to item? itesm.
     145
     146==== ilist-iterate-until
     147<procedure>(ilist-iterate-until ok? fn x)</procedure>
    141148constructs a typed list by successively applying fn to x as long as ok?
    142149returns #f.
    143 fn must map type? items to type? itesm.
    144 
    145 ==== typed-list->untyped-list
    146 <procedure>(typed-list->untyped-list lst)</procedure>
     150fn must map item? items to item? itesm.
     151
     152==== ilist->list
     153<procedure>(ilist->list lst)</procedure>
    147154strips type information and immutability. The returned list is a normal
    148155Scheme list.
    149156
    150 ==== list-apply
    151 <procedure>(list-apply fn . args)</procedure>
     157==== ilist-apply
     158<procedure>(ilist-apply fn . args)</procedure>
    152159like apply, but the last argument must be a typed list.
    153160
    154 ==== list-null?
    155 <procedure>(list-null? xpr)</procedure>
     161==== ilist-null?
     162<procedure>(ilist-null? xpr)</procedure>
    156163is xpr an empty typed list?
    157164
    158 ==== list-first
    159 <procedure>(list-first tlst)</procedure>
     165==== ilist-first
     166<procedure>(ilist-first ilst)</procedure>
    160167like car but with arguments in reversed order.
    161168
    162 ==== list-rest
    163 <procedure>(list-rest tlst)</procedure>
     169==== ilist-rest
     170<procedure>(ilist-rest ilst)</procedure>
    164171like cdr but with arguments in reversed order.
    165172
    166 ==== list-reverse
    167 <procedure>(list-reverse . tlsts)</procedure>
     173==== ilist-reverse
     174<procedure>(ilist-reverse . ilsts)</procedure>
    168175like reverse, but can reverse typed lists of equal length
    169176simultaneously.
    170177
    171 ==== list-length
    172 <procedure>(list-length tlst)</procedure>
     178==== ilist-length
     179<procedure>(ilist-length ilst)</procedure>
    173180like length.
    174181
    175 ==== list-from-upto
    176 <procedure>(list-from-upto from upto tlst)</procedure>
     182==== ilist-from-upto
     183<procedure>(ilist-from-upto from upto ilst)</procedure>
    177184like sublist.
    178185
    179 ==== list-item
    180 <procedure>(list-item k tlst)</procedure>
     186==== ilist-item
     187<procedure>(ilist-item k ilst)</procedure>
    181188like list-ref, but with reversed argument order.
    182189
    183 ==== list-split-at
    184 <procedure>(list-split-at k tlst)</procedure>
     190==== ilist-split-at
     191<procedure>(ilist-split-at k ilst)</procedure>
    185192splits a typed list at index k returning two sublist values, the head and the
    186193tail.
    187194
    188 ==== list-split-with
    189 <procedure>(list-split-with ok? tlst)</procedure>
     195==== ilist-split-with
     196<procedure>(ilist-split-with ok? ilst)</procedure>
    190197splits a typed list at the first item passing the ok? predicate.
    191198Returns two sublists.
    192199
    193 ==== list-drop
    194 <procedure>(list-drop k tlst)</procedure>
     200==== ilist-drop
     201<procedure>(ilist-drop k ilst)</procedure>
    195202like list-tail, but with revrsed argument order.
    196203
    197 ==== list-drop-while
    198 <procedure>(list-drop-while ok? tlst)</procedure>
     204==== ilist-drop-while
     205<procedure>(ilist-drop-while ok? ilst)</procedure>
    199206drops the first items as long as they pass the ok? predicate.
    200207
    201 ==== list-take
    202 <procedure>(list-take k tlst)</procedure>
     208==== ilist-take
     209<procedure>(ilist-take k ilst)</procedure>
    203210returns the head of the typed list upto (but excluding) the index k.
    204211
    205 ==== list-take-while
    206 <procedure>(list-take-while ok? tlst)</procedure>
     212==== ilist-take-while
     213<procedure>(ilist-take-while ok? ilst)</procedure>
    207214returns the longest sublist of a typed list where all items pass ok?
    208215starting from index 0.
    209216
    210 ==== list-append
    211 <procedure>(list-append . tlsts)</procedure>
     217==== ilist-append
     218<procedure>(ilist-append . ilsts)</procedure>
    212219like append.
    213220
    214 ==== list-map
    215 <procedure>(list-map fn . tlsts)</procedure>
     221==== ilist-map
     222<procedure>(ilist-map fn . ilsts)</procedure>
    216223like map.
    217224
    218 ==== list-mappend
    219 <procedure>(list-mappend fn . tlsts)</procedure>
     225==== ilist-mappend
     226<procedure>(ilist-mappend fn . ilsts)</procedure>
    220227combination of map and append.
    221228
    222 ==== list-for-each
    223 <procedure>(list-for-each fn . tlsts)</procedure>
     229==== ilist-for-each
     230<procedure>(ilist-for-each fn . ilsts)</procedure>
    224231like for-each.
    225232
    226 ==== list-filter
    227 <procedure>(list-filter ok? tlst)</procedure>
     233==== ilist-filter
     234<procedure>(ilist-filter ok? ilst)</procedure>
    228235returns two sublist of a typed list. In the first one all items pass
    229236ok?, in the second no one does that.
    230237
    231 ==== list-adjoin
    232 <procedure>(list-adjoin item tlst)</procedure>
     238==== ilist-adjoin
     239<procedure>(ilist-adjoin item ilst)</procedure>
    233240adds an item to a typed list only if it is not allready a member.
    234241
    235 ==== list-equal?
    236 <procedure>(list-equal? tlst0 tlst1)</procedure>
     242==== ilist-equal?
     243<procedure>(ilist-equal? ilst0 ilst1)</procedure>
    237244Are the typed argument lists equal?. All items are compared with equ?,
    238245the other exported routine of the functor argument.
    239246
    240 ==== list-memp
    241 <procedure>(list-memp ok? tlst)</procedure>
     247==== ilist-memp
     248<procedure>(ilist-memp ok? ilst)</procedure>
    242249returns the sublist of a typed list, starting with the first item
    243250passing ok?.
    244251
    245 ==== list-member
    246 <procedure>(list-member item tlst)</procedure>
     252==== ilist-member
     253<procedure>(ilist-member item ilst)</procedure>
    247254like member, items are compared with equ?.
    248255
    249 ==== list-remp
    250 <procedure>(list-remp ok? tlst)</procedure>
     256==== ilist-remp
     257<procedure>(ilist-remp ok? ilst)</procedure>
    251258removes all items from a typed list, which pass the ok? test.
    252259
    253 ==== list-remove
    254 <procedure>(list-remove item tlst)</procedure>
     260==== ilist-remove
     261<procedure>(ilist-remove item ilst)</procedure>
    255262removes all items from a typed list which are equ? to item.
    256263
    257 ==== list-remove-dups
    258 <procedure>(list-remove-dups tlst)</procedure>
     264==== ilist-remove-dups
     265<procedure>(ilist-remove-dups ilst)</procedure>
    259266removes all duplicates, compared with equ?.
    260267
    261 ==== list-assp
    262 <procedure>(list-assp ok? tlst)</procedure>
    263 returns the first pair of a typed-list of pairs, whose car passes the
     268==== ilist-assp
     269<procedure>(ilist-assp ok? ilst)</procedure>
     270returns the first pair of a ilist of pairs, whose car passes the
    264271ok? test.
    265272
    266 ==== list-assoc
    267 <procedure>(list-assoc item tlst)</procedure>
     273==== ilist-assoc
     274<procedure>(ilist-assoc item ilst)</procedure>
    268275like assoc for typed lists of pairs, the cars of which must pass the
    269 type predicate type? and the cars are compared with equ?.
    270 
    271 ==== list-fold-left
    272 <procedure>(list-fold-left op base . tlsts)</procedure>
     276type predicate item? and the cars are compared with equ?.
     277
     278==== ilist-fold-left
     279<procedure>(ilist-fold-left op base . ilsts)</procedure>
    273280like fold-left in R7RS.
    274281
    275 ==== list-fold-right
    276 <procedure>(list-fold-right op base . tlsts)</procedure>
     282==== ilist-fold-right
     283<procedure>(ilist-fold-right op base . ilsts)</procedure>
    277284like fold-right in R7RS.
    278285
    279 ==== list-merge
    280 <procedure>(list-merge <? tlst0 tlst1)</procedure>
     286==== ilist-merge
     287<procedure>(ilist-merge <? ilst0 ilst1)</procedure>
    281288merges two <?-sorted typed lists.
    282289
    283 ==== list-sort
    284 <procedure>(list-sort <? tlst)</procedure>
    285 merge sorts a typed list according to <?.
    286 
    287290====
    288 <procedure>(list-sorted? <? tlst)</procedure>
     291<procedure>(ilist-sorted? <? ilst)</procedure>
    289292is a typed list sorted with respect ot <?.
    290293
    291 ==== list-cons-sorted
    292 <procedure>(list-cons-sorted <? item tlst)</procedure>
     294==== ilist-insert-sorted
     295<procedure>(ilist-insert-sorted <? item ilst)</procedure>
    293296inserts an item into a sorted typed list without disturbing order.
    294297
    295 ==== list-zip
    296 <procedure>(list-zip tlst0 tlst1)</procedure>
     298==== ilist-insertion-sort
     299<procedure>(ilist-insertion-sort <? ilst)</procedure>
     300insertion sorts a typed list according to <?.
     301
     302==== ilist-zip
     303<procedure>(ilist-zip ilst0 ilst1)</procedure>
    297304combines two typed lists in zip mode, i.e. alternating between the items
    298305of the left and right argument list.
    299306
    300 ==== list-interpose
    301 <procedure>(list-interpose sep tlst)</procedure>
     307==== ilist-interpose
     308<procedure>(ilist-interpose sep ilst)</procedure>
    302309interposes a separator sep of type type between the list's items.
    303310
    304 ==== list-every?
    305 <procedure>(list-every? ok? tlst)</procedure>
     311==== ilist-every?
     312<procedure>(ilist-every? ok? ilst)</procedure>
    306313passes every item the ok? test?
    307314
    308 ==== list-some
    309 <procedure>(list-some ok? tlst)</procedure>
     315==== ilist-some
     316<procedure>(ilist-some ok? ilst)</procedure>
    310317returns the first item passing the ok? test.
    311318
    312 ==== list-not-every?
    313 <procedure>(list-not-every? ok? tlst)</procedure>
    314 checks if not every item of tlst passes the ok? test.
    315 
    316 ==== list-not-any?
    317 <procedure>(list-not-any? ok? tlst)</procedure>
    318 checks if not any item of tlst passes the ok? test.
    319 
    320 ==== list-in?
    321 <procedure>(list-in? tlst0 tlst1)</procedure>
    322 checks, if the typed list tlst0 is a contiguous sublist of the
    323 typed-list tlst1.
    324 
    325 ==== list-bind
    326 
    327 <macro>(list-bind (x ... . xs) tlst xpr . xprs)</macro>
     319==== ilist-not-every?
     320<procedure>(ilist-not-every? ok? ilst)</procedure>
     321checks if not every item of ilst passes the ok? test.
     322
     323==== ilist-not-any?
     324<procedure>(ilist-not-any? ok? ilst)</procedure>
     325checks if not any item of ilst passes the ok? test.
     326
     327==== ilist-in?
     328<procedure>(ilist-in? ilst0 ilst1)</procedure>
     329checks, if the typed list ilst0 is a contiguous sublist of the
     330ilist ilst1.
     331
     332==== ilist-bind
     333
     334<macro>(ilist-bind (x ... . xs) ilst xpr . xprs)</macro>
    328335
    329336This macro allows for general pattern matching of typed lists. A more
     
    332339<enscript highlight=scheme>
    333340(use bindings)
    334 (seq-length-ref-tail! typed-list?
     341(seq-length-ref-tail! ilist?
    335342                      list-length
    336                       (lambda (tlst item) (list-item item tlst))
    337                       (lambda (tlst item) (list-drop item tlst)))
     343                      (lambda (ilst item) (ilist-item item ilst))
     344                      (lambda (ilst item) (ilist-drop item ilst)))
    338345</enscript>
    339346
     
    341348sequence types.
    342349
    343 === Usage of typed-sets
     350==== Examples of using list-functor
    344351
    345352<enscript highlight=scheme>
    346 (require-library datatype)
    347 (import typed-lists typed-sets datatype)
     353
     354(require-library typed-lists datatype)
     355(import list-functor datatype)
     356
     357;;; symbol-lists
     358;;; ------------
     359;; argument module
     360(module symbols (equ? item?)
     361  (import scheme)
     362  (define equ? eq?)
     363  (define item? symbol?))
     364
     365;; apply functor
     366(module symbol-lists = (list-functor symbols))
     367
     368;; imports
     369(import (prefix symbol-lists sym-))
     370
     371;; tests
     372(sym-ilist-append (sym-ilist 'a 'b) (sym-ilist 'c))
     373  ; -> ['a 'b 'c]
     374(sym-ilist-bind (x y z) (sym-ilist 'a 'b 'c) (list x y z))
     375  ; -> '(a b c)
     376(sym-ilist-bind (x . y) (sym-ilist 'a 'b 'c) y)
     377  ; -> ['b 'c]
     378(sym-ilist-bind x (sym-ilist-null) x) ; -> []
     379(sym-ilist-bind () (sym-ilist-null) #t) ; -> #t
     380
     381;;; pair-lists
     382;;; ----------
     383;; argument module
     384(module pairs (item? equ?)
     385  (import scheme)
     386  (define (item? x)
     387    (and (pair? x) (number? (car x)) (string? (cdr x))))
     388  (define equ? equal?))
     389
     390;; apply functor
     391(module pair-lists = (list-functor pairs))
     392
     393;; tests
     394(import (prefix pair-lists nsp-))
     395(define nspl (nsp-ilist (cons 1 "one") (cons 2 "two") (cons 3 "three")))
     396(nsp-ilist-assoc 2 nspl) ; -> '(2 . "two")
     397(nsp-ilist-assp zero? nspl) ; -> #f
     398</enscript>
     399
     400
     401=== set-functor
     402
     403the second functor's name, generating immutable typed sets when applied
     404to two modules, the first one providing the proper item? and equ?
     405symbols, the second being generated by invoking list-functor with the
     406first module.
     407
     408=== Usage of set-functor
     409
     410<enscript highlight=scheme>
     411(require-library typed-lists datatype)
     412(import list-functor set-functor datatype)
    348413
    349414;; define first argument module
    350 (module vals (type? equ?)
     415(module vals (item? equ?)
    351416  (import scheme)
    352   (define type? ...)
     417  (define item? ...)
    353418  (define equ? ...))
    354419
    355 ;; apply typed-lists functor to provide second argument module
    356 (module val-lists = (typed-lists vals))
    357 
    358 ;; apply typed-sets functor
    359 (module val-sets = (typed-sets vals val-lists))
     420;; apply list-functor to provide second argument module
     421(module val-lists = (list-functor vals))
     422
     423;; apply set-functor
     424(module val-sets = (set-functor vals val-lists))
    360425
    361426;; import the modules
     
    365430</enscript>
    366431
    367 === Generated functions of the set datatype
     432=== Procedures generated by set-functor
    368433
    369434==== sets
     
    371436documentation procedure.
    372437
    373 ==== typed-list->set
    374 <procedure>(typed-list->set lst)</procedure>
     438==== ilist->set
     439<procedure>(ilist->set lst)</procedure>
    375440fundamental datatype constructor. Typed sets are implemented as
    376441equivalence classes of typed lists.
     
    382447==== set
    383448<procedure>(set . args)</procedure>
    384 set constructor. All args must pass the type? test.
    385 
    386 ==== set->typed-list
    387 <procedure>(set->typed-list st)</procedure>
     449set constructor. All args must pass the item? test.
     450
     451==== set->ilist
     452<procedure>(set->ilist st)</procedure>
    388453forget set equality, set=, and return to list equality, list-equal?.
    389454
    390455==== set-in?
    391456<procedure>(set-in? item st)</procedure>
    392 is item of type type? a member of the set st?
     457is item of type item? a member of the set st?
    393458
    394459==== set<=
     
    437502returns the set of items which are in all argument sets.
    438503
    439 === Examples
     504=== immutable-lists
     505
     506the module generated by list-functor with non-checking item?  predicate
     507and equal? comparison operator. This is the most used case.
     508
     509==== Examples of using module immutable-lists
    440510
    441511<enscript highlight=scheme>
    442512
    443 (require-library cells datatype)
    444 (import typed-lists datatype)
    445 
    446 ;;; number-lists
    447 ;;; ------------
    448 ;; argument module
    449 (module nums (type? equ?)
    450   (import scheme cells)
    451   (define (type? x)
    452     (or (number? x) ((cell-of? number?) x)))
    453   (define (equ? x y)
    454     (or (and (number? x)
    455              (number? y)
    456              (= x y))
    457         (and (cell? x)
    458              (cell? y)
    459              (= (cell-ref x)
    460                 (cell-ref y)))))
    461   )
    462 
    463 ;; apply functor
    464 (module lists = (typed-lists nums))
    465 
    466 ;; imports
    467 (import lists cells)
    468  
    469 ;; tests
    470 (define nil (list-null))
    471 (typed-list? nil)
    472 (list-null? nil)
    473 (not (null? nil))
    474 (define nls (list-cons 1 nil))
    475 (typed-list? nls)
    476 (define nlst (typed-list 0 1 (cell 2) 3 4))
    477 (typed-list? nlst)
    478 (not (list? nlst))
    479 (= (list-apply + 1 2 (typed-list 3 4 5)) 15)
    480 (list-equal? (list-repeat 5 0) (typed-list 0 0 0 0 0))
    481 (list-equal? (list-iterate 5 add1 0) (typed-list 0 1 2 3 4))
    482 (list-equal? (list-iterate-while (lambda (x) (< x 5)) add1 0)
    483              (typed-list 0 1 2 3 4))
    484 (list-equal? (list-iterate-until (lambda (x) (= x 5)) add1 0)
    485              (typed-list 0 1 2 3 4))
    486 (list-equal? (list-zip (typed-list 1 2 3 4 5) (typed-list 10 20 30))
    487              (typed-list 1 10 2 20 3 30 4 5))
    488 (list-equal? (list-interpose 10 (typed-list 1 2 3 4 5))
    489              (typed-list 1 10 2 10 3 10 4 10 5))
    490 (list-equal? (list-drop 3 nlst) (typed-list 3 4))
    491 (list-equal? (list-drop-while odd? (typed-list 1 3 2 4 5))
    492              (typed-list 2 4 5))
    493 (list-equal? (list-take-while odd? (typed-list 1 3 2 4 5))
    494              (typed-list 1 3))
    495 (receive (head tail) (list-split-with even? (typed-list 1 3 2 4 5))
    496   (and (list-equal? head (typed-list 1 3))
    497        (list-equal? tail (typed-list 2 4 5))))
    498 (list-equal? (list-take 2 nlst) (typed-list 0 1))
    499 (define nrest (list-rest nlst))
    500 (typed-list? (list-null))
    501 (list-null? (list-null))
    502 (not (list-null? nls))
    503 (not (typed-list? '(1 2)))
    504 (list-null? (list-rest nls))
    505 (= (list-first nlst) 0)
    506 (typed-list? (list-reverse nlst))
    507 (list-reverse nlst)
    508 (equal? (typed-list->untyped-list nlst)
    509         (list 0 1 (cell 2) 3 4))
    510 (equal? (list-item 2 nlst) (cell 2))
    511 (cell-set! (list-item 2 nlst) 20)
    512 (equal? (list-item 2 nlst) (cell 20))
    513 (= (cell-ref (list-item 2 nlst)) 20)
    514 (= (list-length nlst) 5)
    515 (list-equal? (list-from-upto 2 4 nlst)
    516              (typed-list (cell 20) 3))
    517 (list-equal?  (list-append (typed-list 0 1 2 3)
    518                            (typed-list 4 5 6))
    519               (typed-list 0 1 2 3 4 5 6))
    520 (list-equal? (list-append
    521                (typed-list 0)
    522                (typed-list 1)
    523                (typed-list 2)
    524                (typed-list 3 4)
    525                (typed-list 5 6 7)
    526                (typed-list 8))
    527              (typed-list 0 1 2 3 4 5 6 7 8))
    528 (list-equal? (list-map add1
    529                        (typed-list 0 1 2 3))
    530              (typed-list 1 2 3 4))
    531 (list-equal? (list-map +
    532                        (typed-list 1 2 3)
    533                        (typed-list 10 20 30 40))
    534              (typed-list 11 22 33))
    535 (list-equal?
    536   (list-mappend typed-list (typed-list 10 20 30) (typed-list 1 2 3 4 5))
    537   (typed-list 10 1 20 2 30 3))
    538 (list-equal?
    539   (list-fold-right list-cons (list-null) (typed-list 0 1 2 3 4))
    540   (typed-list 0 1 2 3 4))
    541 (list-equal?
    542   (list-fold-right list-cons (typed-list 0 1 2) (typed-list 3 4))
    543   (typed-list 3 4 0 1 2))
    544 (= (list-fold-right * 1 (typed-list 1 2 3 4 5)) 120)
    545 (= (list-fold-left * 1 (typed-list 1 2 3 4 5)) 120)
    546 (= (list-fold-left + 0 (typed-list 1 2 3) (typed-list 10 20 30)) 66)
    547 (equal? (list-fold-left cons '(100) (typed-list 1 2 3 4))
    548         '(((((100) . 1) . 2) . 3) . 4))
     513(require-library typed-lists cells)
     514(import immutable-lists cells)
     515
     516(define nil (ilist-null))
     517(ilist? nil) ; -> #t
     518(ilist-null? nil) ; -> #t
     519(null? nil) ; -> #f
     520(define nls (ilist-cons 1 nil))
     521(ilist? nls) ; -> #t
     522(define nlst (ilist 0 1 (cell 2) 3 4))
     523(ilist? nlst) ; -> #t
     524(list? nlst) ; -> #f
     525(ilist-apply + 1 2 (ilist 3 4 5); -> 15
     526(ilist-repeat 5 0) ; -> [0 0 0 0 0]
     527(ilist-iterate 5 add1 0) ; -> [0 1 2 3 4]
     528(ilist-iterate-while (lambda (x) (< x 5)) add1 0)
     529  ; -> [0 1 2 3 4]
     530(ilist-iterate-until (lambda (x) (= x 5)) add1 0)
     531            ; -> [0 1 2 3 4]
     532(ilist-zip (ilist 1 2 3 4 5) (ilist 10 20 30))
     533  ; -> [1 10 2 20 3 30 4 5]
     534(ilist-interpose 10 (ilist 1 2 3 4 5))
     535  ; -> [1 10 2 10 3 10 4 10 5]
     536(ilist-drop 3 nlst) ; -> [3 4]
     537(ilist-drop-while odd? (ilist 1 3 2 4 5)) ; -> [2 4 5]
     538(ilist-take-while odd? (ilist 1 3 2 4 5)) ; -> [1 3]
     539(receive (head tail) (ilist-split-with even? (ilist 1 3 2 4 5))
     540  (and (ilist-equal? head (ilist 1 3))
     541       (ilist-equal? tail (ilist 2 4 5)))) ; -> #t
     542(ilist-take 2 nlst); -> [0 1]
     543(define nrest (ilist-rest nlst))
     544(ilist? (ilist-null)) ; -> #t
     545(ilist-null? (ilist-null)) ; -> #t
     546(ilist-null? nls) ; -> #f
     547(ilist? '(1 2)) ; -> #f
     548(ilist-null? (ilist-rest nls)) ; -> #t
     549(ilist-first nlst) ; -> 0
     550(ilist? (ilist-reverse nlst)) ; -> #t
     551(ilist-reverse nlst)
     552(ilist->list nlst) ; -> (list 0 1 (cell 2) 3 4)
     553(ilist-item 2 nlst) ; -> !2!
     554(cell-set! (ilist-item 2 nlst) 20)
     555(ilist-item 2 nlst) ; -> !20!
     556(cell-ref (ilist-item 2 nlst)) ; -> 20
     557(ilist-length nlst) ; -> 5
     558(ilist-from-upto 2 4 nlst) ; -> [!20! 3]
     559(ilist-append (ilist 0 1 2 3) (ilist 4 5 6))
     560  ; -> [0 1 2 3 4 5 6]
     561(ilist-append
     562  (ilist 0)
     563  (ilist 1)
     564  (ilist 2)
     565  (ilist 3 4)
     566  (ilist 5 6 7)
     567  (ilist 8))
     568  ; -> [0 1 2 3 4 5 6 7 8]
     569(ilist-map add1 (ilist 0 1 2 3)) ; -> [1 2 3 4]
     570(ilist-map + (ilist 1 2 3) (ilist 10 20 30 40))
     571  ; -> [11 22 33]
     572(ilist-mappend ilist (ilist 10 20 30) (ilist 1 2 3 4 5))
     573  ; -> [10 1 20 2 30 3]
     574(ilist-fold-right list-cons (ilist-null) (ilist 0 1 2 3 4))
     575  ; -> [0 1 2 3 4]
     576(ilist-fold-right list-cons (ilist 0 1 2) (ilist 3 4))
     577  ; -> [3 4 0 1 2]
     578(ilist-fold-right * 1 (ilist 1 2 3 4 5)) ; -> 120
     579(ilist-fold-left * 1 (ilist 1 2 3 4 5)); ->  120
     580(ilist-fold-left + 0 (ilist 1 2 3) (ilist 10 20 30)); ->  66
     581(equal? (ilist-fold-left cons '(100) (ilist 1 2 3 4))
     582        '(((((100) . 1) . 2) . 3) . 4)) ; -> #t
    549583(equal?
    550584  (call-with-values
    551     (lambda () (list-reverse (typed-list 1 2 3) (typed-list 10 20 30)))
     585    (lambda () (ilist-reverse (ilist 1 2 3) (ilist 10 20 30)))
    552586    list)
    553   (list (typed-list 3 2 1) (typed-list 30 20 10)))
    554 (list-equal? (list-remove 0 (typed-list 1 0 2 0 3 0 4))
    555              (typed-list 1 2 3 4))
    556 (list-equal? (list-merge < (typed-list 2 4 5 7 8) (typed-list 1 3 6 9 10))
    557              (typed-list 1 2 3 4 5 6 7 8 9 10))
    558 (not (condition-case (list-merge < (list-null) (typed-list 1 3 2))
    559        ((exn) #f)))
    560 (list-equal? (list-sort <= (typed-list 2 0 1 4 3))
    561              (typed-list 0 1 2 3 4))
    562 (not (list-sorted? <= (typed-list 2 0 1 4 3)))
    563 (list-sorted? <= (typed-list 0 1 2 3 4))
    564 (list-equal?
    565   (list-cons-sorted <= 2 (typed-list 0 1 2 3 4))
    566   (typed-list 0 1 2 2 3 4))
    567 (list-equal?
    568   (list-cons-sorted <= 5 (typed-list 0 1 2 3 4))
    569   (typed-list 0 1 2 3 4 5))
    570 (list-every? odd? (typed-list 1 3 5))
    571 (list-every? odd? (typed-list))
    572 (= (list-some odd? (typed-list 2 3 5)) 3)
    573 (not (list-some odd? (typed-list 2 4 6)))
    574 (list-not-every? odd? (typed-list 1 2 3))
    575 (list-not-any? odd? (typed-list 2 4 6))
    576 (list-in? (typed-list 2 3) (typed-list 1 2 3))
    577 (not (list-in? (typed-list 1 2 3) (typed-list 2 3)))
    578 (not (list-in? (typed-list 1 2 3) (typed-list 2 1 3)))
    579 (list-in? (typed-list) (typed-list 2 3))
    580 
    581 ;;; number-sets
    582 ;;; -----------
    583 ;; generate module and import it
    584 (module sets = (typed-sets nums lists)
     587  (list (ilist 3 2 1) (ilist 30 20 10))) ; -> #t
     588(ilist-remove 0 (ilist 1 0 2 0 3 0 4)) ; -> [1 2 3 4]
     589(ilist-merge < (ilist 2 4 5 7 8) (ilist 1 3 6 9 10))
     590  ; -> [1 2 3 4 5 6 7 8 9 10]
     591(condition-case (ilist-merge < (ilist-null) (ilist 1 3 2))
     592       ((exn) #f)) ; -> #f
     593(ilist-merge-sort <= (ilist 2 0 1 4 3)) ; -> [0 1 2 3 4]
     594(ilist-sorted? <= (ilist 2 0 1 4 3)) ; -> #f
     595(ilist-sorted? <= (ilist 0 1 2 3 4)) ; -> #t
     596(ilist-insert-sorted <= 2 (ilist 0 1 2 3 4))
     597  ; -> [0 1 2 2 3 4]
     598(ilist-insert-sorted <= 5 (ilist 0 1 2 3 4))
     599  ; -> [0 1 2 3 4 5]
     600(ilist-every? odd? (ilist 1 3 5)) ; -> #t
     601(ilist-every? odd? (ilist)) ; -> #t
     602(ilist-some odd? (ilist 2 3 5)) ; -> 3
     603(ilist-some odd? (ilist 2 4 6))) ; -> #f
     604(ilist-not-every? odd? (ilist 1 2 3)) ; -> #t
     605(ilist-not-any? odd? (ilist 2 4 6)) ; -> #t
     606(ilist-in? (ilist 2 3) (ilist 1 2 3)) ; -> #t
     607(ilist-in? (ilist 1 2 3) (ilist 2 3)) ; -> #f
     608(ilist-in? (ilist 1 2 3) (ilist 2 1 3)) ; -> #f
     609(ilist-in? (ilist) (ilist 2 3)) ; -> #t
     610
     611</enscript>
     612
     613=== sets
     614
     615the module generated by the set-functor with non-checking item?
     616predicate and equal? comparison operator. This is the most used case.
     617
     618==== Examples of using module sets
     619
     620<enscript highlight=scheme>
     621
     622(require-library typed-lists)
    585623(import sets)
    586624
    587 ;; apply it
    588 (set=
    589   (typed-list->set (typed-list 1 2 1 3 2 3))
    590   (set 3 2 1))
     625(ilist->set (ilist 1 2 1 3 2 3)) ; -> {3 2 1}
    591626(set? (set 1 2 3))
    592627(set? (set 1 2 2 3))
    593628(set= (set 2 1 3) (set 1 2 2 3))
    594 (set-in? 2 (set 1 1 2 3))
    595 (set<= (set 2 1 2) (set 4 1 2 3 4))
    596 (set=
    597   (set-add 0 (set 1 2 3))
    598   (set 0 1 2 3))
    599 (set=
    600   (set-add 2 (set 1 2 3))
    601   (set 1 2 3))
    602 (= (set-cardinality (set 2 1 2 3 2)) 3)
    603 (set=
    604   (set-remove 2 (set 2 1 2 3 2))
    605   (set 1 3))
    606 (set=
    607   (set 0 1 1 0 2 3 2)
    608   (set 2 3 0 1))
    609 (set=
    610   (set-difference (set 0 2 1 3) (set 1 1))
    611   (set 0 2 3))
    612 (set=
    613   (set-union (set 1 2) (set 2 3) (set 3 4))
    614   (set 1 2 3 4))
    615 (set=
    616   (set-intersection (set 1 2 3 4) (set 2 3 5) (set 3 4))
    617   (set 3))
    618 (set= (set-filter odd? (set 2 1 3 3 1 1)) (set 3 1))
    619 
    620 ;;; symbol-lists
    621 ;;; ------------
    622 ;; argument module
    623 (module symbols (equ? type?)
    624   (import scheme)
    625   (define equ? eq?)
    626   (define type? symbol?))
    627 
    628 ;; apply functor
    629 (module symbol-lists = (typed-lists symbols))
    630 
    631 ;; imports
    632 (import (prefix symbol-lists sym-))
    633 
    634 ;; tests
    635 (sym-list-equal?
    636   (sym-list-append (sym-typed-list 'a 'b)
    637                (sym-typed-list 'c))
    638   (sym-typed-list 'a 'b 'c))
    639 (equal?
    640   (sym-list-bind (x y z) (sym-typed-list 'a 'b 'c) (list x y z))
    641   '(a b c))
    642 (sym-list-equal?
    643     (sym-list-bind (x . y) (sym-typed-list 'a 'b 'c) y)
    644   (sym-typed-list 'b 'c))
    645 (sym-list-null? (sym-list-bind x (sym-list-null) x))
    646 (sym-list-bind () (sym-list-null) #t)
    647 
    648 ;;; pair-lists
    649 ;;; ----------
    650 ;; argument module
    651 (module pairs (type? equ?)
    652   (import scheme)
    653   (define (type? x)
    654     (and (pair? x) (number? (car x)) (string? (cdr x))))
    655   (define equ? equal?))
    656 
    657 ;; apply functor
    658 (module pair-lists = (typed-lists pairs))
    659 
    660 ;; tests
    661 (import (prefix pair-lists nsp-))
    662 (define nspl (nsp-typed-list (cons 1 "one") (cons 2 "two") (cons 3 "three")))
    663 (equal? (nsp-list-assoc 2 nspl) '(2 . "two"))
    664 (not (nsp-list-assp zero? nspl))
     629(set-in? 2 (set 1 1 2 3)) ; -> #t
     630(set<= (set 2 1 2) (set 4 1 2 3 4)) ; -> #t
     631(set-add 0 (set 1 2 3)) ; -> {0 1 2 3}
     632(set-add 2 (set 1 2 3)) ; -> {1 2 3}
     633(set-cardinality (set 2 1 2 3 2) ; -> 3
     634(set-remove 2 (set 2 1 2 3 2)) ; -> {1 3}
     635(set= (set 0 1 1 0 2 3 2) (set 2 3 0 1)) ; -> #t
     636(set-difference (set 0 2 1 3) (set 1 1)) ; -> {0 2 3}
     637(set-union (set 1 2) (set 2 3) (set 3 4)) ; -> {1 2 3 4}
     638(set-intersection (set 1 2 3 4) (set 2 3 5) (set 3 4)) ; -> {3}
     639(set= (set-filter odd? (set 2 1 3 3 1 1)) ; -> {3 1}
     640
    665641</enscript>
    666642
     
    671647== Last update
    672648
    673 Aug 22, 2014
     649Sep 05, 2014
    674650
    675651== Author
     
    710686== Version History
    711687
     688; 2.0 : modules immutable-lists and sets introduced, exported symbols renamed
    712689; 1.3 : functor split in two
    713690; 1.2 : list-cons-sorted added
Note: See TracChangeset for help on using the changeset viewer.