chickadee » pseudolists

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

pl-parameterparameter

pl-parameter newparameter

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

pl-checker

pl-checker ok? argprocedure

pl-checker ok?procedure

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?

pl-checker? xprprocedure

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

pl

pl #!rest argsprocedure

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?

pl? xprprocedure

type predicate

pl-maker

pl-maker len fillprocedure

pl-maker lenprocedure

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

pl-at

pl-at k plsprocedure

pl-at kprocedure

returns the kth item of pls

pl-set!

pl-set! k val plsprocedure

sets the kth item of pls to val

pl-length

pl-length plsprocedure

returns the length of the pseudolist pls

pl-null?

pl-null? xprprocedure

checks, if no items are stored in the pseudolist xpr

pl-head

pl-head plsprocedure

returns the list part of the pseudolist pls

pl-tail

pl-tail plsprocedure

returns the sentinel of the pseudolist pls

pl-data

pl-data plsprocedure

returns the dotted list underlying the pseudolist pls

pl-cons

pl-cons x plsprocedure

pl-cons xprocedure

adds the item x to the front of the pseudolist pls

pl-car

pl-car plsprocedure

returns the first item of the pseudolist pls

pl-cdr

pl-cdr plsprocedure

returns a new pseudolist removing the first item of pls

pl-of?

pl-of? tag #!rest predsprocedure

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

pl-iterate

pl-iterate fn times initprocedure

pl-iterate fn timesprocedure

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

pl-drop

pl-drop n plsprocedure

pl-drop nprocedure

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

pl-drop-while

pl-drop-while ok? plsprocedure

pl-drop-while ok?procedure

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

pl-take

pl-take n plsprocedure

pl-take nprocedure

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

pl-take-while

pl-take-while ok? plsprocedure

pl-take-while ok?procedure

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

pl-reverse

pl-reverse plprocedure

reverses its pseudolist argument to a new pseudolist with same sentinel

pl-map

pl-map fn #!rest plssprocedure

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

pl-for-each fn pls #!rest plssprocedure

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

pl-memp ok? plsprocedure

pl-memp ok?procedure

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

pl-memq x plsprocedure

pl-memq xprocedure

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

pl-memv

pl-memv x plsprocedure

pl-memv xprocedure

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

pl-member

pl-member x plsprocedure

pl-member xprocedure

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

pl-index

pl-index ok? plsprocedure

pl-index ok?procedure

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

pl-filter

pl-filter ok? plsprocedure

pl-filter ok?procedure

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

pl-append pls #!rest plssprocedure

appends all argument pseudolist, provided their tags are all equal

pl-fold-right

pl-fold-right op init plsprocedure

pl-fold-right op initprocedure

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

pl-fold-right0

pl-fold-right0 op plsprocedure

pl-fold-right0 opprocedure

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

pl-fold-left

pl-fold-left op init plsprocedure

pl-fold-left op initprocedure

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

pl-fold-left0

pl-fold-left0 op plsprocedure

pl-fold-left0 opprocedure

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

pl-adjoin

pl-adjoin obj plsprocedure

pl-adjoin objprocedure

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

pl-remove-dups

pl-remove-dups plsprocedure

removes the duplicates in the pseudolist pls

pl-flat?

pl-flat? xprprocedure

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

pl-flatten

pl-flatten pl-treeprocedure

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

(pl-collect item-xpr (var pls ok-xpr ...))syntax

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

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

pseudolistsprocedure

pseudolists symprocedure

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

Copyright (c) 2013-2021 , Juergen Lorenz, ju (at) jugilo (dot) de 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

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