## TOC »

- Rationale
- list-functor
- Functions generated by list-functor
- ilist-null
- ilist-cons
- ilists
- ilist?
- ilist
- ilist->ilist
- ilist-repeat
- ilist-iterate
- ilist-iterate-while
- ilist-iterate-until
- ilist->list
- ilist-apply
- ilist-null?
- ilist-first
- ilist-rest
- ilist-reverse
- ilist-length
- ilist-from-upto
- ilist-item
- ilist-split-at
- ilist-split-with
- ilist-drop
- ilist-drop-while
- ilist-take
- ilist-take-while
- ilist-append
- ilist-map
- ilist-mappend
- ilist-for-each
- ilist-filter
- ilist-adjoin
- ilist-equal?
- ilist-memp
- ilist-member
- ilist-remp
- ilist-remove
- ilist-remove-dups
- ilist-assp
- ilist-assoc
- ilist-fold-left
- ilist-fold-right
- ilist-merge
- ilist-insert-sorted
- ilist-insertion-sort
- ilist-merge-sort
- ilist-sorted?
- ilist-zip
- ilist-unzip
- ilist-interpose
- ilist-every?
- ilist-some
- ilist-not-every?
- ilist-not-any?
- ilist-in?
- ilist-bind
- Examples of using list-functor

- set-functor
- Usage of set-functor
- Procedures generated by set-functor
- immutable-lists
- list-sets
- Requirements

- 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

`(ilist-null)`procedurethe fundamental datatype-constructor of an empty typed list.

#### ilist-cons

`(ilist-cons item ilst)`procedurethe 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])`proceduredocumentation procedure.

#### ilist?

`(ilist? xpr)`proceduretype predicate.

#### ilist

`(ilist . args)`procedureconstructor. All args must pass item?.

#### ilist->ilist

`(ilist->ilist lst)`procedureanother constructor.

#### ilist-repeat

`(ilist-repeat n x)`procedureconstructs a typed list of length n with items all x of item?.

#### ilist-iterate

`(ilist-iterate n fn x)`procedureconstructs 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)`procedureconstructs 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)`procedureconstructs 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)`procedurestrips type information and immutability. The returned list is a normal Scheme list.

#### ilist-apply

`(ilist-apply fn . args)`procedurelike apply, but the last argument must be a typed list.

#### ilist-null?

`(ilist-null? xpr)`procedureis xpr an empty typed list?

#### ilist-first

`(ilist-first ilst)`procedurelike car but with arguments in reversed order.

#### ilist-rest

`(ilist-rest ilst)`procedurelike cdr but with arguments in reversed order.

#### ilist-reverse

`(ilist-reverse . ilsts)`procedurelike reverse, but can reverse typed lists of equal length simultaneously.

#### ilist-length

`(ilist-length ilst)`procedurelike length.

#### ilist-from-upto

`(ilist-from-upto from upto ilst)`procedurelike sublist.

#### ilist-item

`(ilist-item k ilst)`procedurelike list-ref, but with reversed argument order.

#### ilist-split-at

`(ilist-split-at k ilst)`proceduresplits a typed list at index k returning two sublist values, the head and the tail.

#### ilist-split-with

`(ilist-split-with ok? ilst)`proceduresplits a typed list at the first item passing the ok? predicate. Returns two sublists.

#### ilist-drop

`(ilist-drop k ilst)`procedurelike list-tail, but with revrsed argument order.

#### ilist-drop-while

`(ilist-drop-while ok? ilst)`proceduredrops the first items as long as they pass the ok? predicate.

#### ilist-take

`(ilist-take k ilst)`procedurereturns the head of the typed list upto (but excluding) the index k.

#### ilist-take-while

`(ilist-take-while ok? ilst)`procedurereturns the longest sublist of a typed list where all items pass ok? starting from index 0.

#### ilist-append

`(ilist-append . ilsts)`procedurelike append.

#### ilist-map

`(ilist-map fn . ilsts)`procedurelike map.

#### ilist-mappend

`(ilist-mappend fn . ilsts)`procedurecombination of map and append.

#### ilist-for-each

`(ilist-for-each fn . ilsts)`procedurelike for-each.

#### ilist-filter

`(ilist-filter ok? ilst)`procedurereturns 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)`procedureadds an item to a typed list only if it is not allready a member.

#### ilist-equal?

`(ilist-equal? ilst0 ilst1)`procedureAre 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)`procedurereturns the sublist of a typed list, starting with the first item passing ok?.

#### ilist-member

`(ilist-member item ilst)`procedurelike member, items are compared with equ?.

#### ilist-remp

`(ilist-remp ok? ilst)`procedureremoves all items from a typed list, which pass the ok? test.

#### ilist-remove

`(ilist-remove item ilst)`procedureremoves all items from a typed list which are equ? to item.

#### ilist-remove-dups

`(ilist-remove-dups ilst)`procedureremoves all duplicates, compared with equ?.

#### ilist-assp

`(ilist-assp ok? ilst)`procedurereturns the first pair of a ilist of pairs, whose car passes the ok? test.

#### ilist-assoc

`(ilist-assoc item ilst)`procedurelike 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)`procedurelike fold-left in R7RS.

#### ilist-fold-right

`(ilist-fold-right op base . ilsts)`procedurelike fold-right in R7RS.

#### ilist-merge

`(ilist-merge <? ilst0 ilst1)`proceduremerges two <?-sorted typed lists.

#### ilist-insert-sorted

`(ilist-insert-sorted <? item ilst)`procedureinserts an item into a sorted typed list without disturbing order.

#### ilist-insertion-sort

`(ilist-insertion-sort <? ilst)`procedureinsertion sorts a typed list according to <?.

#### ilist-merge-sort

`(ilist-merge-sort <? ilst)`proceduremerge sorts a typed list according to <?.

#### ilist-sorted?

`(ilist-sorted? <? ilst)`procedureis a typed list sorted with respect ot <?.

#### ilist-zip

`(ilist-zip ilst0 ilst1)`procedurecombines two typed lists in zip mode, i.e. alternating between the items of the left and right argument list.

#### ilist-unzip

`(ilist-zip ilst)`proceduresplits a typed list into two, populating the result values alternating with items from ilst.

#### ilist-interpose

`(ilist-interpose sep ilst)`procedureinterposes a separator sep of type type between the list's items.

#### ilist-every?

`(ilist-every? ok? ilst)`procedurepasses every item the ok? test?

#### ilist-some

`(ilist-some ok? ilst)`procedurereturns the first item passing the ok? test.

#### ilist-not-every?

`(ilist-not-every? ok? ilst)`procedurechecks if not every item of ilst passes the ok? test.

#### ilist-not-any?

`(ilist-not-any? ok? ilst)`procedurechecks if not any item of ilst passes the ok? test.

#### ilist-in?

`(ilist-in? ilst0 ilst1)`procedurechecks, if the typed list ilst0 is a contiguous sublist of the ilist ilst1.

#### ilist-bind

`(ilist-bind (x ... . xs) ilst xpr . xprs)`syntaxThis 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]`proceduredocumentation procedure.

#### ilist->set

`(ilist->set lst)`procedurefundamental datatype constructor. Typed sets are implemented as equivalence classes of typed lists.

#### set?

`(set? xpr)`procedureevaluates an expression to a typed set?

#### set

`(set . args)`procedureset constructor. All args must pass the item? test.

#### set->ilist

`(set->ilist st)`procedureforget set equality, set=, and return to list equality, list-equal?.

#### set-in?

`(set-in? item st)`procedureis item of type item? a member of the set st?

#### set<=

`(set<= set0 set1)`proceduresubset relation.

#### set>=

`(set>= set0 set1)`proceduresubset relation.

#### set=

`(set= set0 set1)`procedureset equality.

#### set-filter

`(set-filter ok? st)`procedurefilters a set, returning two subsets.

#### set-null?

`(set-null? xpr)`procedureis the set empty?

#### set-add

`(set-add item st)`procedureadds an item to the set.

#### set-remove

`(set-remove item st)`procedureremoves 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)`procedurereturns the number of (different!) items in a set.

#### set-difference

`(set-difference set0 set1)`procedureremoves all items of set1 from set0.

#### set-union

`(set-union . sts)`procedurereturns the set of all items of all argument sets.

#### set-intersection

`(set-intersection . sts)`procedurereturns 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

## 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