typed-lists | chickadee

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.

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-nullprocedure: the fundamental datatype-constructor of an empty typed list.

ilist-cons

ilist-cons item ilstprocedure: 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 #!optional symprocedure: documentation procedure.

ilist?

ilist? xprprocedure: type predicate.

ilist

ilist #!rest argsprocedure: constructor. All args must pass item?.

ilist->ilist

ilist->ilist lstprocedure: another constructor.

ilist-repeat

ilist-repeat n xprocedure: constructs a typed list of length n with items all x of item?.

ilist-iterate

ilist-iterate n fn xprocedure: 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 xprocedure: 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 xprocedure: 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 lstprocedure: strips type information and immutability. The returned list is a normal Scheme list.

ilist-apply

ilist-apply fn #!rest argsprocedure: like apply, but the last argument must be a typed list.

ilist-null?

ilist-null? xprprocedure: is xpr an empty typed list?

ilist-first

ilist-first ilstprocedure: like car but with arguments in reversed order.

ilist-rest

ilist-rest ilstprocedure: like cdr but with arguments in reversed order.

ilist-reverse

ilist-reverse #!rest ilstsprocedure: like reverse, but can reverse typed lists of equal length simultaneously.

ilist-length

ilist-length ilstprocedure: like length.

ilist-from-upto

ilist-from-upto from upto ilstprocedure: like sublist.

ilist-item

ilist-item k ilstprocedure: like list-ref, but with reversed argument order.

ilist-split-at

ilist-split-at k ilstprocedure: splits a typed list at index k returning two sublist values, the head and the tail.

ilist-split-with

ilist-split-with ok? ilstprocedure: splits a typed list at the first item passing the ok? predicate. Returns two sublists.

ilist-drop

ilist-drop k ilstprocedure: like list-tail, but with revrsed argument order.

ilist-drop-while

ilist-drop-while ok? ilstprocedure: drops the first items as long as they pass the ok? predicate.

ilist-take

ilist-take k ilstprocedure: returns the head of the typed list upto (but excluding) the index k.

ilist-take-while

ilist-take-while ok? ilstprocedure: returns the longest sublist of a typed list where all items pass ok? starting from index 0.

ilist-append

ilist-append #!rest ilstsprocedure: like append.

ilist-map

ilist-map fn #!rest ilstsprocedure: like map.

ilist-mappend

ilist-mappend fn #!rest ilstsprocedure: combination of map and append.

ilist-for-each

ilist-for-each fn #!rest ilstsprocedure: like for-each.

ilist-filter

ilist-filter ok? ilstprocedure: 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 ilstprocedure: adds an item to a typed list only if it is not allready a member.

ilist-equal?

ilist-equal? ilst0 ilst1procedure: 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? ilstprocedure: returns the sublist of a typed list, starting with the first item passing ok?.

ilist-member

ilist-member item ilstprocedure: like member, items are compared with equ?.

ilist-remp

ilist-remp ok? ilstprocedure: removes all items from a typed list, which pass the ok? test.

ilist-remove

ilist-remove item ilstprocedure: removes all items from a typed list which are equ? to item.

ilist-remove-dups

ilist-remove-dups ilstprocedure: removes all duplicates, compared with equ?.

ilist-assp

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

ilist-assoc

ilist-assoc item ilstprocedure: 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 #!rest ilstsprocedure: like fold-left in R7RS.

ilist-fold-right

ilist-fold-right op base #!rest ilstsprocedure: like fold-right in R7RS.

ilist-merge

ilist-merge <? ilst0 ilst1procedure: merges two <?-sorted typed lists.

ilist-insert-sorted

ilist-insert-sorted <? item ilstprocedure: inserts an item into a sorted typed list without disturbing order.

ilist-insertion-sort

ilist-insertion-sort <? ilstprocedure: insertion sorts a typed list according to <?.

ilist-merge-sort

ilist-merge-sort <? ilstprocedure: merge sorts a typed list according to <?.

ilist-sorted?

ilist-sorted? <? ilstprocedure: is a typed list sorted with respect ot <?.

ilist-zip

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

ilist-unzip

ilist-zip ilstprocedure: splits a typed list into two, populating the result values alternating with items from ilst.

ilist-interpose

ilist-interpose sep ilstprocedure: interposes a separator sep of type type between the list's items.

ilist-every?

ilist-every? ok? ilstprocedure: passes every item the ok? test?

ilist-some

ilist-some ok? ilstprocedure: returns the first item passing the ok? test.

ilist-not-every?

ilist-not-every? ok? ilstprocedure: checks if not every item of ilst passes the ok? test.

ilist-not-any?

ilist-not-any? ok? ilstprocedure: checks if not any item of ilst passes the ok? test.

ilist-in?

ilist-in? ilst0 ilst1procedure: 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 lstprocedure: fundamental datatype constructor. Typed sets are implemented as equivalence classes of typed lists.

set?

set? xprprocedure: evaluates an expression to a typed set?

set

set #!rest argsprocedure: set constructor. All args must pass the item? test.

set->ilist

set->ilist stprocedure: forget set equality, set=, and return to list equality, list-equal?.

set-in?

set-in? item stprocedure: is item of type item? a member of the set st?

set<=

set<= set0 set1procedure: subset relation.

set>=

set>= set0 set1procedure: subset relation.

set=

set= set0 set1procedure: set equality.

set-filter

set-filter ok? stprocedure: filters a set, returning two subsets.

set-null?

set-null? xprprocedure: is the set empty?

set-add

set-add item stprocedure: adds an item to the set.

set-remove

set-remove item stprocedure: 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 stprocedure: returns the number of (different!) items in a set.

set-difference

set-difference set0 set1procedure: removes all items of set1 from set0.

set-union

set-union #!rest stsprocedure: returns the set of all items of all argument sets.

set-intersection

set-intersection #!rest stsprocedure: 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}

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

chickadee » typed-lists

Identifier search

TOC »

Contents »