Rationale

This module exports routines to handle pseudolists as a generalisation of ordinary lists. They can be considered as parametrized (or tagged) lists, where the parameter (or tag) is stored in the sentinel of a dotted list. In such a naive approch, we are faced with two problems.

First, since dotted lists differ from lists only insofor, as their sentinels might be arbitrary atoms instead of the empty list. In other words, a dotted list is either a pair or an atom. But since an atom is simply not a pair, everything is a pseudolist, in particular, a list is one. Hence, there is no meaningfull predicate for dotted lists.

Second, there is an efficency problem: to get a handle to the sentinel, we have to traverse the whole dotted list. This is not acceptable, if, for example, the parameter is a type predicate to check the type of items to be put into the dotted list. Ok, as in previous versions of this module, we can put the sentinel into a parameter, but this alone doesn't help much, if different parameters are used simultaneously.

This module offers a simple solution to both problems: Make the dotted list callable, in other words, put it into a closure and acces the items as well as the sentinel -- and the length for that matter -- via calls to that closure, e.g. (pls i), where i is an index.

Note, that most procedures are implemented in a curried and uncurried form, but only the latter is described in detail in the documentation. The former can be used in map and friends.

Note also, that the order or arguments of all procedures is consistent: The pseudolist argument(s) are always last, other procedures first.

API

pl-parameter

[parameter] (pl-parameter)
[parameter] (pl-parameter new)

returns or resets the sentinel of a pseudolist, initially '()

pl-checker

[procedure] (pl-checker ok? arg)
[procedure] (pl-checker ok?)

type constructor: wrap the predicate ok? into a unary procedure, which returns its argument unchanged, if only it passes the ok? test. An uncurried version is given as well

pl-checker?

[procedure] (pl-checker? xpr)

type predicate. Used to check if the tag can be used to check all items.

pl

[procedure] (pl . args)

constructor: creates a pseudolist with sentinel tag from pl-parameter and items from args, encapsulated into a closure, which, when called with an index, returns the argument at that index, or, when called with -1, returns the length of args.

pl?

[procedure] (pl? xpr)

type predicate

pl-maker

[procedure] (pl-maker len fill)
[procedure] (pl-maker len)

creates a pseudolist of length len with sentinel (pl-parameter), items fill or (pl-sentinel), if fill is not given

pl-at

[procedure] (pl-at k pls)
[procedure] (pl-at k)

returns the kth item of pls

pl-set!

[procedure] (pl-set! k val pls)

sets the kth item of pls to val

pl-length

[procedure] (pl-length pls)

returns the length of the pseudolist pls

pl-null?

[procedure] (pl-null? xpr)

checks, if no items are stored in the pseudolist xpr

pl-head

[procedure] (pl-head pls)

returns the list part of the pseudolist pls

pl-tail

[procedure] (pl-tail pls)

returns the sentinel of the pseudolist pls

pl-data

[procedure] (pl-data pls)

returns the dotted list underlying the pseudolist pls

pl-cons

[procedure] (pl-cons x pls)
[procedure] (pl-cons x)

adds the item x to the front of the pseudolist pls

pl-car

[procedure] (pl-car pls)

returns the first item of the pseudolist pls

pl-cdr

[procedure] (pl-cdr pls)

returns a new pseudolist removing the first item of pls

pl-of?

[procedure] (pl-of? tag . preds)

creates a unary predicate, which tests, if its argument is a pseudolist with parameter tag, whose items pass all the predicates preds

pl-iterate

[procedure] (pl-iterate fn times init)
[procedure] (pl-iterate fn times)

creates a pseudolist with sentinel (pl-parameter) applying fn to init recursively k times

pl-drop

[procedure] (pl-drop n pls)
[procedure] (pl-drop n)

returns a new pseudolist removing the first n items of the pseudolist pls

pl-drop-while

[procedure] (pl-drop-while ok? pls)
[procedure] (pl-drop-while ok?)

returns the tail of pls starting with the first item that does not pass the ok? test

pl-take

[procedure] (pl-take n pls)
[procedure] (pl-take n)

returns a new pseudolist consisting of the first n items of the pseudolist pls, keeping the sentinel

pl-take-while

[procedure] (pl-take-while ok? pls)
[procedure] (pl-take-while ok?)

returns the sublist of pls consisting of items until the first item doesn't pass the ok? test.

pl-reverse

[procedure] (pl-reverse pl)

reverses its pseudolist argument to a new pseudolist with same sentinel

pl-map

[procedure] (pl-map fn . plss)

maps fn over the pseudolists plss as long as none of the items is pl-null? and returns a new pseudolist if all sentinels are equal. Note, that this is R7RS-, not R5RS-logic.

pl-for-each

[procedure] (pl-for-each fn pls . plss)

applies fn over the pseudolists (cons pls plss) stops if one of the items is pl-null? Note, that this is R7RS-, not R5RS-logic

pl-memp

[procedure] (pl-memp ok? pls)
[procedure] (pl-memp ok?)

returns the subpseudolist starting at the first item which passes the ok? test, keeping ps's sentinel. Returns #f if no item passes the ok? test

pl-memq

[procedure] (pl-memq x pls)
[procedure] (pl-memq x)

same as (pl-memp (cut eq? <> x) pls)

pl-memv

[procedure] (pl-memv x pls)
[procedure] (pl-memv x)

same as (pl-memp (cut eqv? <> x) pls)

pl-member

[procedure] (pl-member x pls)
[procedure] (pl-member x)

same as (pl-memp (cut equal? <> x) pls)

pl-index

[procedure] (pl-index ok? pls)
[procedure] (pl-index ok?)

returns the index of the first item passing the ok? test, -1 otherwise

pl-filter

[procedure] (pl-filter ok? pls)
[procedure] (pl-filter ok?)

filters a pseudolist by means of a predicate ok? returning two new pseudolists, those of items of pls passing the ok? test, and those that don't

pl-append

[procedure] (pl-append pls . plss)

appends all argument pseudolist, provided their tags are all equal

pl-fold-right

[procedure] (pl-fold-right op init pls)
[procedure] (pl-fold-right op init)

folds pls from the right with binary operation op and starting value init

pl-fold-right0

[procedure] (pl-fold-right0 op pls)
[procedure] (pl-fold-right0 op)

folds (pl-cdr pls) from the right with binary operation op and starting value (pl-car pls)

pl-fold-left

[procedure] (pl-fold-left op init pls)
[procedure] (pl-fold-left op init)

folds pls from the left with binary operation op and starting value init

pl-fold-left0

[procedure] (pl-fold-left0 op pls)
[procedure] (pl-fold-left0 op)

folds (pl-cdr pls) from the left with binary operation op and starting value (pl-car pls)

pl-adjoin

[procedure] (pl-adjoin obj pls)
[procedure] (pl-adjoin obj)

add obj to the front of pls only if it is not already a member of pls

pl-remove-dups

[procedure] (pl-remove-dups pls)

removes the duplicates in the pseudolist pls

pl-flat?

[procedure] (pl-flat? xpr)

is xpr a flat pseudolist, i.e. not containing other pseudolists

pl-flatten

[procedure] (pl-flatten pl-tree)

flattens the nested pseudolist pl-tree to a pseudolist, i.e. splices the pseudolist items of pl-tree into pl-tree provided all parameters are equal

pl-collect

[syntax] (pl-collect item-xpr (var pls ok-xpr ...))
[syntax] (pl-collect item-xpr (var pls ok-xpr ...) (var1 pls1 ok-xpr1 ...) ...)

creates a new pseudolist by binding var to each element of the pseudolist pls in sequence, and if it passes the checks, ok-xpr ..., inserts the value of xpr into the resulting pseudolist. The qualifieres, (var pls ok-xpr ...), are processed sequentially from left to right, so that filters of a qualifier have access to the variables of qualifiers to its left.

pseudolists

[procedure] (pseudolists)
[procedure] (pseudolists sym)

with sym: documentation of exported symbol without sym: list of exported symbols

Examples


(import pseudolists)

'(basic?
   parameter
   (pl-parameter 0)
   pls
   (pl 0 1 2 3)
   mls
   (pl-maker 5)
   ils
   (pl-iterate add1 5 1))

(pl-parameter)
;-> 0

(pl-data pls)
;-> (quote (0 1 2 3 . 0))

(pl-data mls)
;-> (quote (0 0 0 0 0 . 0))

(pl-data ils)
;-> (quote (1 2 3 4 5 . 0))

(pl? pls)
;-> #t

(pl? mls)
;-> #t

(pl? ils)
;-> #t

(pl? '(0 1 2 3))
;-> #f

((pl-of? 0) pls)
;-> #t

((pl-of? '()) mls)
;-> #f

(pl-car mls)
;-> 0

(pl-at 3 mls)
;-> 0

(pl-at 3 pls)
;-> 3

(pls 3)
;-> 3

(pl-head pls)
;-> (quote (0 1 2 3))

(pls)
;-> (quote (0 1 2 3))

(pl-tail pls)
;-> 0

(pl-data pls)
;-> (quote (0 1 2 3 . 0))

(pl-data mls)
;-> (quote (0 0 0 0 0 . 0))

(pl-tail mls)
;-> 0

(pl-data ils)
;-> (quote (1 2 3 4 5 . 0))

(ils)
;-> (quote (1 2 3 4 5))

(pl-tail ils)
;-> 0

(pl-head (pl-cons -1 pls))
;-> (quote (-1 0 1 2 3))

(pl-head (pl-cdr pls))
;-> (quote (1 2 3))

(pl-set! 0 1 mls)
;-> (void)

(pl-at 0 mls)
;-> 1

(pl-set! 1 2 mls)
;-> (void)

(pl-at 1 mls)
;-> 2

(mls 1)
;-> 2

(mls 2 3)
;-> (void)

(mls 2)
;-> 3

(mls)
;-> (quote (1 2 3 0 0))

(pl-head mls)
;-> (quote (1 2 3 0 0))

(newline)

'(checked? parameter (pl-parameter (pl-checker integer?)) pls (pl 0 1 2 3))

(pl-tail pls)
;-> (pl-parameter)

(pl-head pls)
;-> (quote (0 1 2 3))

(condition-case (pl 0 1 #f 3) ((exn) #f))
;-> #f

(condition-case (pl-set! 0 #f pls) ((exn) #f))
;-> #f

(pl-set! 0 100 pls)
;-> (void)

(pl-car pls)
;-> 100

(pls 0 10)
;-> (void)

(pls 0)
;-> 10

(newline)

'(ops? parameter
       (pl-parameter 0)
       pls
       (pl 0 1 2 3)
       mls
       (pl-maker 5)
       ils
       (pl-iterate add1 5 1)
       ii
       (pl-iterate add1 5))

(pl-parameter)
;-> 0

(pl-data pls)
;-> (quote (0 1 2 3 . 0))

(pl-data mls)
;-> (quote (0 0 0 0 0 . 0))

(pl-data ils)
;-> (quote (1 2 3 4 5 . 0))

(pl-data (ii 1))
;-> (quote (1 2 3 4 5 . 0))

(pls)
;-> (quote (0 1 2 3))

(pl? pls)
;-> #t

((pl-of? 1) pls)
;-> #f

((pl-of? 0) pls)
;-> #t

((pl-of? 0 integer?) pls)
;-> #t

((pl-of? 0 integer? positive?) pls)
;-> #f

(pl? '(0 1 2 3 . 0))
;-> #f

(pl-at 0 pls)
;-> 0

(pl-at 3 pls)
;-> 3

(pl-head (pl-map add1 pls))
;-> (quote (1 2 3 4))

(pl-head (pl-map + pls pls))
;-> (quote (0 2 4 6))

(pl-index negative? pls)
;-> -1

(pl-index odd? pls)
;-> 1

(pl-head (pl-filter odd? pls))
;-> (quote (1 3))

(receive (_ pl-no) (pl-filter odd? pls) (pl-head pl-no))
;-> (quote (0 2))

(pl-head (pl-append pls ils))
;-> (quote (0 1 2 3 1 2 3 4 5))

(pl-head (pl-append pls ils mls))
;-> (quote (0 1 2 3 1 2 3 4 5 0 0 0 0 0))

(pl-set! 2 20 pls)
;-> (void)

(pl-head pls)
;-> (quote (0 1 20 3))

(pl-length pls)
;-> 4

(pl-tail pls)
;-> 0

(pl-at 2 pls)
;-> 20

(pl-head pls)
;-> (quote (0 1 20 3))

(pl-head (pl-drop 3 pls))
;-> (quote (3))

(pl-head (pl-drop-while zero? pls))
;-> (quote (1 20 3))

(pl-head (pl-drop-while (cut <= <> 10) pls))
;-> (quote (20 3))

(pl-head (pl-take 3 pls))
;-> (quote (0 1 20))

(pl-head (pl-take-while (cut <= <> 10) pls))
;-> (quote (0 1))

(pl-head (pl-reverse pls))
;-> (quote (3 20 1 0))

(pl-head (pl-memp (lambda (x) (> x 10)) pls))
;-> (quote (20 3))

(pl-head mls)
;-> (quote (0 0 0 0 0))

((pl-of? 0 zero?) mls)
;-> #t

(pl-length mls)
;-> 5

(pl-set! 2 20 mls)
;-> (void)

(pl-head mls)
;-> (quote (0 0 20 0 0))

(pl-tail mls)
;-> 0

(pl? mls)
;-> #t

(pl-head (pl-maker 5 1))
;-> (quote (1 1 1 1 1))

(pl? ils)
;-> #t

(pl-head ils)
;-> (quote (1 2 3 4 5))

(pl-tail ils)
;-> 0

(pl-at 2 ils)
;-> 3

(pl? ii)
;-> #f

(pl? (ii 1))
;-> #t

(pl-length (ii 1))
;-> 5

(pl-at 3 (ii 1))
;-> 4

(pl-head (pl-map * (pl 0 1 2 3) (pl 10 20)))
;-> (quote (0 20))

(condition-case
  (pl-map
    +
    (parameterize ((pl-parameter #f)) (pl 0 1 2 3))
    (parameterize ((pl-parameter #t)) (pl 0 1 2 3)))
  ((exn) #f))
;-> #f

(newline)

'(new-ops? parameter (pl-parameter 0) pls (pl 0 1 2 3 4 5))

(pl-data pls)
;-> (quote (0 1 2 3 4 5 . 0))

(pl-fold-right + 0 pls)
;-> 15

(pl-fold-left + 0 pls)
;-> 15

(pl-fold-right0 + pls)
;-> 15

(pl-fold-left0 + pls)
;-> 15

(pl-head (pl-fold-right pl-cons (pl) pls))
;-> (quote (0 1 2 3 4 5))

(pl-fold-right cons '() pls)
;-> (quote (0 1 2 3 4 5))

(pl-head (pl-adjoin 3 pls))
;-> (quote (0 1 2 3 4 5))

(pl-head (pl-adjoin #f pls))
;-> (quote (#f 0 1 2 3 4 5))

(pl-head (pl-remove-dups pls))
;-> (quote (0 1 2 3 4 5))

(pl-head (pl-remove-dups (pl 0 1 0 1 0 1)))
;-> (quote (0 1))

(pl-flat? pls)
;-> #t

(pl-flat? (pl 0 (pl 1 (pl 2))))
;-> #f

(pl-head (pl-flatten (pl 1 2 3)))
;-> (quote (1 2 3))

(pl-head (pl-flatten (pl 1 '(2 3))))
;-> (quote (1 (2 3)))

(pl-head (pl-flatten (pl 1 (pl 2 3))))
;-> (quote (1 2 3))

(pl-head (pl-flatten (pl 1 (pl 2 3) (pl 4 5) 6)))
;-> (quote (1 2 3 4 5 6))

(pl-head (pl-flatten (pl 1 (pl 2 (pl 3)))))
;-> (quote (1 2 3))

(pl-head (pl-flatten (pl 1 (pl 2 (pl 3 (pl 4)) 5) 6)))
;-> (quote (1 2 3 4 5 6))

(condition-case
  (pl-flatten (pl 1 (parameterize ((pl-parameter #f)) (pl 2 3))))
  ((exn) #f))
;-> #f

(newline)

(pl-data (pl-collect (add1 x) (x (pl 0 1 2 3))))
;-> (quote (1 2 3 4 . 0))

(pl-data (pl-collect (add1 x) (x (pl 0 1 2 3))))
;-> (quote (1 2 3 4 . 0))

(pl-data (pl-collect x (x (pl 0 1 2 3 4 5) (odd? x))))
;-> (quote (1 3 5 . 0))

(pl-data (pl-collect x (x (pl 0 1 2 3 4 5) (odd? x))))
;-> (quote (1 3 5 . 0))

(pl-data (pl-collect (* 10 n) (n (pl 0 1 2 3 4 5) (positive? n) (even? n))))
;-> (quote (20 40 . 0))

(pl-data (pl-collect (list c k) (c (pl 'A 'B 'C)) (k (pl 1 2 3 4))))
;-> (quote ((A 1) (A 2) (A 3) (A 4) (B 1) (B 2) (B 3) (B 4) (C 1) (C 2) (C 3) (C 4) . 0))

(newline)

Requirements

None

Last update

Feb 15, 2021

Author

Juergen Lorenz

Repository

This egg is hosted on the CHICKEN Subversion repository:

https://anonymous@code.call-cc.org/svn/chicken-eggs/release/5/pseudolists

If you want to check out the source code repository of this egg and you are not familiar with Subversion, see this page.

License

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

Version History

3.0: pseudolists as parametrized (or tagged) lists
2.0: sentinels kept, not stripped
1.4: pl-maker added
1.3: sentinel-options removed, all constructors create ordinary lists
1.2: macro pl-for renamed pl-collect
1.1: some sentinel-option arguments added; syntax-change of pl-for and pl-iterate
1.0: initial import