Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

Outdated egg!
Rationale
Last update
Author
License
Version History

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

[procedure] (ilist-null)

the fundamental datatype-constructor of an empty typed list.

ilist-cons

[procedure] (ilist-cons item ilst)

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

[procedure] (ilists [sym])

documentation procedure.

ilist?

[procedure] (ilist? xpr)

type predicate.

ilist

[procedure] (ilist . args)

constructor. All args must pass item?.

ilist->ilist

[procedure] (ilist->ilist lst)

another constructor.

ilist-repeat

[procedure] (ilist-repeat n x)

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

ilist-iterate

[procedure] (ilist-iterate n fn x)

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

ilist-iterate-while

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

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

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

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

[procedure] (ilist->list lst)

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

ilist-apply

[procedure] (ilist-apply fn . args)

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

ilist-null?

[procedure] (ilist-null? xpr)

is xpr an empty typed list?

ilist-first

[procedure] (ilist-first ilst)

like car but with arguments in reversed order.

ilist-rest

[procedure] (ilist-rest ilst)

like cdr but with arguments in reversed order.

ilist-reverse

[procedure] (ilist-reverse . ilsts)

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

ilist-length

[procedure] (ilist-length ilst)

like length.

ilist-from-upto

[procedure] (ilist-from-upto from upto ilst)

like sublist.

ilist-item

[procedure] (ilist-item k ilst)

like list-ref, but with reversed argument order.

ilist-split-at

[procedure] (ilist-split-at k ilst)

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

ilist-split-with

[procedure] (ilist-split-with ok? ilst)

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

ilist-drop

[procedure] (ilist-drop k ilst)

like list-tail, but with revrsed argument order.

ilist-drop-while

[procedure] (ilist-drop-while ok? ilst)

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

ilist-take

[procedure] (ilist-take k ilst)

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

ilist-take-while

[procedure] (ilist-take-while ok? ilst)

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

ilist-append

[procedure] (ilist-append . ilsts)

like append.

ilist-map

[procedure] (ilist-map fn . ilsts)

like map.

ilist-mappend

[procedure] (ilist-mappend fn . ilsts)

combination of map and append.

ilist-for-each

[procedure] (ilist-for-each fn . ilsts)

like for-each.

ilist-filter

[procedure] (ilist-filter ok? ilst)

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

ilist-adjoin

[procedure] (ilist-adjoin item ilst)

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

ilist-equal?

[procedure] (ilist-equal? ilst0 ilst1)

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

ilist-memp

[procedure] (ilist-memp ok? ilst)

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

ilist-member

[procedure] (ilist-member item ilst)

like member, items are compared with equ?.

ilist-remp

[procedure] (ilist-remp ok? ilst)

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

ilist-remove

[procedure] (ilist-remove item ilst)

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

ilist-remove-dups

[procedure] (ilist-remove-dups ilst)

removes all duplicates, compared with equ?.

ilist-assp

[procedure] (ilist-assp ok? ilst)

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

ilist-assoc

[procedure] (ilist-assoc item ilst)

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

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

like fold-left in R7RS.

ilist-fold-right

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

like fold-right in R7RS.

ilist-merge

[procedure] (ilist-merge <? ilst0 ilst1)

merges two <?-sorted typed lists.

ilist-insert-sorted

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

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

ilist-insertion-sort

[procedure] (ilist-insertion-sort <? ilst)

insertion sorts a typed list according to <?.

ilist-merge-sort

[procedure] (ilist-merge-sort <? ilst)

merge sorts a typed list according to <?.

ilist-sorted?

[procedure] (ilist-sorted? <? ilst)

is a typed list sorted with respect ot <?.

ilist-zip

[procedure] (ilist-zip ilst0 ilst1)

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

ilist-unzip

[procedure] (ilist-zip ilst)

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

ilist-interpose

[procedure] (ilist-interpose sep ilst)

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

ilist-every?

[procedure] (ilist-every? ok? ilst)

passes every item the ok? test?

ilist-some

[procedure] (ilist-some ok? ilst)

returns the first item passing the ok? test.

ilist-not-every?

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

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

ilist-not-any?

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

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

ilist-in?

[procedure] (ilist-in? ilst0 ilst1)

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

ilist-bind

[syntax] (ilist-bind (x ... . xs) ilst 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! 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


(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}

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