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

Last change on this file since 31239 was 31239, checked in by juergen, 7 years ago

typed-lists version 1.2 added list-cons-sorted

File size: 20.1 KB
Line 
1[[tags: egg]]
2[[toc:]]
3
4
5== Rationale
6
7Scheme lists are mutable and untyped. The list types produced with
8this functor module 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-cons-sorted
280<procedure>(list-cons-sorted <? item tlst)</procedure>
281inserts an item into a sorted typed list without disturbing order.
282
283==== list-zip
284<procedure>(list-zip tlst0 tlst1)</procedure>
285combines two typed lists in zip mode, i.e. alternating between the items
286of the left and right argument list.
287
288==== list-interpose
289<procedure>(list-interpose sep tlst)</procedure>
290interposes a separator sep of type type between the list's items.
291
292==== list-every?
293<procedure>(list-every? ok? tlst)</procedure>
294passes every item the ok? test?
295
296==== list-some
297<procedure>(list-some ok? tlst)</procedure>
298returns the first item passing the ok? test.
299
300==== list-not-every?
301<procedure>(list-not-every? ok? tlst)</procedure>
302checks if not every item of tlst passes the ok? test.
303
304==== list-not-any?
305<procedure>(list-not-any? ok? tlst)</procedure>
306checks if not any item of tlst passes the ok? test.
307
308==== list-in?
309<procedure>(list-in? tlst0 tlst1)</procedure>
310checks, if the typed list tlst0 is a contiguous sublist of the
311typed-list tlst1.
312
313==== list-bind
314
315<macro>(list-bind (x ... . xs) tlst xpr . xprs)</macro>
316
317This macro allows for general pattern matching of typed lists. A more
318featurefull solution would be to use the bindings macro
319
320<enscript highlight=scheme>
321(use bindings)
322(seq-length-ref-tail! typed-list?
323                      list-length
324                      (lambda (tlst item) (list-item item tlst))
325                      (lambda (tlst item) (list-drop item tlst)))
326</enscript>
327
328Then you can use bind and friends and freely mix typed lists with other
329sequence types.
330
331=== Generated functions of the set datatype
332
333==== sets
334<procedure>(sets [sym]</procedure>
335documentation procedure.
336
337==== typed-list->set
338<procedure>(typed-list->set lst)</procedure>
339fundamental datatype constructor. Typed sets are implemented as
340equivalence classes of typed lists.
341
342==== set?
343<procedure>(set? xpr)</procedure>
344evaluates an expression to a typed set?
345
346==== set
347<procedure>(set . args)</procedure>
348set constructor. All args must pass the type? test.
349
350==== set->typed-list
351<procedure>(set->typed-list st)</procedure>
352forget set equality, set=, and return to list equality, list-equal?.
353
354==== set-in?
355<procedure>(set-in? item st)</procedure>
356is item of type type? a member of the set st?
357
358==== set<=
359<procedure>(set<= set0 set1)</procedure>
360subset relation.
361
362==== set>=
363<procedure>(set>= set0 set1)</procedure>
364subset relation.
365
366==== set=
367<procedure>(set= set0 set1)</procedure>
368set equality.
369
370==== set-filter
371<procedure>(set-filter ok? st)</procedure>
372filters a set, returning two subsets.
373
374==== set-null?
375<procedure>(set-null? xpr)</procedure>
376is the set empty?
377
378==== set-add
379<procedure>(set-add item st)</procedure>
380adds an item to the set.
381
382==== set-remove
383<procedure>(set-remove item st)</procedure>
384removes an item from the set, i.e. remove all items from the underlying
385listed list, that are equ? to item.
386
387==== set-cardinality
388<procedure>(set-cardinality st)</procedure>
389returns the number of (different!) items in a set.
390
391==== set-difference
392<procedure>(set-difference set0 set1)</procedure>
393removes all items of set1 from set0.
394
395==== set-union
396<procedure>(set-union . sts)</procedure>
397returns the set of all items of all argument sets.
398
399==== set-intersection
400<procedure>(set-intersection . sts)</procedure>
401returns the set of items which are in all argument sets.
402
403=== Examples
404
405<enscript highlight=scheme>
406
407(require-library cells datatype)
408(import typed-lists datatype)
409
410;;; number-lists
411;;; ------------
412;; argument module
413(module nums (type? equ?)
414  (import scheme cells)
415  (define (type? x)
416    (or (number? x) ((cell-of? number?) x)))
417  (define (equ? x y)
418    (or (and (number? x)
419             (number? y)
420             (= x y))
421        (and (cell? x)
422             (cell? y)
423             (= (cell-ref x)
424                (cell-ref y)))))
425  )
426
427;; apply functor
428(module lists = (typed-lists nums))
429
430;; imports
431(import lists cells)
432 
433;; tests
434(define nil (list-null))
435(typed-list? nil)
436(list-null? nil)
437(not (null? nil))
438(define nls (list-cons 1 nil))
439(typed-list? nls)
440(define nlst (typed-list 0 1 (cell 2) 3 4))
441(typed-list? nlst)
442(not (list? nlst))
443(= (list-apply + 1 2 (typed-list 3 4 5)) 15)
444(list-equal? (list-repeat 5 0) (typed-list 0 0 0 0 0))
445(list-equal? (list-iterate 5 add1 0) (typed-list 0 1 2 3 4))
446(list-equal? (list-iterate-while (lambda (x) (< x 5)) add1 0)
447             (typed-list 0 1 2 3 4))
448(list-equal? (list-iterate-until (lambda (x) (= x 5)) add1 0)
449             (typed-list 0 1 2 3 4))
450(list-equal? (list-zip (typed-list 1 2 3 4 5) (typed-list 10 20 30))
451             (typed-list 1 10 2 20 3 30 4 5))
452(list-equal? (list-interpose 10 (typed-list 1 2 3 4 5))
453             (typed-list 1 10 2 10 3 10 4 10 5))
454(list-equal? (list-drop 3 nlst) (typed-list 3 4))
455(list-equal? (list-drop-while odd? (typed-list 1 3 2 4 5))
456             (typed-list 2 4 5))
457(list-equal? (list-take-while odd? (typed-list 1 3 2 4 5))
458             (typed-list 1 3))
459(receive (head tail) (list-split-with even? (typed-list 1 3 2 4 5))
460  (and (list-equal? head (typed-list 1 3))
461       (list-equal? tail (typed-list 2 4 5))))
462(list-equal? (list-take 2 nlst) (typed-list 0 1))
463(define nrest (list-rest nlst))
464(typed-list? (list-null))
465(list-null? (list-null))
466(not (list-null? nls))
467(not (typed-list? '(1 2)))
468(list-null? (list-rest nls))
469(= (list-first nlst) 0)
470(typed-list? (list-reverse nlst))
471(list-reverse nlst)
472(equal? (typed-list->untyped-list nlst)
473        (list 0 1 (cell 2) 3 4))
474(equal? (list-item 2 nlst) (cell 2))
475(cell-set! (list-item 2 nlst) 20)
476(equal? (list-item 2 nlst) (cell 20))
477(= (cell-ref (list-item 2 nlst)) 20)
478(= (list-length nlst) 5)
479(list-equal? (list-from-upto 2 4 nlst)
480             (typed-list (cell 20) 3))
481(list-equal?  (list-append (typed-list 0 1 2 3)
482                           (typed-list 4 5 6))
483              (typed-list 0 1 2 3 4 5 6))
484(list-equal? (list-append
485               (typed-list 0)
486               (typed-list 1)
487               (typed-list 2)
488               (typed-list 3 4)
489               (typed-list 5 6 7)
490               (typed-list 8))
491             (typed-list 0 1 2 3 4 5 6 7 8))
492(list-equal? (list-map add1
493                       (typed-list 0 1 2 3))
494             (typed-list 1 2 3 4))
495(list-equal? (list-map +
496                       (typed-list 1 2 3)
497                       (typed-list 10 20 30 40))
498             (typed-list 11 22 33))
499(list-equal?
500  (list-mappend typed-list (typed-list 10 20 30) (typed-list 1 2 3 4 5))
501  (typed-list 10 1 20 2 30 3))
502(list-equal?
503  (list-fold-right list-cons (list-null) (typed-list 0 1 2 3 4))
504  (typed-list 0 1 2 3 4))
505(list-equal?
506  (list-fold-right list-cons (typed-list 0 1 2) (typed-list 3 4))
507  (typed-list 3 4 0 1 2))
508(= (list-fold-right * 1 (typed-list 1 2 3 4 5)) 120)
509(= (list-fold-left * 1 (typed-list 1 2 3 4 5)) 120)
510(= (list-fold-left + 0 (typed-list 1 2 3) (typed-list 10 20 30)) 66)
511(equal? (list-fold-left cons '(100) (typed-list 1 2 3 4))
512        '(((((100) . 1) . 2) . 3) . 4))
513(equal?
514  (call-with-values
515    (lambda () (list-reverse (typed-list 1 2 3) (typed-list 10 20 30)))
516    list)
517  (list (typed-list 3 2 1) (typed-list 30 20 10)))
518(list-equal? (list-remove 0 (typed-list 1 0 2 0 3 0 4))
519             (typed-list 1 2 3 4))
520(list-equal? (list-merge < (typed-list 2 4 5 7 8) (typed-list 1 3 6 9 10))
521             (typed-list 1 2 3 4 5 6 7 8 9 10))
522(not (condition-case (list-merge < (list-null) (typed-list 1 3 2))
523       ((exn) #f)))
524(list-equal? (list-sort <= (typed-list 2 0 1 4 3))
525             (typed-list 0 1 2 3 4))
526(not (list-sorted? <= (typed-list 2 0 1 4 3)))
527(list-sorted? <= (typed-list 0 1 2 3 4))
528(list-equal?
529  (list-cons-sorted <= 2 (typed-list 0 1 2 3 4))
530  (typed-list 0 1 2 2 3 4))
531(list-equal?
532  (list-cons-sorted <= 5 (typed-list 0 1 2 3 4))
533  (typed-list 0 1 2 3 4 5))
534(list-every? odd? (typed-list 1 3 5))
535(list-every? odd? (typed-list))
536(= (list-some odd? (typed-list 2 3 5)) 3)
537(not (list-some odd? (typed-list 2 4 6)))
538(list-not-every? odd? (typed-list 1 2 3))
539(list-not-any? odd? (typed-list 2 4 6))
540(list-in? (typed-list 2 3) (typed-list 1 2 3))
541(not (list-in? (typed-list 1 2 3) (typed-list 2 3)))
542(not (list-in? (typed-list 1 2 3) (typed-list 2 1 3)))
543(list-in? (typed-list) (typed-list 2 3))
544
545;;; number-sets
546;;; -----------
547(set=
548  (typed-list->set (typed-list 1 2 1 3 2 3))
549  (set 3 2 1))
550(set? (set 1 2 3))
551(set? (set 1 2 2 3))
552(set= (set 2 1 3) (set 1 2 2 3))
553(set-in? 2 (set 1 1 2 3))
554(set<= (set 2 1 2) (set 4 1 2 3 4))
555(set=
556  (set-add 0 (set 1 2 3))
557  (set 0 1 2 3))
558(set=
559  (set-add 2 (set 1 2 3))
560  (set 1 2 3))
561(= (set-cardinality (set 2 1 2 3 2)) 3)
562(set=
563  (set-remove 2 (set 2 1 2 3 2))
564  (set 1 3))
565(set=
566  (set 0 1 1 0 2 3 2)
567  (set 2 3 0 1))
568(set=
569  (set-difference (set 0 2 1 3) (set 1 1))
570  (set 0 2 3))
571(set=
572  (set-union (set 1 2) (set 2 3) (set 3 4))
573  (set 1 2 3 4))
574(set=
575  (set-intersection (set 1 2 3 4) (set 2 3 5) (set 3 4))
576  (set 3))
577(set= (set-filter odd? (set 2 1 3 3 1 1)) (set 3 1))
578
579;;; symbol-lists
580;;; ------------
581;; argument module
582(module symbols (equ? type?)
583  (import scheme)
584  (define equ? eq?)
585  (define type? symbol?))
586
587;; apply functor
588(module symbol-lists = (typed-lists symbols))
589
590;; imports
591(import (prefix symbol-lists sym-))
592
593;; tests
594(sym-list-equal?
595  (sym-list-append (sym-typed-list 'a 'b)
596               (sym-typed-list 'c))
597  (sym-typed-list 'a 'b 'c))
598(equal?
599  (sym-list-bind (x y z) (sym-typed-list 'a 'b 'c) (list x y z))
600  '(a b c))
601(sym-list-equal?
602    (sym-list-bind (x . y) (sym-typed-list 'a 'b 'c) y)
603  (sym-typed-list 'b 'c))
604(sym-list-null? (sym-list-bind x (sym-list-null) x))
605(sym-list-bind () (sym-list-null) #t)
606
607;;; pair-lists
608;;; ----------
609;; argument module
610(module pairs (type? equ?)
611  (import scheme)
612  (define (type? x)
613    (and (pair? x) (number? (car x)) (string? (cdr x))))
614  (define equ? equal?))
615
616;; apply functor
617(module pair-lists = (typed-lists pairs))
618
619;; tests
620(import (prefix pair-lists nsp-))
621(define nspl (nsp-typed-list (cons 1 "one") (cons 2 "two") (cons 3 "three")))
622(equal? (nsp-list-assoc 2 nspl) '(2 . "two"))
623(not (nsp-list-assp zero? nspl))
624</enscript>
625
626=== Requirements
627
628datatype
629
630== Last update
631
632Aug 18, 2014
633
634== Author
635
636[[/users/juergen-lorenz|Juergen Lorenz]]
637
638== License
639
640 Copyright (c) 2014, Juergen Lorenz
641 All rights reserved.
642
643 Redistribution and use in source and binary forms, with or without
644 modification, are permitted provided that the following conditions are
645 met:
646 
647 Redistributions of source code must retain the above copyright
648 notice, this list of conditions and the following disclaimer.
649 
650 Redistributions in binary form must reproduce the above copyright
651 notice, this list of conditions and the following disclaimer in the
652 documentation and/or other materials provided with the distribution.
653 Neither the name of the author nor the names of its contributors may be
654 used to endorse or promote products derived from this software without
655 specific prior written permission.
656   
657 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
658 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
659 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
660 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
661 HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
662 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
663 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
664 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
665 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
666 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
667 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
668
669== Version History
670
671; 1.2 : list-cons-sorted added
672; 1.1 : list-bind corrected, list-in? added
673; 1.0 : functor implementation
674; 0.1 : initial import
Note: See TracBrowser for help on using the repository browser.