chickadee » typed-lists

Rationale

Scheme lists are mutable and untyped. The list types produced with the functors of this library are immutable and -- in the general case -- 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 Chicken programmers.

Recall, that functors are to Chicken modules what functions are to Scheme 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 library implements a functor, list-functor, depending on a module parameter which must supply two exports, named equ? and item?, checking the list item's type and equality of its items. The resulting code -- when applied to a concrete module which implements these two routines -- defines immutable typed lists.

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.

As an application of the list-functor, this library defines another functor, set-functor, which depends on a second module, being generated by the list-functor, which generates immutable typed sets, being implemented as equivalence classes of immutable typed lists.

Two untyped modules, immutable-lists and sets, are also supplied as instantiation of the two functors. They are untyped because the item predicate is simply (lambda (x) #t), i.e. everything passes this test.

But note, that for compiling these modules we needed to supply two patches, since the functor implementation is still buggy: In the Chicken generated import modules the abstract module parameters must be replaced by the concrete module arguments. Fortunately, this bug is fixed as of chicken-4.10.

list-functor

the first functor's name, generating immutable typed lists when applied to a module which provides the proper item? and equ? symbols.

Usage

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

;; define argument module
(module vals (item? equ?)
  (import scheme)
  (define item? ...)
  (define equ? ...))

;; apply functor
(module val-lists = (list-functor vals))

;; import the functor
(import (prefix val-lists val-))

;; now use the generated routines

Functions generated by list-functor

In this version of the library, we've changed all exported symbol names. The first reason is consistency, the second -- more important -- is that some of the old names contained the symbol typed, which didn't fit well to the untyped example module immutable-lists. Now, all symbols start with the ilist- prefix, in particular the analoga to most of the classical list procedures.

Note the order of arguments: the lists generated by this functor are consistently the last ones.

ilist-null

(ilist-null) procedure

the fundamental datatype-constructor of an empty typed list.

ilist-cons

(ilist-cons item ilst) procedure

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

ilists

(ilists [sym]) procedure

documentation procedure.

ilist?

(ilist? xpr) procedure

type predicate.

ilist

(ilist . args) procedure

constructor. All args must pass item?.

ilist->ilist

(ilist->ilist lst) procedure

another constructor.

ilist-repeat

(ilist-repeat n x) procedure

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

ilist-iterate

(ilist-iterate n fn x) procedure

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

ilist-iterate-while

(ilist-iterate-while ok? fn x) procedure

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

ilist-iterate-until

(ilist-iterate-until ok? fn x) procedure

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

ilist->list

(ilist->list lst) procedure

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

ilist-apply

(ilist-apply fn . args) procedure

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

ilist-null?

(ilist-null? xpr) procedure

is xpr an empty typed list?

ilist-first

(ilist-first ilst) procedure

like car but with arguments in reversed order.

ilist-rest

(ilist-rest ilst) procedure

like cdr but with arguments in reversed order.

ilist-reverse

(ilist-reverse . ilsts) procedure

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

ilist-length

(ilist-length ilst) procedure

like length.

ilist-from-upto

(ilist-from-upto from upto ilst) procedure

like sublist.

ilist-item

(ilist-item k ilst) procedure

like list-ref, but with reversed argument order.

ilist-split-at

(ilist-split-at k ilst) procedure

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

ilist-split-with

(ilist-split-with ok? ilst) procedure

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

ilist-drop

(ilist-drop k ilst) procedure

like list-tail, but with revrsed argument order.

ilist-drop-while

(ilist-drop-while ok? ilst) procedure

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

ilist-take

(ilist-take k ilst) procedure

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

ilist-take-while

(ilist-take-while ok? ilst) procedure

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

ilist-append

(ilist-append . ilsts) procedure

like append.

ilist-map

(ilist-map fn . ilsts) procedure

like map.

ilist-mappend

(ilist-mappend fn . ilsts) procedure

combination of map and append.

ilist-for-each

(ilist-for-each fn . ilsts) procedure

like for-each.

ilist-filter

(ilist-filter ok? ilst) procedure

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

ilist-adjoin

(ilist-adjoin item ilst) procedure

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

ilist-equal?

(ilist-equal? ilst0 ilst1) procedure

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

ilist-memp

(ilist-memp ok? ilst) procedure

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

ilist-member

(ilist-member item ilst) procedure

like member, items are compared with equ?.

ilist-remp

(ilist-remp ok? ilst) procedure

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

ilist-remove

(ilist-remove item ilst) procedure

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

ilist-remove-dups

(ilist-remove-dups ilst) procedure

removes all duplicates, compared with equ?.

ilist-assp

(ilist-assp ok? ilst) procedure

returns the first pair of a ilist of pairs, whose car passes the ok? test.

ilist-assoc

(ilist-assoc item ilst) procedure

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

ilist-fold-left

(ilist-fold-left op base . ilsts) procedure

like fold-left in R7RS.

ilist-fold-right

(ilist-fold-right op base . ilsts) procedure

like fold-right in R7RS.

ilist-merge

(ilist-merge <? ilst0 ilst1) procedure

merges two <?-sorted typed lists.

ilist-insert-sorted

(ilist-insert-sorted <? item ilst) procedure

inserts an item into a sorted typed list without disturbing order.

ilist-insertion-sort

(ilist-insertion-sort <? ilst) procedure

insertion sorts a typed list according to <?.

ilist-merge-sort

(ilist-merge-sort <? ilst) procedure

merge sorts a typed list according to <?.

ilist-sorted?

(ilist-sorted? <? ilst) procedure

is a typed list sorted with respect ot <?.

ilist-zip

(ilist-zip ilst0 ilst1) procedure

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

ilist-unzip

(ilist-zip ilst) procedure

splits a typed list into two, populating the result values alternating with items from ilst.

ilist-interpose

(ilist-interpose sep ilst) procedure

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

ilist-every?

(ilist-every? ok? ilst) procedure

passes every item the ok? test?

ilist-some

(ilist-some ok? ilst) procedure

returns the first item passing the ok? test.

ilist-not-every?

(ilist-not-every? ok? ilst) procedure

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

ilist-not-any?

(ilist-not-any? ok? ilst) procedure

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

ilist-in?

(ilist-in? ilst0 ilst1) procedure

checks, if the typed list ilst0 is a contiguous sublist of the ilist ilst1.

ilist-bind

(ilist-bind (x ... . xs) ilst xpr . xprs) syntax

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! ilist?
                      ilist-length
                      (lambda (ilst item) (ilist-item item ilst))
                      (lambda (ilst item) (ilist-drop item ilst)))

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

Examples of using list-functor

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

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

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

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

;; tests
(sym-ilist-append (sym-ilist 'a 'b) (sym-ilist 'c))
  ; -> ['a 'b 'c]
(sym-ilist-bind (x y z) (sym-ilist 'a 'b 'c) (list x y z))
  ; -> '(a b c)
(sym-ilist-bind (x . y) (sym-ilist 'a 'b 'c) y)
  ; -> ['b 'c]
(sym-ilist-bind x (sym-ilist-null) x) ; -> []
(sym-ilist-bind () (sym-ilist-null) #t) ; -> #t

;;; pair-lists
;;; ----------
;; argument module
(module pairs (item? equ?)
  (import scheme)
  (define (item? x)
    (and (pair? x) (number? (car x)) (string? (cdr x))))
  (define equ? equal?))

;; apply functor
(module pair-lists = (list-functor pairs))

;; tests
(import (prefix pair-lists nsp-))
(define nspl (nsp-ilist (cons 1 "one") (cons 2 "two") (cons 3 "three")))
(nsp-ilist-assoc 2 nspl) ; -> '(2 . "two")
(nsp-ilist-assp zero? nspl) ; -> #f

set-functor

the second functor's name, generating immutable typed sets when applied to two modules, the first one providing the proper item? and equ? symbols, the second being generated by invoking list-functor with the first module.

Usage of set-functor

(require-library typed-lists datatype)
(import list-functor set-functor datatype)

;; define first argument module
(module vals (item? equ?)
  (import scheme)
  (define item? ...)
  (define equ? ...))

;; apply list-functor to provide second argument module
(module val-lists = (list-functor vals))

;; apply set-functor
(module val-sets = (set-functor vals val-lists))

;; import the modules
(import val-lists val-sets)

;; now use the generated routines

Procedures generated by set-functor

list-sets

(list-sets [sym] procedure

documentation procedure.

ilist->set

(ilist->set lst) procedure

fundamental datatype constructor. Typed sets are implemented as equivalence classes of typed lists.

set?

(set? xpr) procedure

evaluates an expression to a typed set?

set

(set . args) procedure

set constructor. All args must pass the item? test.

set->ilist

(set->ilist st) procedure

forget set equality, set=, and return to list equality, list-equal?.

set-in?

(set-in? item st) procedure

is item of type item? a member of the set st?

set<=

(set<= set0 set1) procedure

subset relation.

set>=

(set>= set0 set1) procedure

subset relation.

set=

(set= set0 set1) procedure

set equality.

set-filter

(set-filter ok? st) procedure

filters a set, returning two subsets.

set-null?

(set-null? xpr) procedure

is the set empty?

set-add

(set-add item st) procedure

adds an item to the set.

set-remove

(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

(set-cardinality st) procedure

returns the number of (different!) items in a set.

set-difference

(set-difference set0 set1) procedure

removes all items of set1 from set0.

set-union

(set-union . sts) procedure

returns the set of all items of all argument sets.

set-intersection

(set-intersection . sts) procedure

returns the set of items which are in all argument sets.

immutable-lists

the module generated by list-functor with non-checking item? predicate and equal? comparison operator. This is the most used case.

Examples of using module immutable-lists

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

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

list-sets

the module generated by the set-functor with non-checking item? predicate and equal? comparison operator. This is the most used case.

Examples of using module list-sets

(require-library typed-lists)
(import list-sets)

(ilist->set (ilist 1 2 1 3 2 3)) ; -> {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)) ; -> #t
(set<= (set 2 1 2) (set 4 1 2 3 4)) ; -> #t
(set-add 0 (set 1 2 3)) ; -> {0 1 2 3}
(set-add 2 (set 1 2 3)) ; -> {1 2 3}
(set-cardinality (set 2 1 2 3 2) ; -> 3
(set-remove 2 (set 2 1 2 3 2)) ; -> {1 3}
(set= (set 0 1 1 0 2 3 2) (set 2 3 0 1)) ; -> #t
(set-difference (set 0 2 1 3) (set 1 1)) ; -> {0 2 3}
(set-union (set 1 2) (set 2 3) (set 3 4)) ; -> {1 2 3 4}
(set-intersection (set 1 2 3 4) (set 2 3 5) (set 3 4)) ; -> {3}
(set= (set-filter odd? (set 2 1 3 3 1 1)) ; -> {3 1}

Requirements

datatype

Last update

Dec 12, 2015

Author

Juergen Lorenz

License

Copyright (c) 2014-2015, 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

2.3
sets module renamed to list-sets
2.1
ilist-unzip added, ilist-appyl and ilist-mappend simplified
2.0
modules immutable-lists and sets introduced, exported symbols renamed
1.3
functor split in two
1.2
list-cons-sorted added
1.1
list-bind corrected, list-in? added
1.0
functor implementation
0.1
initial import

Contents »