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

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

typed-lists docu again

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