Changeset 31338 in project
 Timestamp:
 09/06/14 16:00:32 (5 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

wiki/eggref/4/typedlists
r31265 r31338 5 5 == Rationale 6 6 7 Scheme lists are mutable and untyped. The list types produced with 8 this library are immutable and typed. 7 Scheme lists are mutable and untyped. The list types produced with the 8 functors of this library are immutable and  in the general case  9 typed. 9 10 10 11 Concerning mutability, Scheme's authors, G. J. Sussman and G. L. Steele jr. … … 41 42 one version of the functor value is used. 42 43 43 Hence, this library implements a functor, typedlists, 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. 44 Hence, this library implements a functor, listfunctor, depending on a 45 module parameter which must supply two exports, named equ? and item?, 46 checking the list item's type and equality of its items. The resulting 47 code  when applied to a concrete module which implements these two 48 routines  defines immutable typed lists. 47 49 48 50 Note, that these typed lists don't pass the list? predicate. They … … 50 52 cases from the datatype module. 51 53 52 As an application of the typedlists functor, this library defines 53 another functor, typedsets, which depends on a second module, being 54 generated by the typedlists functor, which generates immutable typed sets, 55 being implemented as equivalence classes of immutable typed lists. 56 57 === typedlists 54 As an application of the listfunctor, this library defines another 55 functor, setfunctor, which depends on a second module, being generated 56 by the listfunctor, which generates immutable typed sets, being 57 implemented as equivalence classes of immutable typed lists. 58 59 Two untyped modules, immutablelists and sets, are also supplied as 60 instantiation of the two functors. They are untyped because the item 61 predicate is simply (lambda (x) #t), i.e. everything passes this test. 62 But note, that for compiling these modules we needed to supply two 63 patches, since the functor implementation is still buggy: In the Chicken 64 generated import modules the abstract module parameters must be replaced 65 by the concrete module arguments. 66 67 === listfunctor 58 68 59 69 the first functor's name, generating immutable typed lists when applied 60 to a module which provides the proper type? and equ? symbols. 61 62 === typedsets 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 typedlists with the 67 first module. 68 69 === Usage of typedlists 70 to a module which provides the proper item? and equ? symbols. 71 72 ==== Usage 70 73 71 74 <enscript highlight=scheme> 72 (requirelibrary datatype)73 (import typedlistsdatatype)75 (requirelibrary typedlists datatype) 76 (import listfunctor datatype) 74 77 75 78 ;; define argument module 76 (module vals ( type? equ?)79 (module vals (item? equ?) 77 80 (import scheme) 78 (define type? ...)81 (define item? ...) 79 82 (define equ? ...)) 80 83 81 84 ;; apply functor 82 (module vallists = ( typedlistsvals))85 (module vallists = (listfunctor vals)) 83 86 84 87 ;; import the functor 85 (import vallists)88 (import (prefix vallists val)) 86 89 87 90 ;; now use the generated routines 88 91 </enscript> 89 92 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 ==== listnull 99 <procedure>(listnull)</procedure> 93 === Functions generated by listfunctor 94 95 In this version of the library, we've changed all exported symbol names. 96 The first reason is consistency, the second  more important  is that 97 some of the old names contained the symbol typed, which didn't fit well 98 to the untyped example module immutablelists. 99 Now, all symbols start with the ilist prefix, in particular the analoga 100 to most of the classical list procedures. 101 102 Note the order of arguments: the lists generated by this functor are 103 consistently the last ones. 104 105 ==== ilistnull 106 <procedure>(ilistnull)</procedure> 100 107 the fundamental datatypeconstructor of an empty typed list. 101 108 102 ==== listcons103 <procedure>( listcons item tlst)</procedure>109 ==== ilistcons 110 <procedure>(ilistcons item ilst)</procedure> 104 111 the fundamental datatypeconstructor consing an item to a tlist while 105 checking, if it passes the type? test, one of the two routines exported by112 checking, if it passes the item? test, one of the two routines exported by 106 113 the argument module of the functor. 107 114 108 ==== typedlists109 <procedure>( typedlists [sym])</procedure>115 ==== ilists 116 <procedure>(ilists [sym])</procedure> 110 117 documentation procedure. 111 118 112 ==== typedlist?113 <procedure>( typedlist? xpr)</procedure>119 ==== ilist? 120 <procedure>(ilist? xpr)</procedure> 114 121 type predicate. 115 122 116 ==== typedlist117 <procedure>( typedlist . args)</procedure>118 constructor. All args must pass type?.119 120 ==== untypedlist>typedlist121 <procedure>( untypedlist>typedlist lst)</procedure>123 ==== ilist 124 <procedure>(ilist . args)</procedure> 125 constructor. All args must pass item?. 126 127 ==== ilist>ilist 128 <procedure>(ilist>ilist lst)</procedure> 122 129 another constructor. 123 130 124 131 ==== repeat 125 <procedure>( listrepeat n x)</procedure>126 constructs a typed list of length n with items all x of type?.127 128 ==== listiterate129 <procedure>( listiterate n fn x)</procedure>132 <procedure>(ilistrepeat n x)</procedure> 133 constructs a typed list of length n with items all x of item?. 134 135 ==== ilistiterate 136 <procedure>(ilistiterate n fn x)</procedure> 130 137 constructs a typed list of length n by successively applying fn to x. 131 fn must map type? items to type? itesm.132 133 ==== listiteratewhile134 <procedure>( listiteratewhile ok? fn x)</procedure>138 fn must map item? items to item? itesm. 139 140 ==== ilistiteratewhile 141 <procedure>(ilistiteratewhile ok? fn x)</procedure> 135 142 constructs a typed list by successively applying fn to x as long as ok? 136 143 returns #t. 137 fn must map type? items to type? itesm.138 139 ==== listiterateuntil140 <procedure>( listiterateuntil ok? fn x)</procedure>144 fn must map item? items to item? itesm. 145 146 ==== ilistiterateuntil 147 <procedure>(ilistiterateuntil ok? fn x)</procedure> 141 148 constructs a typed list by successively applying fn to x as long as ok? 142 149 returns #f. 143 fn must map type? items to type? itesm.144 145 ==== typedlist>untypedlist146 <procedure>( typedlist>untypedlist lst)</procedure>150 fn must map item? items to item? itesm. 151 152 ==== ilist>list 153 <procedure>(ilist>list lst)</procedure> 147 154 strips type information and immutability. The returned list is a normal 148 155 Scheme list. 149 156 150 ==== listapply151 <procedure>( listapply fn . args)</procedure>157 ==== ilistapply 158 <procedure>(ilistapply fn . args)</procedure> 152 159 like apply, but the last argument must be a typed list. 153 160 154 ==== listnull?155 <procedure>( listnull? xpr)</procedure>161 ==== ilistnull? 162 <procedure>(ilistnull? xpr)</procedure> 156 163 is xpr an empty typed list? 157 164 158 ==== listfirst159 <procedure>( listfirst tlst)</procedure>165 ==== ilistfirst 166 <procedure>(ilistfirst ilst)</procedure> 160 167 like car but with arguments in reversed order. 161 168 162 ==== listrest163 <procedure>( listrest tlst)</procedure>169 ==== ilistrest 170 <procedure>(ilistrest ilst)</procedure> 164 171 like cdr but with arguments in reversed order. 165 172 166 ==== listreverse167 <procedure>( listreverse . tlsts)</procedure>173 ==== ilistreverse 174 <procedure>(ilistreverse . ilsts)</procedure> 168 175 like reverse, but can reverse typed lists of equal length 169 176 simultaneously. 170 177 171 ==== listlength172 <procedure>( listlength tlst)</procedure>178 ==== ilistlength 179 <procedure>(ilistlength ilst)</procedure> 173 180 like length. 174 181 175 ==== listfromupto176 <procedure>( listfromupto from upto tlst)</procedure>182 ==== ilistfromupto 183 <procedure>(ilistfromupto from upto ilst)</procedure> 177 184 like sublist. 178 185 179 ==== listitem180 <procedure>( listitem k tlst)</procedure>186 ==== ilistitem 187 <procedure>(ilistitem k ilst)</procedure> 181 188 like listref, but with reversed argument order. 182 189 183 ==== listsplitat184 <procedure>( listsplitat k tlst)</procedure>190 ==== ilistsplitat 191 <procedure>(ilistsplitat k ilst)</procedure> 185 192 splits a typed list at index k returning two sublist values, the head and the 186 193 tail. 187 194 188 ==== listsplitwith189 <procedure>( listsplitwith ok? tlst)</procedure>195 ==== ilistsplitwith 196 <procedure>(ilistsplitwith ok? ilst)</procedure> 190 197 splits a typed list at the first item passing the ok? predicate. 191 198 Returns two sublists. 192 199 193 ==== listdrop194 <procedure>( listdrop k tlst)</procedure>200 ==== ilistdrop 201 <procedure>(ilistdrop k ilst)</procedure> 195 202 like listtail, but with revrsed argument order. 196 203 197 ==== listdropwhile198 <procedure>( listdropwhile ok? tlst)</procedure>204 ==== ilistdropwhile 205 <procedure>(ilistdropwhile ok? ilst)</procedure> 199 206 drops the first items as long as they pass the ok? predicate. 200 207 201 ==== listtake202 <procedure>( listtake k tlst)</procedure>208 ==== ilisttake 209 <procedure>(ilisttake k ilst)</procedure> 203 210 returns the head of the typed list upto (but excluding) the index k. 204 211 205 ==== listtakewhile206 <procedure>( listtakewhile ok? tlst)</procedure>212 ==== ilisttakewhile 213 <procedure>(ilisttakewhile ok? ilst)</procedure> 207 214 returns the longest sublist of a typed list where all items pass ok? 208 215 starting from index 0. 209 216 210 ==== listappend211 <procedure>( listappend . tlsts)</procedure>217 ==== ilistappend 218 <procedure>(ilistappend . ilsts)</procedure> 212 219 like append. 213 220 214 ==== listmap215 <procedure>( listmap fn . tlsts)</procedure>221 ==== ilistmap 222 <procedure>(ilistmap fn . ilsts)</procedure> 216 223 like map. 217 224 218 ==== listmappend219 <procedure>( listmappend fn . tlsts)</procedure>225 ==== ilistmappend 226 <procedure>(ilistmappend fn . ilsts)</procedure> 220 227 combination of map and append. 221 228 222 ==== listforeach223 <procedure>( listforeach fn . tlsts)</procedure>229 ==== ilistforeach 230 <procedure>(ilistforeach fn . ilsts)</procedure> 224 231 like foreach. 225 232 226 ==== listfilter227 <procedure>( listfilter ok? tlst)</procedure>233 ==== ilistfilter 234 <procedure>(ilistfilter ok? ilst)</procedure> 228 235 returns two sublist of a typed list. In the first one all items pass 229 236 ok?, in the second no one does that. 230 237 231 ==== listadjoin232 <procedure>( listadjoin item tlst)</procedure>238 ==== ilistadjoin 239 <procedure>(ilistadjoin item ilst)</procedure> 233 240 adds an item to a typed list only if it is not allready a member. 234 241 235 ==== listequal?236 <procedure>( listequal? tlst0 tlst1)</procedure>242 ==== ilistequal? 243 <procedure>(ilistequal? ilst0 ilst1)</procedure> 237 244 Are the typed argument lists equal?. All items are compared with equ?, 238 245 the other exported routine of the functor argument. 239 246 240 ==== listmemp241 <procedure>( listmemp ok? tlst)</procedure>247 ==== ilistmemp 248 <procedure>(ilistmemp ok? ilst)</procedure> 242 249 returns the sublist of a typed list, starting with the first item 243 250 passing ok?. 244 251 245 ==== listmember246 <procedure>( listmember item tlst)</procedure>252 ==== ilistmember 253 <procedure>(ilistmember item ilst)</procedure> 247 254 like member, items are compared with equ?. 248 255 249 ==== listremp250 <procedure>( listremp ok? tlst)</procedure>256 ==== ilistremp 257 <procedure>(ilistremp ok? ilst)</procedure> 251 258 removes all items from a typed list, which pass the ok? test. 252 259 253 ==== listremove254 <procedure>( listremove item tlst)</procedure>260 ==== ilistremove 261 <procedure>(ilistremove item ilst)</procedure> 255 262 removes all items from a typed list which are equ? to item. 256 263 257 ==== listremovedups258 <procedure>( listremovedups tlst)</procedure>264 ==== ilistremovedups 265 <procedure>(ilistremovedups ilst)</procedure> 259 266 removes all duplicates, compared with equ?. 260 267 261 ==== listassp262 <procedure>( listassp ok? tlst)</procedure>263 returns the first pair of a typedlist of pairs, whose car passes the268 ==== ilistassp 269 <procedure>(ilistassp ok? ilst)</procedure> 270 returns the first pair of a ilist of pairs, whose car passes the 264 271 ok? test. 265 272 266 ==== listassoc267 <procedure>( listassoc item tlst)</procedure>273 ==== ilistassoc 274 <procedure>(ilistassoc item ilst)</procedure> 268 275 like 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 ==== listfoldleft272 <procedure>( listfoldleft op base . tlsts)</procedure>276 type predicate item? and the cars are compared with equ?. 277 278 ==== ilistfoldleft 279 <procedure>(ilistfoldleft op base . ilsts)</procedure> 273 280 like foldleft in R7RS. 274 281 275 ==== listfoldright276 <procedure>( listfoldright op base . tlsts)</procedure>282 ==== ilistfoldright 283 <procedure>(ilistfoldright op base . ilsts)</procedure> 277 284 like foldright in R7RS. 278 285 279 ==== listmerge280 <procedure>( listmerge <? tlst0 tlst1)</procedure>286 ==== ilistmerge 287 <procedure>(ilistmerge <? ilst0 ilst1)</procedure> 281 288 merges two <?sorted typed lists. 282 289 283 ==== listsort284 <procedure>(listsort <? tlst)</procedure>285 merge sorts a typed list according to <?.286 287 290 ==== 288 <procedure>( listsorted? <? tlst)</procedure>291 <procedure>(ilistsorted? <? ilst)</procedure> 289 292 is a typed list sorted with respect ot <?. 290 293 291 ==== listconssorted292 <procedure>( listconssorted <? item tlst)</procedure>294 ==== ilistinsertsorted 295 <procedure>(ilistinsertsorted <? item ilst)</procedure> 293 296 inserts an item into a sorted typed list without disturbing order. 294 297 295 ==== listzip 296 <procedure>(listzip tlst0 tlst1)</procedure> 298 ==== ilistinsertionsort 299 <procedure>(ilistinsertionsort <? ilst)</procedure> 300 insertion sorts a typed list according to <?. 301 302 ==== ilistzip 303 <procedure>(ilistzip ilst0 ilst1)</procedure> 297 304 combines two typed lists in zip mode, i.e. alternating between the items 298 305 of the left and right argument list. 299 306 300 ==== listinterpose301 <procedure>( listinterpose sep tlst)</procedure>307 ==== ilistinterpose 308 <procedure>(ilistinterpose sep ilst)</procedure> 302 309 interposes a separator sep of type type between the list's items. 303 310 304 ==== listevery?305 <procedure>( listevery? ok? tlst)</procedure>311 ==== ilistevery? 312 <procedure>(ilistevery? ok? ilst)</procedure> 306 313 passes every item the ok? test? 307 314 308 ==== listsome309 <procedure>( listsome ok? tlst)</procedure>315 ==== ilistsome 316 <procedure>(ilistsome ok? ilst)</procedure> 310 317 returns the first item passing the ok? test. 311 318 312 ==== listnotevery?313 <procedure>( listnotevery? ok? tlst)</procedure>314 checks if not every item of tlst passes the ok? test.315 316 ==== listnotany?317 <procedure>( listnotany? ok? tlst)</procedure>318 checks if not any item of tlst passes the ok? test.319 320 ==== listin?321 <procedure>( listin? tlst0 tlst1)</procedure>322 checks, if the typed list tlst0 is a contiguous sublist of the323 typedlist tlst1.324 325 ==== listbind326 327 <macro>( listbind (x ... . xs) tlst xpr . xprs)</macro>319 ==== ilistnotevery? 320 <procedure>(ilistnotevery? ok? ilst)</procedure> 321 checks if not every item of ilst passes the ok? test. 322 323 ==== ilistnotany? 324 <procedure>(ilistnotany? ok? ilst)</procedure> 325 checks if not any item of ilst passes the ok? test. 326 327 ==== ilistin? 328 <procedure>(ilistin? ilst0 ilst1)</procedure> 329 checks, if the typed list ilst0 is a contiguous sublist of the 330 ilist ilst1. 331 332 ==== ilistbind 333 334 <macro>(ilistbind (x ... . xs) ilst xpr . xprs)</macro> 328 335 329 336 This macro allows for general pattern matching of typed lists. A more … … 332 339 <enscript highlight=scheme> 333 340 (use bindings) 334 (seqlengthreftail! typedlist?341 (seqlengthreftail! ilist? 335 342 listlength 336 (lambda ( tlst item) (listitem item tlst))337 (lambda ( tlst item) (listdrop item tlst)))343 (lambda (ilst item) (ilistitem item ilst)) 344 (lambda (ilst item) (ilistdrop item ilst))) 338 345 </enscript> 339 346 … … 341 348 sequence types. 342 349 343 === Usage of typedsets350 ==== Examples of using listfunctor 344 351 345 352 <enscript highlight=scheme> 346 (requirelibrary datatype) 347 (import typedlists typedsets datatype) 353 354 (requirelibrary typedlists datatype) 355 (import listfunctor datatype) 356 357 ;;; symbollists 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 symbollists = (listfunctor symbols)) 367 368 ;; imports 369 (import (prefix symbollists sym)) 370 371 ;; tests 372 (symilistappend (symilist 'a 'b) (symilist 'c)) 373 ; > ['a 'b 'c] 374 (symilistbind (x y z) (symilist 'a 'b 'c) (list x y z)) 375 ; > '(a b c) 376 (symilistbind (x . y) (symilist 'a 'b 'c) y) 377 ; > ['b 'c] 378 (symilistbind x (symilistnull) x) ; > [] 379 (symilistbind () (symilistnull) #t) ; > #t 380 381 ;;; pairlists 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 pairlists = (listfunctor pairs)) 392 393 ;; tests 394 (import (prefix pairlists nsp)) 395 (define nspl (nspilist (cons 1 "one") (cons 2 "two") (cons 3 "three"))) 396 (nspilistassoc 2 nspl) ; > '(2 . "two") 397 (nspilistassp zero? nspl) ; > #f 398 </enscript> 399 400 401 === setfunctor 402 403 the second functor's name, generating immutable typed sets when applied 404 to two modules, the first one providing the proper item? and equ? 405 symbols, the second being generated by invoking listfunctor with the 406 first module. 407 408 === Usage of setfunctor 409 410 <enscript highlight=scheme> 411 (requirelibrary typedlists datatype) 412 (import listfunctor setfunctor datatype) 348 413 349 414 ;; define first argument module 350 (module vals ( type? equ?)415 (module vals (item? equ?) 351 416 (import scheme) 352 (define type? ...)417 (define item? ...) 353 418 (define equ? ...)) 354 419 355 ;; apply typedlistsfunctor to provide second argument module356 (module vallists = ( typedlistsvals))357 358 ;; apply typedsetsfunctor359 (module valsets = ( typedsetsvals vallists))420 ;; apply listfunctor to provide second argument module 421 (module vallists = (listfunctor vals)) 422 423 ;; apply setfunctor 424 (module valsets = (setfunctor vals vallists)) 360 425 361 426 ;; import the modules … … 365 430 </enscript> 366 431 367 === Generated functions of the set datatype432 === Procedures generated by setfunctor 368 433 369 434 ==== sets … … 371 436 documentation procedure. 372 437 373 ==== typedlist>set374 <procedure>( typedlist>set lst)</procedure>438 ==== ilist>set 439 <procedure>(ilist>set lst)</procedure> 375 440 fundamental datatype constructor. Typed sets are implemented as 376 441 equivalence classes of typed lists. … … 382 447 ==== set 383 448 <procedure>(set . args)</procedure> 384 set constructor. All args must pass the type? test.385 386 ==== set> typedlist387 <procedure>(set> typedlist st)</procedure>449 set constructor. All args must pass the item? test. 450 451 ==== set>ilist 452 <procedure>(set>ilist st)</procedure> 388 453 forget set equality, set=, and return to list equality, listequal?. 389 454 390 455 ==== setin? 391 456 <procedure>(setin? item st)</procedure> 392 is item of type type? a member of the set st?457 is item of type item? a member of the set st? 393 458 394 459 ==== set<= … … 437 502 returns the set of items which are in all argument sets. 438 503 439 === Examples 504 === immutablelists 505 506 the module generated by listfunctor with nonchecking item? predicate 507 and equal? comparison operator. This is the most used case. 508 509 ==== Examples of using module immutablelists 440 510 441 511 <enscript highlight=scheme> 442 512 443 (requirelibrary cells datatype) 444 (import typedlists datatype) 445 446 ;;; numberlists 447 ;;;  448 ;; argument module 449 (module nums (type? equ?) 450 (import scheme cells) 451 (define (type? x) 452 (or (number? x) ((cellof? 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 (= (cellref x) 460 (cellref y))))) 461 ) 462 463 ;; apply functor 464 (module lists = (typedlists nums)) 465 466 ;; imports 467 (import lists cells) 468 469 ;; tests 470 (define nil (listnull)) 471 (typedlist? nil) 472 (listnull? nil) 473 (not (null? nil)) 474 (define nls (listcons 1 nil)) 475 (typedlist? nls) 476 (define nlst (typedlist 0 1 (cell 2) 3 4)) 477 (typedlist? nlst) 478 (not (list? nlst)) 479 (= (listapply + 1 2 (typedlist 3 4 5)) 15) 480 (listequal? (listrepeat 5 0) (typedlist 0 0 0 0 0)) 481 (listequal? (listiterate 5 add1 0) (typedlist 0 1 2 3 4)) 482 (listequal? (listiteratewhile (lambda (x) (< x 5)) add1 0) 483 (typedlist 0 1 2 3 4)) 484 (listequal? (listiterateuntil (lambda (x) (= x 5)) add1 0) 485 (typedlist 0 1 2 3 4)) 486 (listequal? (listzip (typedlist 1 2 3 4 5) (typedlist 10 20 30)) 487 (typedlist 1 10 2 20 3 30 4 5)) 488 (listequal? (listinterpose 10 (typedlist 1 2 3 4 5)) 489 (typedlist 1 10 2 10 3 10 4 10 5)) 490 (listequal? (listdrop 3 nlst) (typedlist 3 4)) 491 (listequal? (listdropwhile odd? (typedlist 1 3 2 4 5)) 492 (typedlist 2 4 5)) 493 (listequal? (listtakewhile odd? (typedlist 1 3 2 4 5)) 494 (typedlist 1 3)) 495 (receive (head tail) (listsplitwith even? (typedlist 1 3 2 4 5)) 496 (and (listequal? head (typedlist 1 3)) 497 (listequal? tail (typedlist 2 4 5)))) 498 (listequal? (listtake 2 nlst) (typedlist 0 1)) 499 (define nrest (listrest nlst)) 500 (typedlist? (listnull)) 501 (listnull? (listnull)) 502 (not (listnull? nls)) 503 (not (typedlist? '(1 2))) 504 (listnull? (listrest nls)) 505 (= (listfirst nlst) 0) 506 (typedlist? (listreverse nlst)) 507 (listreverse nlst) 508 (equal? (typedlist>untypedlist nlst) 509 (list 0 1 (cell 2) 3 4)) 510 (equal? (listitem 2 nlst) (cell 2)) 511 (cellset! (listitem 2 nlst) 20) 512 (equal? (listitem 2 nlst) (cell 20)) 513 (= (cellref (listitem 2 nlst)) 20) 514 (= (listlength nlst) 5) 515 (listequal? (listfromupto 2 4 nlst) 516 (typedlist (cell 20) 3)) 517 (listequal? (listappend (typedlist 0 1 2 3) 518 (typedlist 4 5 6)) 519 (typedlist 0 1 2 3 4 5 6)) 520 (listequal? (listappend 521 (typedlist 0) 522 (typedlist 1) 523 (typedlist 2) 524 (typedlist 3 4) 525 (typedlist 5 6 7) 526 (typedlist 8)) 527 (typedlist 0 1 2 3 4 5 6 7 8)) 528 (listequal? (listmap add1 529 (typedlist 0 1 2 3)) 530 (typedlist 1 2 3 4)) 531 (listequal? (listmap + 532 (typedlist 1 2 3) 533 (typedlist 10 20 30 40)) 534 (typedlist 11 22 33)) 535 (listequal? 536 (listmappend typedlist (typedlist 10 20 30) (typedlist 1 2 3 4 5)) 537 (typedlist 10 1 20 2 30 3)) 538 (listequal? 539 (listfoldright listcons (listnull) (typedlist 0 1 2 3 4)) 540 (typedlist 0 1 2 3 4)) 541 (listequal? 542 (listfoldright listcons (typedlist 0 1 2) (typedlist 3 4)) 543 (typedlist 3 4 0 1 2)) 544 (= (listfoldright * 1 (typedlist 1 2 3 4 5)) 120) 545 (= (listfoldleft * 1 (typedlist 1 2 3 4 5)) 120) 546 (= (listfoldleft + 0 (typedlist 1 2 3) (typedlist 10 20 30)) 66) 547 (equal? (listfoldleft cons '(100) (typedlist 1 2 3 4)) 548 '(((((100) . 1) . 2) . 3) . 4)) 513 (requirelibrary typedlists cells) 514 (import immutablelists cells) 515 516 (define nil (ilistnull)) 517 (ilist? nil) ; > #t 518 (ilistnull? nil) ; > #t 519 (null? nil) ; > #f 520 (define nls (ilistcons 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 (ilistapply + 1 2 (ilist 3 4 5); > 15 526 (ilistrepeat 5 0) ; > [0 0 0 0 0] 527 (ilistiterate 5 add1 0) ; > [0 1 2 3 4] 528 (ilistiteratewhile (lambda (x) (< x 5)) add1 0) 529 ; > [0 1 2 3 4] 530 (ilistiterateuntil (lambda (x) (= x 5)) add1 0) 531 ; > [0 1 2 3 4] 532 (ilistzip (ilist 1 2 3 4 5) (ilist 10 20 30)) 533 ; > [1 10 2 20 3 30 4 5] 534 (ilistinterpose 10 (ilist 1 2 3 4 5)) 535 ; > [1 10 2 10 3 10 4 10 5] 536 (ilistdrop 3 nlst) ; > [3 4] 537 (ilistdropwhile odd? (ilist 1 3 2 4 5)) ; > [2 4 5] 538 (ilisttakewhile odd? (ilist 1 3 2 4 5)) ; > [1 3] 539 (receive (head tail) (ilistsplitwith even? (ilist 1 3 2 4 5)) 540 (and (ilistequal? head (ilist 1 3)) 541 (ilistequal? tail (ilist 2 4 5)))) ; > #t 542 (ilisttake 2 nlst); > [0 1] 543 (define nrest (ilistrest nlst)) 544 (ilist? (ilistnull)) ; > #t 545 (ilistnull? (ilistnull)) ; > #t 546 (ilistnull? nls) ; > #f 547 (ilist? '(1 2)) ; > #f 548 (ilistnull? (ilistrest nls)) ; > #t 549 (ilistfirst nlst) ; > 0 550 (ilist? (ilistreverse nlst)) ; > #t 551 (ilistreverse nlst) 552 (ilist>list nlst) ; > (list 0 1 (cell 2) 3 4) 553 (ilistitem 2 nlst) ; > !2! 554 (cellset! (ilistitem 2 nlst) 20) 555 (ilistitem 2 nlst) ; > !20! 556 (cellref (ilistitem 2 nlst)) ; > 20 557 (ilistlength nlst) ; > 5 558 (ilistfromupto 2 4 nlst) ; > [!20! 3] 559 (ilistappend (ilist 0 1 2 3) (ilist 4 5 6)) 560 ; > [0 1 2 3 4 5 6] 561 (ilistappend 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 (ilistmap add1 (ilist 0 1 2 3)) ; > [1 2 3 4] 570 (ilistmap + (ilist 1 2 3) (ilist 10 20 30 40)) 571 ; > [11 22 33] 572 (ilistmappend ilist (ilist 10 20 30) (ilist 1 2 3 4 5)) 573 ; > [10 1 20 2 30 3] 574 (ilistfoldright listcons (ilistnull) (ilist 0 1 2 3 4)) 575 ; > [0 1 2 3 4] 576 (ilistfoldright listcons (ilist 0 1 2) (ilist 3 4)) 577 ; > [3 4 0 1 2] 578 (ilistfoldright * 1 (ilist 1 2 3 4 5)) ; > 120 579 (ilistfoldleft * 1 (ilist 1 2 3 4 5)); > 120 580 (ilistfoldleft + 0 (ilist 1 2 3) (ilist 10 20 30)); > 66 581 (equal? (ilistfoldleft cons '(100) (ilist 1 2 3 4)) 582 '(((((100) . 1) . 2) . 3) . 4)) ; > #t 549 583 (equal? 550 584 (callwithvalues 551 (lambda () ( listreverse (typedlist 1 2 3) (typedlist 10 20 30)))585 (lambda () (ilistreverse (ilist 1 2 3) (ilist 10 20 30))) 552 586 list) 553 (list (typedlist 3 2 1) (typedlist 30 20 10))) 554 (listequal? (listremove 0 (typedlist 1 0 2 0 3 0 4)) 555 (typedlist 1 2 3 4)) 556 (listequal? (listmerge < (typedlist 2 4 5 7 8) (typedlist 1 3 6 9 10)) 557 (typedlist 1 2 3 4 5 6 7 8 9 10)) 558 (not (conditioncase (listmerge < (listnull) (typedlist 1 3 2)) 559 ((exn) #f))) 560 (listequal? (listsort <= (typedlist 2 0 1 4 3)) 561 (typedlist 0 1 2 3 4)) 562 (not (listsorted? <= (typedlist 2 0 1 4 3))) 563 (listsorted? <= (typedlist 0 1 2 3 4)) 564 (listequal? 565 (listconssorted <= 2 (typedlist 0 1 2 3 4)) 566 (typedlist 0 1 2 2 3 4)) 567 (listequal? 568 (listconssorted <= 5 (typedlist 0 1 2 3 4)) 569 (typedlist 0 1 2 3 4 5)) 570 (listevery? odd? (typedlist 1 3 5)) 571 (listevery? odd? (typedlist)) 572 (= (listsome odd? (typedlist 2 3 5)) 3) 573 (not (listsome odd? (typedlist 2 4 6))) 574 (listnotevery? odd? (typedlist 1 2 3)) 575 (listnotany? odd? (typedlist 2 4 6)) 576 (listin? (typedlist 2 3) (typedlist 1 2 3)) 577 (not (listin? (typedlist 1 2 3) (typedlist 2 3))) 578 (not (listin? (typedlist 1 2 3) (typedlist 2 1 3))) 579 (listin? (typedlist) (typedlist 2 3)) 580 581 ;;; numbersets 582 ;;;  583 ;; generate module and import it 584 (module sets = (typedsets nums lists) 587 (list (ilist 3 2 1) (ilist 30 20 10))) ; > #t 588 (ilistremove 0 (ilist 1 0 2 0 3 0 4)) ; > [1 2 3 4] 589 (ilistmerge < (ilist 2 4 5 7 8) (ilist 1 3 6 9 10)) 590 ; > [1 2 3 4 5 6 7 8 9 10] 591 (conditioncase (ilistmerge < (ilistnull) (ilist 1 3 2)) 592 ((exn) #f)) ; > #f 593 (ilistmergesort <= (ilist 2 0 1 4 3)) ; > [0 1 2 3 4] 594 (ilistsorted? <= (ilist 2 0 1 4 3)) ; > #f 595 (ilistsorted? <= (ilist 0 1 2 3 4)) ; > #t 596 (ilistinsertsorted <= 2 (ilist 0 1 2 3 4)) 597 ; > [0 1 2 2 3 4] 598 (ilistinsertsorted <= 5 (ilist 0 1 2 3 4)) 599 ; > [0 1 2 3 4 5] 600 (ilistevery? odd? (ilist 1 3 5)) ; > #t 601 (ilistevery? odd? (ilist)) ; > #t 602 (ilistsome odd? (ilist 2 3 5)) ; > 3 603 (ilistsome odd? (ilist 2 4 6))) ; > #f 604 (ilistnotevery? odd? (ilist 1 2 3)) ; > #t 605 (ilistnotany? odd? (ilist 2 4 6)) ; > #t 606 (ilistin? (ilist 2 3) (ilist 1 2 3)) ; > #t 607 (ilistin? (ilist 1 2 3) (ilist 2 3)) ; > #f 608 (ilistin? (ilist 1 2 3) (ilist 2 1 3)) ; > #f 609 (ilistin? (ilist) (ilist 2 3)) ; > #t 610 611 </enscript> 612 613 === sets 614 615 the module generated by the setfunctor with nonchecking item? 616 predicate and equal? comparison operator. This is the most used case. 617 618 ==== Examples of using module sets 619 620 <enscript highlight=scheme> 621 622 (requirelibrary typedlists) 585 623 (import sets) 586 624 587 ;; apply it 588 (set= 589 (typedlist>set (typedlist 1 2 1 3 2 3)) 590 (set 3 2 1)) 625 (ilist>set (ilist 1 2 1 3 2 3)) ; > {3 2 1} 591 626 (set? (set 1 2 3)) 592 627 (set? (set 1 2 2 3)) 593 628 (set= (set 2 1 3) (set 1 2 2 3)) 594 (setin? 2 (set 1 1 2 3)) 595 (set<= (set 2 1 2) (set 4 1 2 3 4)) 596 (set= 597 (setadd 0 (set 1 2 3)) 598 (set 0 1 2 3)) 599 (set= 600 (setadd 2 (set 1 2 3)) 601 (set 1 2 3)) 602 (= (setcardinality (set 2 1 2 3 2)) 3) 603 (set= 604 (setremove 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 (setdifference (set 0 2 1 3) (set 1 1)) 611 (set 0 2 3)) 612 (set= 613 (setunion (set 1 2) (set 2 3) (set 3 4)) 614 (set 1 2 3 4)) 615 (set= 616 (setintersection (set 1 2 3 4) (set 2 3 5) (set 3 4)) 617 (set 3)) 618 (set= (setfilter odd? (set 2 1 3 3 1 1)) (set 3 1)) 619 620 ;;; symbollists 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 symbollists = (typedlists symbols)) 630 631 ;; imports 632 (import (prefix symbollists sym)) 633 634 ;; tests 635 (symlistequal? 636 (symlistappend (symtypedlist 'a 'b) 637 (symtypedlist 'c)) 638 (symtypedlist 'a 'b 'c)) 639 (equal? 640 (symlistbind (x y z) (symtypedlist 'a 'b 'c) (list x y z)) 641 '(a b c)) 642 (symlistequal? 643 (symlistbind (x . y) (symtypedlist 'a 'b 'c) y) 644 (symtypedlist 'b 'c)) 645 (symlistnull? (symlistbind x (symlistnull) x)) 646 (symlistbind () (symlistnull) #t) 647 648 ;;; pairlists 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 pairlists = (typedlists pairs)) 659 660 ;; tests 661 (import (prefix pairlists nsp)) 662 (define nspl (nsptypedlist (cons 1 "one") (cons 2 "two") (cons 3 "three"))) 663 (equal? (nsplistassoc 2 nspl) '(2 . "two")) 664 (not (nsplistassp zero? nspl)) 629 (setin? 2 (set 1 1 2 3)) ; > #t 630 (set<= (set 2 1 2) (set 4 1 2 3 4)) ; > #t 631 (setadd 0 (set 1 2 3)) ; > {0 1 2 3} 632 (setadd 2 (set 1 2 3)) ; > {1 2 3} 633 (setcardinality (set 2 1 2 3 2) ; > 3 634 (setremove 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 (setdifference (set 0 2 1 3) (set 1 1)) ; > {0 2 3} 637 (setunion (set 1 2) (set 2 3) (set 3 4)) ; > {1 2 3 4} 638 (setintersection (set 1 2 3 4) (set 2 3 5) (set 3 4)) ; > {3} 639 (set= (setfilter odd? (set 2 1 3 3 1 1)) ; > {3 1} 640 665 641 </enscript> 666 642 … … 671 647 == Last update 672 648 673 Aug 22, 2014649 Sep 05, 2014 674 650 675 651 == Author … … 710 686 == Version History 711 687 688 ; 2.0 : modules immutablelists and sets introduced, exported symbols renamed 712 689 ; 1.3 : functor split in two 713 690 ; 1.2 : listconssorted added
Note: See TracChangeset
for help on using the changeset viewer.