You are looking at historical revision 31220 of this page. It may differ significantly from its current revision.

• egg

Rationale

Scheme lists are mutable and untyped. The list types produced with this module, a functor, ar immutable and typed.

Concerning mutability, Scheme's authors, G. J. Sussman and G. L. Steele jr. in their paper "The First Report on Scheme Revisited", Higher-Order and Symbolic Computation, 11, 399-404 (1998), argued:

"We also now believe that Carl Hewitt was right: we would have been better off to have introduced cells as a separate, primitive kind of object, rather than allowing assignment to any and every lambda-bound variable"

Well, cells -- or boxes, if you prefer -- exist as modules, so restricted mutability can be provided by accepting cells -- or boxes -- as item types.

Typing of list arguments on the other hand improves security of the implemented functions on the one side, but are cumbersome to use on the other: After all, we don't want to write the same routines for lists of numbers, lists of strings, lists of symbols, ... or what have you.

My first solution to this problem in version 0.1 was really pedestrian, a huge macro which generated a bunch of procedures all prefixed with some symbol depending on the use of the macro. Well, that worked, but it was rather ugly. There is a much more elegant and flexible solution, which depends on functors, which are unfortunately rarely known by programmers.

Recall, that functors are to Chicken modules what functions are to Chicken values. In other words, functors are defined with abstract module parameters, which produce modules only when fed with concrete module arguments. This is exactly what we need. The abstract module parameter should export the names of the routines to be replaced by the equally named routines of the concrete module argument. The generated module can than be imported with a prefix of your liking or without one, if only one version of the functor value is used.

Hence, this module implements a functor, typed-lists, depending on a module parameter which must supply two exports, named equ? and type?. The resulting code -- when applied to a concrete module which implements these two routines -- defines list and set datatypes, to be more precise, immutable typed lists and immutable typed sets, the latter being equivalence classes of the former.

Note, that these typed lists don't pass the list? predicate. They are different creatures, created with define-datatype and accessed with cases from the datatype module.

typed-lists

the functor's name, exporting typed lists and (typed) sets.

Usage

(require-library datatype)
(import typed-lists datatype)

;; define argument module
(module arg-name (type? equ?)
  (import scheme)
  (define type? ...)
  (define equ? ...))

;; apply functor
(module val-name = (typed-lists arg-name))

;; import the functor
(import val-name)

;; now use the generated routines

Generated functions of the list datatype

Most of the names start with a list- prefix and work the same as the equally named ordinary Scheme routines without that prefix.

Note the order of arguments: typed lists are consistently the last ones and named tlst.

list-null

[procedure] (list-null)

the fundamental datatype-constructor of an empty typed list.

list-cons

[procedure] (list-cons item tlst)

the fundamental datatype-constructor consing an item to a tlist while checking, if it passes the type? test, one of the two routines exported by the argument module of the functor.

typed-lists

[procedure] (typed-lists [sym])

documentation procedure.

typed-list?

[procedure] (typed-list? xpr)

type predicate.

typed-list

[procedure] (typed-list . args)

constructor. All args must pass type?.

untyped-list->typed-list

[procedure] (untyped-list->typed-list lst)

another constructor.

repeat

[procedure] (list-repeat n x)

constructs a typed list of length n with items all x of type?.

list-iterate

[procedure] (list-iterate n fn x)

constructs a typed list of length n by successively applying fn to x. fn must map type? items to type? itesm.

list-iterate-while

[procedure] (list-iterate-while ok? fn x)

constructs a typed list by successively applying fn to x as long as ok? returns #t. fn must map type? items to type? itesm.

list-iterate-until

[procedure] (list-iterate-until ok? fn x)

constructs a typed list by successively applying fn to x as long as ok? returns #f. fn must map type? items to type? itesm.

typed-list->untyped-list

[procedure] (typed-list->untyped-list lst)

strips type information and immutability. The returned list is a normal Scheme list.

list-apply

[procedure] (list-apply fn . args)

like apply, but the last argument must be a typed list.

list-null?

[procedure] (list-null? xpr)

is xpr an empty typed list?

list-first

[procedure] (list-first tlst)

like car but with arguments in reversed order.

list-rest

[procedure] (list-rest tlst)

like cdr but with arguments in reversed order.

list-reverse

[procedure] (list-reverse . tlsts)

like reverse, but can reverse typed lists of equal length simultaneously.

list-length

[procedure] (list-length tlst)

like length.

list-from-upto

[procedure] (list-from-upto from upto tlst)

like sublist.

list-item

[procedure] (list-item k tlst)

like list-ref, but with reversed argument order.

list-split-at

[procedure] (list-split-at k tlst)

splits a typed list at index k returning two sublist values, the head and the tail.

list-split-with

[procedure] (list-split-with ok? tlst)

splits a typed list at the first item passing the ok? predicate. Returns two sublists.

list-drop

[procedure] (list-drop k tlst)

like list-tail, but with revrsed argument order.

list-drop-while

[procedure] (list-drop-while ok? tlst)

drops the first items as long as they pass the ok? predicate.

list-take

[procedure] (list-take k tlst)

returns the head of the typed list upto (but excluding) the index k.

list-take-while

[procedure] (list-take-while ok? tlst)

returns the longest sublist of a typed list where all items pass ok? starting from index 0.

list-append

[procedure] (list-append . tlsts)

like append.

list-map

[procedure] (list-map fn . tlsts)

like map.

list-mappend

[procedure] (list-mappend fn . tlsts)

combination of map and append.

list-for-each

[procedure] (list-for-each fn . tlsts)

like for-each.

list-filter

[procedure] (list-filter ok? tlst)

returns two sublist of a typed list. In the first one all items pass ok?, in the second no one does that.

list-adjoin

[procedure] (list-adjoin item tlst)

adds an item to a typed list only if it is not allready a member.

list-equal?

[procedure] (list-equal? tlst0 tlst1)

Are the typed argument lists equal?. All items are compared with equ?, the other exported routine of the functor argument.

list-memp

[procedure] (list-memp ok? tlst)

returns the sublist of a typed list, starting with the first item passing ok?.

list-member

[procedure] (list-member item tlst)

like member, items are compared with equ?.

list-remp

[procedure] (list-remp ok? tlst)

removes all items from a typed list, which pass the ok? test.

list-remove

[procedure] (list-remove item tlst)

removes all items from a typed list which are equ? to item.

list-remove-dups

[procedure] (list-remove-dups tlst)

removes all duplicates, compared with equ?.

list-assp

[procedure] (list-assp ok? tlst)

returns the first pair of a typed-list of pairs, whose car passes the ok? test.

list-assoc

[procedure] (list-assoc item tlst)

like assoc for typed lists of pairs, the cars of which must pass the type predicate type? and the cars are compared with equ?.

list-fold-left

[procedure] (list-fold-left op base . tlsts)

like fold-left in R7RS.

list-fold-right

[procedure] (list-fold-right op base . tlsts)

like fold-right in R7RS.

list-merge

[procedure] (list-merge <? tlst0 tlst1)

merges two <?-sorted typed lists.

list-sort

[procedure] (list-sort <? tlst)

merge sorts a typed list according to <?.

==== <procedure>(list-sorted? <? tlst)</procedure> is a typed list sorted with respect ot <?.

list-zip

[procedure] (list-zip tlst0 tlst1)

combines two typed lists in zip mode, i.e. alternating between the items of the left and right argument list.

list-interpose

[procedure] (list-interpose sep tlst)

interposes a separator sep of type type between the list's items.

list-every?

[procedure] (list-every? ok? tlst)

passes every item the ok? test?

list-some

[procedure] (list-some ok? tlst)

returns the first item passing the ok? test.

list-not-every?

[procedure] (list-not-every? ok? tlst)

checks if not every item of tlst passes the ok? test.

list-not-any?

[procedure] (list-not-any? ok? tlst)

checks if not any item of tlst passes the ok? test.

list-bind

[syntax] (list-bind (x ... . xs) tlst xpr . xprs)

This macro allows for general pattern matching of typed lists. A more featurefull solution would be to use the bindings macro

(use bindings)
(seq-length-ref-tail! typed-list?
                      list-length
                      (lambda (tlst item) (list-item item tlst))
                      (lambda (tlst item) (list-drop item tlst)))
</encscript>

Then you can use bind and friends and freely mix typed lists with other
sequence types.

=== Generated functions of the set datatype

==== sets
<procedure>(sets [sym]</procedure>
documentation procedure.

==== typed-list->set
<procedure>(typed-list->set lst)</procedure>
fundamental datatype constructor. Typed sets are implemented as
equivalence classes of typed lists.

==== set?
<procedure>(set? xpr)</procedure>
evaluates an expression to a typed set?

==== set
<procedure>(set . args)</procedure>
set constructor. All args must pass the type? test.

==== set->typed-list
<procedure>(set->typed-list st)</procedure>
forget set equality, set=, and return to list equality, list-equal?.

==== set-in?
<procedure>(set-in? item st)</procedure>
is item of type type? a member of the set st?

==== set<=
<procedure>(set<= set0 set1)</procedure>
subset relation.

==== set>=
<procedure>(set>= set0 set1)</procedure>
subset relation.

==== set=
<procedure>(set= set0 set1)</procedure>
set equality.

==== set-filter
<procedure>(set-filter ok? st)</procedure>
filters a set, returning two subsets.

==== set-null?
<procedure>(set-null? xpr)</procedure>
is the set empty?

==== set-add
<procedure>(set-add item st)</procedure>
adds an item to the set.

==== set-remove
<procedure>(set-remove item st)</procedure>
removes an item from the set, i.e. remove all items from the underlying
listed list, that are equ? to item.

==== set-cardinality
<procedure>(set-cardinality st)</procedure>
returns the number of (different!) items in a set.

==== set-difference
<procedure>(set-difference set0 set1)</procedure>
removes all items of set1 from set0.

==== set-union
<procedure>(set-union . sts)</procedure>
returns the set of all items of all argument sets.

==== set-intersection
<procedure>(set-intersection . sts)</procedure>
returns the set of items which are in all argument sets.

=== Examples

<enscript highlight=scheme>

(require-library cells datatype)
(import typed-lists datatype)

;;; number-lists
;;; ------------
;; argument module
(module nums (type? equ?)
  (import scheme cells)
  (define (type? x)
    (or (number? x) ((cell-of? number?) x)))
  (define (equ? x y)
    (or (and (number? x)
             (number? y)
             (= x y))
        (and (cell? x)
             (cell? y)
             (= (cell-ref x)
                (cell-ref y)))))
  )

;; apply functor
(module lists = (typed-lists nums))

;; imports
(import lists cells)
 
;; tests
(define nil (list-null))
(typed-list? nil)
(list-null? nil)
(not (null? nil))
(define nls (list-cons 1 nil))
(typed-list? nls)
(define nlst (typed-list 0 1 (cell 2) 3 4))
(typed-list? nlst)
(not (list? nlst))
(= (list-apply + 1 2 (typed-list 3 4 5)) 15)
(list-equal? (list-repeat 5 0) (typed-list 0 0 0 0 0))
(list-equal? (list-iterate 5 add1 0) (typed-list 0 1 2 3 4))
(list-equal? (list-iterate-while (lambda (x) (< x 5)) add1 0)
             (typed-list 0 1 2 3 4))
(list-equal? (list-iterate-until (lambda (x) (= x 5)) add1 0)
             (typed-list 0 1 2 3 4))
(list-equal? (list-zip (typed-list 1 2 3 4 5) (typed-list 10 20 30))
             (typed-list 1 10 2 20 3 30 4 5))
(list-equal? (list-interpose 10 (typed-list 1 2 3 4 5))
             (typed-list 1 10 2 10 3 10 4 10 5))
(list-equal? (list-drop 3 nlst) (typed-list 3 4))
(list-equal? (list-drop-while odd? (typed-list 1 3 2 4 5))
             (typed-list 2 4 5))
(list-equal? (list-take-while odd? (typed-list 1 3 2 4 5))
             (typed-list 1 3))
(receive (head tail) (list-split-with even? (typed-list 1 3 2 4 5))
  (and (list-equal? head (typed-list 1 3))
       (list-equal? tail (typed-list 2 4 5))))
(list-equal? (list-take 2 nlst) (typed-list 0 1))
(define nrest (list-rest nlst))
(typed-list? (list-null))
(list-null? (list-null))
(not (list-null? nls))
(not (typed-list? '(1 2)))
(list-null? (list-rest nls))
(= (list-first nlst) 0)
(typed-list? (list-reverse nlst))
(list-reverse nlst)
(equal? (typed-list->untyped-list nlst)
        (list 0 1 (cell 2) 3 4))
(equal? (list-item 2 nlst) (cell 2))
(cell-set! (list-item 2 nlst) 20)
(equal? (list-item 2 nlst) (cell 20))
(= (cell-ref (list-item 2 nlst)) 20)
(= (list-length nlst) 5)
(list-equal? (list-from-upto 2 4 nlst)
             (typed-list (cell 20) 3))
(list-equal?  (list-append (typed-list 0 1 2 3)
                           (typed-list 4 5 6))
              (typed-list 0 1 2 3 4 5 6))
(list-equal? (list-append
               (typed-list 0)
               (typed-list 1)
               (typed-list 2)
               (typed-list 3 4)
               (typed-list 5 6 7)
               (typed-list 8))
             (typed-list 0 1 2 3 4 5 6 7 8))
(list-equal? (list-map add1
                       (typed-list 0 1 2 3))
             (typed-list 1 2 3 4))
(list-equal? (list-map +
                       (typed-list 1 2 3)
                       (typed-list 10 20 30 40))
             (typed-list 11 22 33))
(list-equal?
  (list-mappend typed-list (typed-list 10 20 30) (typed-list 1 2 3 4 5))
  (typed-list 10 1 20 2 30 3))
(list-equal?
  (list-fold-right list-cons (list-null) (typed-list 0 1 2 3 4))
  (typed-list 0 1 2 3 4))
(list-equal?
  (list-fold-right list-cons (typed-list 0 1 2) (typed-list 3 4))
  (typed-list 3 4 0 1 2))
(= (list-fold-right * 1 (typed-list 1 2 3 4 5)) 120)
(= (list-fold-left * 1 (typed-list 1 2 3 4 5)) 120)
(= (list-fold-left + 0 (typed-list 1 2 3) (typed-list 10 20 30)) 66)
(equal? (list-fold-left cons '(100) (typed-list 1 2 3 4))
        '(((((100) . 1) . 2) . 3) . 4))
(equal?
  (call-with-values
    (lambda () (list-reverse (typed-list 1 2 3) (typed-list 10 20 30)))
    list)
  (list (typed-list 3 2 1) (typed-list 30 20 10)))
(list-equal? (list-remove 0 (typed-list 1 0 2 0 3 0 4))
             (typed-list 1 2 3 4))
(list-equal? (list-merge < (typed-list 2 4 5 7 8) (typed-list 1 3 6 9 10))
             (typed-list 1 2 3 4 5 6 7 8 9 10))
(not (condition-case (list-merge < (list-null) (typed-list 1 3 2))
       ((exn) #f)))
(list-equal? (list-sort <= (typed-list 2 0 1 4 3))
             (typed-list 0 1 2 3 4))
(not (list-sorted? <= (typed-list 2 0 1 4 3)))
(list-sorted? <= (typed-list 0 1 2 3 4))
(list-every? odd? (typed-list 1 3 5))
(list-every? odd? (typed-list))
(= (list-some odd? (typed-list 2 3 5)) 3)
(not (list-some odd? (typed-list 2 4 6)))
(list-not-every? odd? (typed-list 1 2 3))
(list-not-any? odd? (typed-list 2 4 6))

;;; number-sets
;;; -----------
(set=
  (typed-list->set (typed-list 1 2 1 3 2 3))
  (set 3 2 1))
(set? (set 1 2 3))
(set? (set 1 2 2 3))
(set= (set 2 1 3) (set 1 2 2 3))
(set-in? 2 (set 1 1 2 3))
(set<= (set 2 1 2) (set 4 1 2 3 4))
(set=
  (set-add 0 (set 1 2 3))
  (set 0 1 2 3))
(set=
  (set-add 2 (set 1 2 3))
  (set 1 2 3))
(= (set-cardinality (set 2 1 2 3 2)) 3)
(set=
  (set-remove 2 (set 2 1 2 3 2))
  (set 1 3))
(set=
  (set 0 1 1 0 2 3 2)
  (set 2 3 0 1))
(set=
  (set-difference (set 0 2 1 3) (set 1 1))
  (set 0 2 3))
(set=
  (set-union (set 1 2) (set 2 3) (set 3 4))
  (set 1 2 3 4))
(set=
  (set-intersection (set 1 2 3 4) (set 2 3 5) (set 3 4))
  (set 3))
(set= (set-filter odd? (set 2 1 3 3 1 1)) (set 3 1))

;;; symbol-lists
;;; ------------
;; argument module
(module symbols (equ? type?)
  (import scheme)
  (define equ? eq?)
  (define type? symbol?))

;; apply functor
(module symbol-lists = (typed-lists symbols))

;; imports
(import (prefix symbol-lists sym-))

;; tests
(sym-list-equal?
  (sym-list-append (sym-typed-list 'a 'b)
               (sym-typed-list 'c))
  (sym-typed-list 'a 'b 'c))
(equal?
  (sym-list-bind (x y z) (sym-typed-list 'a 'b 'c) (list x y z))
  '(a b c))
(sym-list-equal?
    (sym-list-bind (x . y) (sym-typed-list 'a 'b 'c) y)
  (sym-typed-list 'b 'c))
(sym-list-null? (sym-list-bind x (sym-list-null) x))
(sym-list-bind () (sym-list-null) #t)

Requirements

datatype

Last update

Aug 17, 2014

Author

Juergen Lorenz

License

Copyright (c) 2014, Juergen Lorenz
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.
Neither the name of the author nor the names of its contributors may be
used to endorse or promote products derived from this software without
specific prior written permission. 
  
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Version History

1.0

functor implementation

0.1

initial import