source: project/wiki/eggref/4/typed-lists @ 31221

Last change on this file since 31221 was 31221, checked in by juergen, 5 years ago

typed-lists 1.0 docu

File size: 18.9 KB
Line 
1[[tags: egg]]
2[[toc:]]
3
4
5== Rationale
6
7Scheme lists are mutable and untyped. The list types produced with
8this module, a functor, are immutable and typed.
9
10Concerning mutability, Scheme's authors, G. J. Sussman and G. L. Steele jr.
11in their paper "The First Report on Scheme Revisited", Higher-Order and
12Symbolic Computation, 11, 399-404 (1998), argued:
13
14"We also now believe that Carl Hewitt was right: we would have been
15better off to have introduced cells as a separate, primitive kind of
16object, rather than allowing assignment to any and every lambda-bound
17variable"
18
19Well, cells -- or boxes, if you prefer -- exist as modules, so restricted
20mutability can be provided by accepting cells -- or boxes -- as item types.
21
22Typing of list arguments on the other hand improves security of the
23implemented functions on the one side, but are cumbersome to use on the
24other:  After all, we don't want to write the same routines for lists of
25numbers, lists of strings, lists of symbols, ... or what have you.
26
27My first solution to this problem in version 0.1 was really pedestrian,
28a huge macro which generated a bunch of procedures all prefixed with
29some symbol depending on the use of the macro. Well, that worked, but it
30was rather ugly. There is a much more elegant and flexible solution, which
31depends on functors, which are unfortunately rarely known by programmers.
32
33Recall, that functors are to Chicken modules what functions are to
34Chicken values. In other words, functors are defined with abstract module
35parameters, which produce modules only when fed with concrete module
36arguments. This is exactly what we need. The abstract module parameter
37should export the names of the routines to be replaced by the equally
38named routines of the concrete module argument. The generated module can
39than be imported with a prefix of your liking or without one, if only
40one version of the functor value is used.
41
42Hence, this module implements a functor, typed-lists, depending on a
43module parameter which must supply two exports, named equ? and type?.
44The resulting code -- when applied to a concrete module which implements
45these two routines -- defines list and set datatypes, to be more
46precise, immutable typed lists and immutable typed sets, the latter
47being equivalence classes of the former.
48
49Note, that these typed lists don't pass the list? predicate. They
50are different creatures, created with define-datatype and accessed with
51cases from the datatype module.
52
53=== typed-lists
54
55the 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
80Most of the names start with a list- prefix and work the same as the
81equally named ordinary Scheme routines without that prefix.
82
83Note the order of arguments: typed lists are consistently the last ones
84and named tlst.
85
86==== list-null
87<procedure>(list-null)</procedure>
88the fundamental datatype-constructor of an empty typed list.
89
90==== list-cons
91<procedure>(list-cons item tlst)</procedure>
92the fundamental datatype-constructor consing an item to a tlist while
93checking, if it passes the type? test, one of the two routines exported by
94the argument module of the functor.
95
96==== typed-lists
97<procedure>(typed-lists [sym])</procedure>
98documentation procedure.
99
100==== typed-list?
101<procedure>(typed-list? xpr)</procedure>
102type predicate.
103
104==== typed-list
105<procedure>(typed-list . args)</procedure>
106constructor. All args must pass type?.
107
108==== untyped-list->typed-list
109<procedure>(untyped-list->typed-list lst)</procedure>
110another constructor.
111
112==== repeat
113<procedure>(list-repeat n x)</procedure>
114constructs a typed list of length n with items all x of type?.
115
116==== list-iterate
117<procedure>(list-iterate n fn x)</procedure>
118constructs a typed list of length n by successively applying fn to x.
119fn must map type? items to type? itesm.
120
121==== list-iterate-while
122<procedure>(list-iterate-while ok? fn x)</procedure>
123constructs a typed list by successively applying fn to x as long as ok?
124returns #t.
125fn must map type? items to type? itesm.
126
127==== list-iterate-until
128<procedure>(list-iterate-until ok? fn x)</procedure>
129constructs a typed list by successively applying fn to x as long as ok?
130returns #f.
131fn must map type? items to type? itesm.
132
133==== typed-list->untyped-list
134<procedure>(typed-list->untyped-list lst)</procedure>
135strips type information and immutability. The returned list is a normal
136Scheme list.
137
138==== list-apply
139<procedure>(list-apply fn . args)</procedure>
140like apply, but the last argument must be a typed list.
141
142==== list-null?
143<procedure>(list-null? xpr)</procedure>
144is xpr an empty typed list?
145
146==== list-first
147<procedure>(list-first tlst)</procedure>
148like car but with arguments in reversed order.
149
150==== list-rest
151<procedure>(list-rest tlst)</procedure>
152like cdr but with arguments in reversed order.
153
154==== list-reverse
155<procedure>(list-reverse . tlsts)</procedure>
156like reverse, but can reverse typed lists of equal length
157simultaneously.
158
159==== list-length
160<procedure>(list-length tlst)</procedure>
161like length.
162
163==== list-from-upto
164<procedure>(list-from-upto from upto tlst)</procedure>
165like sublist.
166
167==== list-item
168<procedure>(list-item k tlst)</procedure>
169like list-ref, but with reversed argument order.
170
171==== list-split-at
172<procedure>(list-split-at k tlst)</procedure>
173splits a typed list at index k returning two sublist values, the head and the
174tail.
175
176==== list-split-with
177<procedure>(list-split-with ok? tlst)</procedure>
178splits a typed list at the first item passing the ok? predicate.
179Returns two sublists.
180
181==== list-drop
182<procedure>(list-drop k tlst)</procedure>
183like list-tail, but with revrsed argument order.
184
185==== list-drop-while
186<procedure>(list-drop-while ok? tlst)</procedure>
187drops the first items as long as they pass the ok? predicate.
188
189==== list-take
190<procedure>(list-take k tlst)</procedure>
191returns 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>
195returns the longest sublist of a typed list where all items pass ok?
196starting from index 0.
197
198==== list-append
199<procedure>(list-append . tlsts)</procedure>
200like append.
201
202==== list-map
203<procedure>(list-map fn . tlsts)</procedure>
204like map.
205
206==== list-mappend
207<procedure>(list-mappend fn . tlsts)</procedure>
208combination of map and append.
209
210==== list-for-each
211<procedure>(list-for-each fn . tlsts)</procedure>
212like for-each.
213
214==== list-filter
215<procedure>(list-filter ok? tlst)</procedure>
216returns two sublist of a typed list. In the first one all items pass
217ok?, in the second no one does that.
218
219==== list-adjoin
220<procedure>(list-adjoin item tlst)</procedure>
221adds 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>
225Are the typed argument lists equal?. All items are compared with equ?,
226the other exported routine of the functor argument.
227
228==== list-memp
229<procedure>(list-memp ok? tlst)</procedure>
230returns the sublist of a typed list, starting with the first item
231passing ok?.
232
233==== list-member
234<procedure>(list-member item tlst)</procedure>
235like member, items are compared with equ?.
236
237==== list-remp
238<procedure>(list-remp ok? tlst)</procedure>
239removes all items from a typed list, which pass the ok? test.
240
241==== list-remove
242<procedure>(list-remove item tlst)</procedure>
243removes all items from a typed list which are equ? to item.
244
245==== list-remove-dups
246<procedure>(list-remove-dups tlst)</procedure>
247removes all duplicates, compared with equ?.
248
249==== list-assp
250<procedure>(list-assp ok? tlst)</procedure>
251returns the first pair of a typed-list of pairs, whose car passes the
252ok? test.
253
254==== list-assoc
255<procedure>(list-assoc item tlst)</procedure>
256like assoc for typed lists of pairs, the cars of which must pass the
257type predicate type? and the cars are compared with equ?.
258
259==== list-fold-left
260<procedure>(list-fold-left op base . tlsts)</procedure>
261like fold-left in R7RS.
262
263==== list-fold-right
264<procedure>(list-fold-right op base . tlsts)</procedure>
265like fold-right in R7RS.
266
267==== list-merge
268<procedure>(list-merge <? tlst0 tlst1)</procedure>
269merges two <?-sorted typed lists.
270
271==== list-sort
272<procedure>(list-sort <? tlst)</procedure>
273merge sorts a typed list according to <?.
274
275====
276<procedure>(list-sorted? <? tlst)</procedure>
277is a typed list sorted with respect ot <?.
278
279==== list-zip
280<procedure>(list-zip tlst0 tlst1)</procedure>
281combines two typed lists in zip mode, i.e. alternating between the items
282of the left and right argument list.
283
284==== list-interpose
285<procedure>(list-interpose sep tlst)</procedure>
286interposes a separator sep of type type between the list's items.
287
288==== list-every?
289<procedure>(list-every? ok? tlst)</procedure>
290passes every item the ok? test?
291
292==== list-some
293<procedure>(list-some ok? tlst)</procedure>
294returns the first item passing the ok? test.
295
296==== list-not-every?
297<procedure>(list-not-every? ok? tlst)</procedure>
298checks if not every item of tlst passes the ok? test.
299
300==== list-not-any?
301<procedure>(list-not-any? ok? tlst)</procedure>
302checks 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
308This macro allows for general pattern matching of typed lists. A more
309featurefull 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
319Then you can use bind and friends and freely mix typed lists with other
320sequence types.
321
322=== Generated functions of the set datatype
323
324==== sets
325<procedure>(sets [sym]</procedure>
326documentation procedure.
327
328==== typed-list->set
329<procedure>(typed-list->set lst)</procedure>
330fundamental datatype constructor. Typed sets are implemented as
331equivalence classes of typed lists.
332
333==== set?
334<procedure>(set? xpr)</procedure>
335evaluates an expression to a typed set?
336
337==== set
338<procedure>(set . args)</procedure>
339set constructor. All args must pass the type? test.
340
341==== set->typed-list
342<procedure>(set->typed-list st)</procedure>
343forget set equality, set=, and return to list equality, list-equal?.
344
345==== set-in?
346<procedure>(set-in? item st)</procedure>
347is item of type type? a member of the set st?
348
349==== set<=
350<procedure>(set<= set0 set1)</procedure>
351subset relation.
352
353==== set>=
354<procedure>(set>= set0 set1)</procedure>
355subset relation.
356
357==== set=
358<procedure>(set= set0 set1)</procedure>
359set equality.
360
361==== set-filter
362<procedure>(set-filter ok? st)</procedure>
363filters a set, returning two subsets.
364
365==== set-null?
366<procedure>(set-null? xpr)</procedure>
367is the set empty?
368
369==== set-add
370<procedure>(set-add item st)</procedure>
371adds an item to the set.
372
373==== set-remove
374<procedure>(set-remove item st)</procedure>
375removes an item from the set, i.e. remove all items from the underlying
376listed list, that are equ? to item.
377
378==== set-cardinality
379<procedure>(set-cardinality st)</procedure>
380returns the number of (different!) items in a set.
381
382==== set-difference
383<procedure>(set-difference set0 set1)</procedure>
384removes all items of set1 from set0.
385
386==== set-union
387<procedure>(set-union . sts)</procedure>
388returns the set of all items of all argument sets.
389
390==== set-intersection
391<procedure>(set-intersection . sts)</procedure>
392returns 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
592datatype
593
594== Last update
595
596Aug 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
Note: See TracBrowser for help on using the repository browser.