1 | [[tags: egg]] |
---|
2 | [[toc:]] |
---|
3 | |
---|
4 | |
---|
5 | == Rationale |
---|
6 | |
---|
7 | Scheme lists are mutable and untyped. The list types produced with |
---|
8 | this module, a functor, are immutable and typed. |
---|
9 | |
---|
10 | Concerning mutability, Scheme's authors, G. J. Sussman and G. L. Steele jr. |
---|
11 | in their paper "The First Report on Scheme Revisited", Higher-Order and |
---|
12 | Symbolic Computation, 11, 399-404 (1998), argued: |
---|
13 | |
---|
14 | "We also now believe that Carl Hewitt was right: we would have been |
---|
15 | better off to have introduced cells as a separate, primitive kind of |
---|
16 | object, rather than allowing assignment to any and every lambda-bound |
---|
17 | variable" |
---|
18 | |
---|
19 | Well, cells -- or boxes, if you prefer -- exist as modules, so restricted |
---|
20 | mutability can be provided by accepting cells -- or boxes -- as item types. |
---|
21 | |
---|
22 | Typing of list arguments on the other hand improves security of the |
---|
23 | implemented functions on the one side, but are cumbersome to use on the |
---|
24 | other: After all, we don't want to write the same routines for lists of |
---|
25 | numbers, lists of strings, lists of symbols, ... or what have you. |
---|
26 | |
---|
27 | My first solution to this problem in version 0.1 was really pedestrian, |
---|
28 | a huge macro which generated a bunch of procedures all prefixed with |
---|
29 | some symbol depending on the use of the macro. Well, that worked, but it |
---|
30 | was rather ugly. There is a much more elegant and flexible solution, which |
---|
31 | depends on functors, which are unfortunately rarely known by programmers. |
---|
32 | |
---|
33 | Recall, that functors are to Chicken modules what functions are to |
---|
34 | Chicken values. In other words, functors are defined with abstract module |
---|
35 | parameters, which produce modules only when fed with concrete module |
---|
36 | arguments. This is exactly what we need. The abstract module parameter |
---|
37 | should export the names of the routines to be replaced by the equally |
---|
38 | named routines of the concrete module argument. The generated module can |
---|
39 | than be imported with a prefix of your liking or without one, if only |
---|
40 | one version of the functor value is used. |
---|
41 | |
---|
42 | Hence, this module implements a functor, typed-lists, depending on a |
---|
43 | module parameter which must supply two exports, named equ? and type?. |
---|
44 | The resulting code -- when applied to a concrete module which implements |
---|
45 | these two routines -- defines list and set datatypes, to be more |
---|
46 | precise, immutable typed lists and immutable typed sets, the latter |
---|
47 | being equivalence classes of the former. |
---|
48 | |
---|
49 | Note, that these typed lists don't pass the list? predicate. They |
---|
50 | are different creatures, created with define-datatype and accessed with |
---|
51 | cases from the datatype module. |
---|
52 | |
---|
53 | === typed-lists |
---|
54 | |
---|
55 | the functor's name, exporting typed lists and (typed) sets. |
---|
56 | |
---|
57 | === Usage |
---|
58 | |
---|
59 | <enscript highlight=scheme> |
---|
60 | (require-library datatype) |
---|
61 | (import typed-lists datatype) |
---|
62 | |
---|
63 | ;; define argument module |
---|
64 | (module arg-name (type? equ?) |
---|
65 | (import scheme) |
---|
66 | (define type? ...) |
---|
67 | (define equ? ...)) |
---|
68 | |
---|
69 | ;; apply functor |
---|
70 | (module val-name = (typed-lists arg-name)) |
---|
71 | |
---|
72 | ;; import the functor |
---|
73 | (import val-name) |
---|
74 | |
---|
75 | ;; now use the generated routines |
---|
76 | </enscript> |
---|
77 | |
---|
78 | === Generated functions of the list datatype |
---|
79 | |
---|
80 | Most of the names start with a list- prefix and work the same as the |
---|
81 | equally named ordinary Scheme routines without that prefix. |
---|
82 | |
---|
83 | Note the order of arguments: typed lists are consistently the last ones |
---|
84 | and named tlst. |
---|
85 | |
---|
86 | ==== list-null |
---|
87 | <procedure>(list-null)</procedure> |
---|
88 | the fundamental datatype-constructor of an empty typed list. |
---|
89 | |
---|
90 | ==== list-cons |
---|
91 | <procedure>(list-cons item tlst)</procedure> |
---|
92 | the fundamental datatype-constructor consing an item to a tlist while |
---|
93 | checking, if it passes the type? test, one of the two routines exported by |
---|
94 | the argument module of the functor. |
---|
95 | |
---|
96 | ==== typed-lists |
---|
97 | <procedure>(typed-lists [sym])</procedure> |
---|
98 | documentation procedure. |
---|
99 | |
---|
100 | ==== typed-list? |
---|
101 | <procedure>(typed-list? xpr)</procedure> |
---|
102 | type predicate. |
---|
103 | |
---|
104 | ==== typed-list |
---|
105 | <procedure>(typed-list . args)</procedure> |
---|
106 | constructor. All args must pass type?. |
---|
107 | |
---|
108 | ==== untyped-list->typed-list |
---|
109 | <procedure>(untyped-list->typed-list lst)</procedure> |
---|
110 | another constructor. |
---|
111 | |
---|
112 | ==== repeat |
---|
113 | <procedure>(list-repeat n x)</procedure> |
---|
114 | constructs a typed list of length n with items all x of type?. |
---|
115 | |
---|
116 | ==== list-iterate |
---|
117 | <procedure>(list-iterate n fn x)</procedure> |
---|
118 | constructs a typed list of length n by successively applying fn to x. |
---|
119 | fn must map type? items to type? itesm. |
---|
120 | |
---|
121 | ==== list-iterate-while |
---|
122 | <procedure>(list-iterate-while ok? fn x)</procedure> |
---|
123 | constructs a typed list by successively applying fn to x as long as ok? |
---|
124 | returns #t. |
---|
125 | fn must map type? items to type? itesm. |
---|
126 | |
---|
127 | ==== list-iterate-until |
---|
128 | <procedure>(list-iterate-until ok? fn x)</procedure> |
---|
129 | constructs a typed list by successively applying fn to x as long as ok? |
---|
130 | returns #f. |
---|
131 | fn must map type? items to type? itesm. |
---|
132 | |
---|
133 | ==== typed-list->untyped-list |
---|
134 | <procedure>(typed-list->untyped-list lst)</procedure> |
---|
135 | strips type information and immutability. The returned list is a normal |
---|
136 | Scheme list. |
---|
137 | |
---|
138 | ==== list-apply |
---|
139 | <procedure>(list-apply fn . args)</procedure> |
---|
140 | like apply, but the last argument must be a typed list. |
---|
141 | |
---|
142 | ==== list-null? |
---|
143 | <procedure>(list-null? xpr)</procedure> |
---|
144 | is xpr an empty typed list? |
---|
145 | |
---|
146 | ==== list-first |
---|
147 | <procedure>(list-first tlst)</procedure> |
---|
148 | like car but with arguments in reversed order. |
---|
149 | |
---|
150 | ==== list-rest |
---|
151 | <procedure>(list-rest tlst)</procedure> |
---|
152 | like cdr but with arguments in reversed order. |
---|
153 | |
---|
154 | ==== list-reverse |
---|
155 | <procedure>(list-reverse . tlsts)</procedure> |
---|
156 | like reverse, but can reverse typed lists of equal length |
---|
157 | simultaneously. |
---|
158 | |
---|
159 | ==== list-length |
---|
160 | <procedure>(list-length tlst)</procedure> |
---|
161 | like length. |
---|
162 | |
---|
163 | ==== list-from-upto |
---|
164 | <procedure>(list-from-upto from upto tlst)</procedure> |
---|
165 | like sublist. |
---|
166 | |
---|
167 | ==== list-item |
---|
168 | <procedure>(list-item k tlst)</procedure> |
---|
169 | like list-ref, but with reversed argument order. |
---|
170 | |
---|
171 | ==== list-split-at |
---|
172 | <procedure>(list-split-at k tlst)</procedure> |
---|
173 | splits a typed list at index k returning two sublist values, the head and the |
---|
174 | tail. |
---|
175 | |
---|
176 | ==== list-split-with |
---|
177 | <procedure>(list-split-with ok? tlst)</procedure> |
---|
178 | splits a typed list at the first item passing the ok? predicate. |
---|
179 | Returns two sublists. |
---|
180 | |
---|
181 | ==== list-drop |
---|
182 | <procedure>(list-drop k tlst)</procedure> |
---|
183 | like list-tail, but with revrsed argument order. |
---|
184 | |
---|
185 | ==== list-drop-while |
---|
186 | <procedure>(list-drop-while ok? tlst)</procedure> |
---|
187 | drops the first items as long as they pass the ok? predicate. |
---|
188 | |
---|
189 | ==== list-take |
---|
190 | <procedure>(list-take k tlst)</procedure> |
---|
191 | returns the head of the typed list upto (but excluding) the index k. |
---|
192 | |
---|
193 | ==== list-take-while |
---|
194 | <procedure>(list-take-while ok? tlst)</procedure> |
---|
195 | returns the longest sublist of a typed list where all items pass ok? |
---|
196 | starting from index 0. |
---|
197 | |
---|
198 | ==== list-append |
---|
199 | <procedure>(list-append . tlsts)</procedure> |
---|
200 | like append. |
---|
201 | |
---|
202 | ==== list-map |
---|
203 | <procedure>(list-map fn . tlsts)</procedure> |
---|
204 | like map. |
---|
205 | |
---|
206 | ==== list-mappend |
---|
207 | <procedure>(list-mappend fn . tlsts)</procedure> |
---|
208 | combination of map and append. |
---|
209 | |
---|
210 | ==== list-for-each |
---|
211 | <procedure>(list-for-each fn . tlsts)</procedure> |
---|
212 | like for-each. |
---|
213 | |
---|
214 | ==== list-filter |
---|
215 | <procedure>(list-filter ok? tlst)</procedure> |
---|
216 | returns two sublist of a typed list. In the first one all items pass |
---|
217 | ok?, in the second no one does that. |
---|
218 | |
---|
219 | ==== list-adjoin |
---|
220 | <procedure>(list-adjoin item tlst)</procedure> |
---|
221 | adds an item to a typed list only if it is not allready a member. |
---|
222 | |
---|
223 | ==== list-equal? |
---|
224 | <procedure>(list-equal? tlst0 tlst1)</procedure> |
---|
225 | Are the typed argument lists equal?. All items are compared with equ?, |
---|
226 | the other exported routine of the functor argument. |
---|
227 | |
---|
228 | ==== list-memp |
---|
229 | <procedure>(list-memp ok? tlst)</procedure> |
---|
230 | returns the sublist of a typed list, starting with the first item |
---|
231 | passing ok?. |
---|
232 | |
---|
233 | ==== list-member |
---|
234 | <procedure>(list-member item tlst)</procedure> |
---|
235 | like member, items are compared with equ?. |
---|
236 | |
---|
237 | ==== list-remp |
---|
238 | <procedure>(list-remp ok? tlst)</procedure> |
---|
239 | removes all items from a typed list, which pass the ok? test. |
---|
240 | |
---|
241 | ==== list-remove |
---|
242 | <procedure>(list-remove item tlst)</procedure> |
---|
243 | removes all items from a typed list which are equ? to item. |
---|
244 | |
---|
245 | ==== list-remove-dups |
---|
246 | <procedure>(list-remove-dups tlst)</procedure> |
---|
247 | removes all duplicates, compared with equ?. |
---|
248 | |
---|
249 | ==== list-assp |
---|
250 | <procedure>(list-assp ok? tlst)</procedure> |
---|
251 | returns the first pair of a typed-list of pairs, whose car passes the |
---|
252 | ok? test. |
---|
253 | |
---|
254 | ==== list-assoc |
---|
255 | <procedure>(list-assoc item tlst)</procedure> |
---|
256 | like assoc for typed lists of pairs, the cars of which must pass the |
---|
257 | type predicate type? and the cars are compared with equ?. |
---|
258 | |
---|
259 | ==== list-fold-left |
---|
260 | <procedure>(list-fold-left op base . tlsts)</procedure> |
---|
261 | like fold-left in R7RS. |
---|
262 | |
---|
263 | ==== list-fold-right |
---|
264 | <procedure>(list-fold-right op base . tlsts)</procedure> |
---|
265 | like fold-right in R7RS. |
---|
266 | |
---|
267 | ==== list-merge |
---|
268 | <procedure>(list-merge <? tlst0 tlst1)</procedure> |
---|
269 | merges two <?-sorted typed lists. |
---|
270 | |
---|
271 | ==== list-sort |
---|
272 | <procedure>(list-sort <? tlst)</procedure> |
---|
273 | merge sorts a typed list according to <?. |
---|
274 | |
---|
275 | ==== |
---|
276 | <procedure>(list-sorted? <? tlst)</procedure> |
---|
277 | is a typed list sorted with respect ot <?. |
---|
278 | |
---|
279 | ==== list-zip |
---|
280 | <procedure>(list-zip tlst0 tlst1)</procedure> |
---|
281 | combines two typed lists in zip mode, i.e. alternating between the items |
---|
282 | of the left and right argument list. |
---|
283 | |
---|
284 | ==== list-interpose |
---|
285 | <procedure>(list-interpose sep tlst)</procedure> |
---|
286 | interposes a separator sep of type type between the list's items. |
---|
287 | |
---|
288 | ==== list-every? |
---|
289 | <procedure>(list-every? ok? tlst)</procedure> |
---|
290 | passes every item the ok? test? |
---|
291 | |
---|
292 | ==== list-some |
---|
293 | <procedure>(list-some ok? tlst)</procedure> |
---|
294 | returns the first item passing the ok? test. |
---|
295 | |
---|
296 | ==== list-not-every? |
---|
297 | <procedure>(list-not-every? ok? tlst)</procedure> |
---|
298 | checks if not every item of tlst passes the ok? test. |
---|
299 | |
---|
300 | ==== list-not-any? |
---|
301 | <procedure>(list-not-any? ok? tlst)</procedure> |
---|
302 | checks if not any item of tlst passes the ok? test. |
---|
303 | |
---|
304 | ==== list-bind |
---|
305 | |
---|
306 | <macro>(list-bind (x ... . xs) tlst xpr . xprs)</macro> |
---|
307 | |
---|
308 | This macro allows for general pattern matching of typed lists. A more |
---|
309 | featurefull solution would be to use the bindings macro |
---|
310 | |
---|
311 | <enscript highlight=scheme> |
---|
312 | (use bindings) |
---|
313 | (seq-length-ref-tail! typed-list? |
---|
314 | list-length |
---|
315 | (lambda (tlst item) (list-item item tlst)) |
---|
316 | (lambda (tlst item) (list-drop item tlst))) |
---|
317 | </enscript> |
---|
318 | |
---|
319 | Then you can use bind and friends and freely mix typed lists with other |
---|
320 | sequence types. |
---|
321 | |
---|
322 | === Generated functions of the set datatype |
---|
323 | |
---|
324 | ==== sets |
---|
325 | <procedure>(sets [sym]</procedure> |
---|
326 | documentation procedure. |
---|
327 | |
---|
328 | ==== typed-list->set |
---|
329 | <procedure>(typed-list->set lst)</procedure> |
---|
330 | fundamental datatype constructor. Typed sets are implemented as |
---|
331 | equivalence classes of typed lists. |
---|
332 | |
---|
333 | ==== set? |
---|
334 | <procedure>(set? xpr)</procedure> |
---|
335 | evaluates an expression to a typed set? |
---|
336 | |
---|
337 | ==== set |
---|
338 | <procedure>(set . args)</procedure> |
---|
339 | set constructor. All args must pass the type? test. |
---|
340 | |
---|
341 | ==== set->typed-list |
---|
342 | <procedure>(set->typed-list st)</procedure> |
---|
343 | forget set equality, set=, and return to list equality, list-equal?. |
---|
344 | |
---|
345 | ==== set-in? |
---|
346 | <procedure>(set-in? item st)</procedure> |
---|
347 | is item of type type? a member of the set st? |
---|
348 | |
---|
349 | ==== set<= |
---|
350 | <procedure>(set<= set0 set1)</procedure> |
---|
351 | subset relation. |
---|
352 | |
---|
353 | ==== set>= |
---|
354 | <procedure>(set>= set0 set1)</procedure> |
---|
355 | subset relation. |
---|
356 | |
---|
357 | ==== set= |
---|
358 | <procedure>(set= set0 set1)</procedure> |
---|
359 | set equality. |
---|
360 | |
---|
361 | ==== set-filter |
---|
362 | <procedure>(set-filter ok? st)</procedure> |
---|
363 | filters a set, returning two subsets. |
---|
364 | |
---|
365 | ==== set-null? |
---|
366 | <procedure>(set-null? xpr)</procedure> |
---|
367 | is the set empty? |
---|
368 | |
---|
369 | ==== set-add |
---|
370 | <procedure>(set-add item st)</procedure> |
---|
371 | adds an item to the set. |
---|
372 | |
---|
373 | ==== set-remove |
---|
374 | <procedure>(set-remove item st)</procedure> |
---|
375 | removes an item from the set, i.e. remove all items from the underlying |
---|
376 | listed list, that are equ? to item. |
---|
377 | |
---|
378 | ==== set-cardinality |
---|
379 | <procedure>(set-cardinality st)</procedure> |
---|
380 | returns the number of (different!) items in a set. |
---|
381 | |
---|
382 | ==== set-difference |
---|
383 | <procedure>(set-difference set0 set1)</procedure> |
---|
384 | removes all items of set1 from set0. |
---|
385 | |
---|
386 | ==== set-union |
---|
387 | <procedure>(set-union . sts)</procedure> |
---|
388 | returns the set of all items of all argument sets. |
---|
389 | |
---|
390 | ==== set-intersection |
---|
391 | <procedure>(set-intersection . sts)</procedure> |
---|
392 | returns the set of items which are in all argument sets. |
---|
393 | |
---|
394 | === Examples |
---|
395 | |
---|
396 | <enscript highlight=scheme> |
---|
397 | |
---|
398 | (require-library cells datatype) |
---|
399 | (import typed-lists datatype) |
---|
400 | |
---|
401 | ;;; number-lists |
---|
402 | ;;; ------------ |
---|
403 | ;; argument module |
---|
404 | (module nums (type? equ?) |
---|
405 | (import scheme cells) |
---|
406 | (define (type? x) |
---|
407 | (or (number? x) ((cell-of? number?) x))) |
---|
408 | (define (equ? x y) |
---|
409 | (or (and (number? x) |
---|
410 | (number? y) |
---|
411 | (= x y)) |
---|
412 | (and (cell? x) |
---|
413 | (cell? y) |
---|
414 | (= (cell-ref x) |
---|
415 | (cell-ref y))))) |
---|
416 | ) |
---|
417 | |
---|
418 | ;; apply functor |
---|
419 | (module lists = (typed-lists nums)) |
---|
420 | |
---|
421 | ;; imports |
---|
422 | (import lists cells) |
---|
423 | |
---|
424 | ;; tests |
---|
425 | (define nil (list-null)) |
---|
426 | (typed-list? nil) |
---|
427 | (list-null? nil) |
---|
428 | (not (null? nil)) |
---|
429 | (define nls (list-cons 1 nil)) |
---|
430 | (typed-list? nls) |
---|
431 | (define nlst (typed-list 0 1 (cell 2) 3 4)) |
---|
432 | (typed-list? nlst) |
---|
433 | (not (list? nlst)) |
---|
434 | (= (list-apply + 1 2 (typed-list 3 4 5)) 15) |
---|
435 | (list-equal? (list-repeat 5 0) (typed-list 0 0 0 0 0)) |
---|
436 | (list-equal? (list-iterate 5 add1 0) (typed-list 0 1 2 3 4)) |
---|
437 | (list-equal? (list-iterate-while (lambda (x) (< x 5)) add1 0) |
---|
438 | (typed-list 0 1 2 3 4)) |
---|
439 | (list-equal? (list-iterate-until (lambda (x) (= x 5)) add1 0) |
---|
440 | (typed-list 0 1 2 3 4)) |
---|
441 | (list-equal? (list-zip (typed-list 1 2 3 4 5) (typed-list 10 20 30)) |
---|
442 | (typed-list 1 10 2 20 3 30 4 5)) |
---|
443 | (list-equal? (list-interpose 10 (typed-list 1 2 3 4 5)) |
---|
444 | (typed-list 1 10 2 10 3 10 4 10 5)) |
---|
445 | (list-equal? (list-drop 3 nlst) (typed-list 3 4)) |
---|
446 | (list-equal? (list-drop-while odd? (typed-list 1 3 2 4 5)) |
---|
447 | (typed-list 2 4 5)) |
---|
448 | (list-equal? (list-take-while odd? (typed-list 1 3 2 4 5)) |
---|
449 | (typed-list 1 3)) |
---|
450 | (receive (head tail) (list-split-with even? (typed-list 1 3 2 4 5)) |
---|
451 | (and (list-equal? head (typed-list 1 3)) |
---|
452 | (list-equal? tail (typed-list 2 4 5)))) |
---|
453 | (list-equal? (list-take 2 nlst) (typed-list 0 1)) |
---|
454 | (define nrest (list-rest nlst)) |
---|
455 | (typed-list? (list-null)) |
---|
456 | (list-null? (list-null)) |
---|
457 | (not (list-null? nls)) |
---|
458 | (not (typed-list? '(1 2))) |
---|
459 | (list-null? (list-rest nls)) |
---|
460 | (= (list-first nlst) 0) |
---|
461 | (typed-list? (list-reverse nlst)) |
---|
462 | (list-reverse nlst) |
---|
463 | (equal? (typed-list->untyped-list nlst) |
---|
464 | (list 0 1 (cell 2) 3 4)) |
---|
465 | (equal? (list-item 2 nlst) (cell 2)) |
---|
466 | (cell-set! (list-item 2 nlst) 20) |
---|
467 | (equal? (list-item 2 nlst) (cell 20)) |
---|
468 | (= (cell-ref (list-item 2 nlst)) 20) |
---|
469 | (= (list-length nlst) 5) |
---|
470 | (list-equal? (list-from-upto 2 4 nlst) |
---|
471 | (typed-list (cell 20) 3)) |
---|
472 | (list-equal? (list-append (typed-list 0 1 2 3) |
---|
473 | (typed-list 4 5 6)) |
---|
474 | (typed-list 0 1 2 3 4 5 6)) |
---|
475 | (list-equal? (list-append |
---|
476 | (typed-list 0) |
---|
477 | (typed-list 1) |
---|
478 | (typed-list 2) |
---|
479 | (typed-list 3 4) |
---|
480 | (typed-list 5 6 7) |
---|
481 | (typed-list 8)) |
---|
482 | (typed-list 0 1 2 3 4 5 6 7 8)) |
---|
483 | (list-equal? (list-map add1 |
---|
484 | (typed-list 0 1 2 3)) |
---|
485 | (typed-list 1 2 3 4)) |
---|
486 | (list-equal? (list-map + |
---|
487 | (typed-list 1 2 3) |
---|
488 | (typed-list 10 20 30 40)) |
---|
489 | (typed-list 11 22 33)) |
---|
490 | (list-equal? |
---|
491 | (list-mappend typed-list (typed-list 10 20 30) (typed-list 1 2 3 4 5)) |
---|
492 | (typed-list 10 1 20 2 30 3)) |
---|
493 | (list-equal? |
---|
494 | (list-fold-right list-cons (list-null) (typed-list 0 1 2 3 4)) |
---|
495 | (typed-list 0 1 2 3 4)) |
---|
496 | (list-equal? |
---|
497 | (list-fold-right list-cons (typed-list 0 1 2) (typed-list 3 4)) |
---|
498 | (typed-list 3 4 0 1 2)) |
---|
499 | (= (list-fold-right * 1 (typed-list 1 2 3 4 5)) 120) |
---|
500 | (= (list-fold-left * 1 (typed-list 1 2 3 4 5)) 120) |
---|
501 | (= (list-fold-left + 0 (typed-list 1 2 3) (typed-list 10 20 30)) 66) |
---|
502 | (equal? (list-fold-left cons '(100) (typed-list 1 2 3 4)) |
---|
503 | '(((((100) . 1) . 2) . 3) . 4)) |
---|
504 | (equal? |
---|
505 | (call-with-values |
---|
506 | (lambda () (list-reverse (typed-list 1 2 3) (typed-list 10 20 30))) |
---|
507 | list) |
---|
508 | (list (typed-list 3 2 1) (typed-list 30 20 10))) |
---|
509 | (list-equal? (list-remove 0 (typed-list 1 0 2 0 3 0 4)) |
---|
510 | (typed-list 1 2 3 4)) |
---|
511 | (list-equal? (list-merge < (typed-list 2 4 5 7 8) (typed-list 1 3 6 9 10)) |
---|
512 | (typed-list 1 2 3 4 5 6 7 8 9 10)) |
---|
513 | (not (condition-case (list-merge < (list-null) (typed-list 1 3 2)) |
---|
514 | ((exn) #f))) |
---|
515 | (list-equal? (list-sort <= (typed-list 2 0 1 4 3)) |
---|
516 | (typed-list 0 1 2 3 4)) |
---|
517 | (not (list-sorted? <= (typed-list 2 0 1 4 3))) |
---|
518 | (list-sorted? <= (typed-list 0 1 2 3 4)) |
---|
519 | (list-every? odd? (typed-list 1 3 5)) |
---|
520 | (list-every? odd? (typed-list)) |
---|
521 | (= (list-some odd? (typed-list 2 3 5)) 3) |
---|
522 | (not (list-some odd? (typed-list 2 4 6))) |
---|
523 | (list-not-every? odd? (typed-list 1 2 3)) |
---|
524 | (list-not-any? odd? (typed-list 2 4 6)) |
---|
525 | |
---|
526 | ;;; number-sets |
---|
527 | ;;; ----------- |
---|
528 | (set= |
---|
529 | (typed-list->set (typed-list 1 2 1 3 2 3)) |
---|
530 | (set 3 2 1)) |
---|
531 | (set? (set 1 2 3)) |
---|
532 | (set? (set 1 2 2 3)) |
---|
533 | (set= (set 2 1 3) (set 1 2 2 3)) |
---|
534 | (set-in? 2 (set 1 1 2 3)) |
---|
535 | (set<= (set 2 1 2) (set 4 1 2 3 4)) |
---|
536 | (set= |
---|
537 | (set-add 0 (set 1 2 3)) |
---|
538 | (set 0 1 2 3)) |
---|
539 | (set= |
---|
540 | (set-add 2 (set 1 2 3)) |
---|
541 | (set 1 2 3)) |
---|
542 | (= (set-cardinality (set 2 1 2 3 2)) 3) |
---|
543 | (set= |
---|
544 | (set-remove 2 (set 2 1 2 3 2)) |
---|
545 | (set 1 3)) |
---|
546 | (set= |
---|
547 | (set 0 1 1 0 2 3 2) |
---|
548 | (set 2 3 0 1)) |
---|
549 | (set= |
---|
550 | (set-difference (set 0 2 1 3) (set 1 1)) |
---|
551 | (set 0 2 3)) |
---|
552 | (set= |
---|
553 | (set-union (set 1 2) (set 2 3) (set 3 4)) |
---|
554 | (set 1 2 3 4)) |
---|
555 | (set= |
---|
556 | (set-intersection (set 1 2 3 4) (set 2 3 5) (set 3 4)) |
---|
557 | (set 3)) |
---|
558 | (set= (set-filter odd? (set 2 1 3 3 1 1)) (set 3 1)) |
---|
559 | |
---|
560 | ;;; symbol-lists |
---|
561 | ;;; ------------ |
---|
562 | ;; argument module |
---|
563 | (module symbols (equ? type?) |
---|
564 | (import scheme) |
---|
565 | (define equ? eq?) |
---|
566 | (define type? symbol?)) |
---|
567 | |
---|
568 | ;; apply functor |
---|
569 | (module symbol-lists = (typed-lists symbols)) |
---|
570 | |
---|
571 | ;; imports |
---|
572 | (import (prefix symbol-lists sym-)) |
---|
573 | |
---|
574 | ;; tests |
---|
575 | (sym-list-equal? |
---|
576 | (sym-list-append (sym-typed-list 'a 'b) |
---|
577 | (sym-typed-list 'c)) |
---|
578 | (sym-typed-list 'a 'b 'c)) |
---|
579 | (equal? |
---|
580 | (sym-list-bind (x y z) (sym-typed-list 'a 'b 'c) (list x y z)) |
---|
581 | '(a b c)) |
---|
582 | (sym-list-equal? |
---|
583 | (sym-list-bind (x . y) (sym-typed-list 'a 'b 'c) y) |
---|
584 | (sym-typed-list 'b 'c)) |
---|
585 | (sym-list-null? (sym-list-bind x (sym-list-null) x)) |
---|
586 | (sym-list-bind () (sym-list-null) #t) |
---|
587 | |
---|
588 | </enscript> |
---|
589 | |
---|
590 | === Requirements |
---|
591 | |
---|
592 | datatype |
---|
593 | |
---|
594 | == Last update |
---|
595 | |
---|
596 | Aug 17, 2014 |
---|
597 | |
---|
598 | == Author |
---|
599 | |
---|
600 | [[/users/juergen-lorenz|Juergen Lorenz]] |
---|
601 | |
---|
602 | == License |
---|
603 | |
---|
604 | Copyright (c) 2014, Juergen Lorenz |
---|
605 | All rights reserved. |
---|
606 | |
---|
607 | Redistribution and use in source and binary forms, with or without |
---|
608 | modification, are permitted provided that the following conditions are |
---|
609 | met: |
---|
610 | |
---|
611 | Redistributions of source code must retain the above copyright |
---|
612 | notice, this list of conditions and the following disclaimer. |
---|
613 | |
---|
614 | Redistributions in binary form must reproduce the above copyright |
---|
615 | notice, this list of conditions and the following disclaimer in the |
---|
616 | documentation and/or other materials provided with the distribution. |
---|
617 | Neither the name of the author nor the names of its contributors may be |
---|
618 | used to endorse or promote products derived from this software without |
---|
619 | specific prior written permission. |
---|
620 | |
---|
621 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS |
---|
622 | IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED |
---|
623 | TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A |
---|
624 | PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
---|
625 | HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
---|
626 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED |
---|
627 | TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
---|
628 | PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
---|
629 | LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
---|
630 | NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
---|
631 | SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
---|
632 | |
---|
633 | == Version History |
---|
634 | |
---|
635 | ; 1.0 : functor implementation |
---|
636 | ; 0.1 : initial import |
---|