chickadee » sequences

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.

sequences

Introduction

Operations over generic or user-defined sequences.

Note: this is currently under review - the API might still change

Usage

(require-extension sequences)

Requirements

fast-generic

This extension requires CHICKEN 4.6.3 or newer.

Documentation

A sequence is a collection of objects and may be either one of the built-in types vector, list or string, or the result of the sequence-constructors make-linear-sequence and make-random-access-sequences. A linear sequence is a sequence that only allows element-by-element access (i.e. a list), a random access sequences allows access to arbitrary elements through an index (i.e. vectors or strings).

An iterator is an object that designates a particular position in a linear or random-access sequence.

Basic sequence operations

size
size Sprocedure

Returns the number of elements in the sequence S. For linear sequences, this operation traverses all elements.

elt
elt S Iprocedure

Returns the I-th element of S. I may be an exact integer or an iterator (see below).

A sequence-element can be modified with (set! (elt S I) X).

If I is an iterator, then S must be the same sequence that had been used to construct the iterator.

rev
rev Sprocedure

Returns a new sequence of the same type with the elements of S in reverse order.

foldl
foldl PROC SEED Sprocedure

Performs a left "fold" over the sequence S, where the procedure PROC is applied to its previous result (or SEED for the first element) and each sequence-element.

foldr
foldr PROC SEED Sprocedure

A right "fold" over sequence S, PROC is applied to each sequence element and the result of its last invocation (or SEED for the first element).

sub
sub S START #!optional ENDprocedure

Returns a new sequence with the elements of S, starting at position START up to but not including the element at position END. If END is not given, all remaining elements are returned. START and END may be exact integers or iterators.

A range of elements may be modified by executing (set! (sub S1 START [END]) S2), which assigns the elements of S2 to the designated locations of sequence S1.

pos
pos PRED Sprocedure

Returns the index of the first element in S that for which the one argument procedure PRED returns true. If PRED returns false for all arguments, #f is returned.

take
take PRED Sprocedure

Returns a new sequence of the same type as S with the elements up to but not including the first element for which the one-argument procedure PRED returns #f.

drop
drop PRED Sprocedure

Returns a new sequence of the same type as S with the elements from the first element for which the one-argument procedure PRED returns #f.

split
split PRED Sprocedure

Returns two sequences of the same type as S holding the elements split at the first position for which the one-argument procedure PRED returns #f.

partition
partition PRED Sprocedure

Returns two sequences of the same type as S holding those elements for which the one-argument procedure PRED returns true and false, respectively.

fill!
fill! PROC S #!optional START ENDprocedure

Calls PROC with the sequence S and an iterator object over the elements in S starting at position START up to but not including END and returns the modified sequence.

all?
all? PROC Sprocedure

Returns true if PROC returns true for all elements of S.

thereis?
thereis? PROC Sprocedure

Returns #t if S contains an element for which PROC returns true.

empty?
empty? Sprocedure

Returns true if S is of size 0.

peek
peek Sprocedure

Returns the first element of S.

pop
pop Sprocedure

Returns all but the first element of S.

filter
filter PROTO PROC Sprocedure

Returns a new sequence of the same type as PROTO with all elements of S for which PROC returns true.

Set-operations

intersection
intersection PROTO COMPARE S1 ...procedure

Returns the intersection of sequences S1 ... using the two-argument procedure COMPARE to compare the elements. The returned sequence is of the same type as PROTO.

difference
difference PROTO COMPARE S1 S2 ...procedure

Returns the set-difference of sequences S2 ... taken from S1 using the two-argument procedure COMPARE to compare the elements. The returned sequence is of the same type as PROTO.

union
union PROTO COMPARE S1 ...procedure

Returns the union of sequences S1 ... using the two-argument procedure COMPARE to compare the elements. The returned sequence is of the same type as PROTO.

Predicates over sequence types

sequence?
sequence? Xprocedure

Returns #t if X is a sequence or #f otherwise.

linear-sequence?
linear-sequence? Xprocedure

Reurns #t if X is a list or a sequence created with make-linear-sequence or #f otherwise.

random-access-sequence?
random-access-sequence? Xprocedure

Returns #t if X is a vector, a string or a sequence created with make-random-access-sequence, or #f otherwise.

Sequence constructors

make-random-access-sequence
make-random-access-sequence MAKE ELT SIZEprocedure

Returns an object representing a sequence that allows random access to its elements. MAKE should be a procedure of two arguments, a size count and an initial value and should return a collection of elements which will be stored as "data" in the sequence object. ELT should be a procedure of two arguments receiving the "data" and an exact integer index and should return the element inside the data collection at the given position. SIZE should be a procedure that receives the data and returns the number of elements in that collection.

Note that the "data" may be anything - the operators fully define how it is interpreted.

make-linear-sequence
make-linear-sequence MAKE ELT NEXTprocedure

Returns an object representing a sequence that only allows sequential "on-at-a-time" access to its elements. MAKE should be a procedure of two arguments, a size count and an initial value and should return a collection of elements which will be stored as "state" in the sequence object. ELT should be a procedure of one argument receiving the "state" and should return the element inside the collection that is represented by the currently stored state. NEXT should be a procedure that receives the current state and returns a new state representing the underlying collection that will make the next element accessible via ELT. If the collection has run out of elements, NEXT should return #f.

make
make S LENGTH INITprocedure

Creates a sequence of the same type as S with LENGTH elements that have the initial value INIT.

sequence
sequence S X1 ...procedure

Creates a sequence of the same type as S with X1, ... as its initial elements.

Iterators

iterator?
iterator? Xprocedure

Returns #t if X is an iterator object or #f otherwise.

linear-iterator?
linear-iterator? Xprocedure

Returns #t if X is an iterator on a linear sequence or #f otherwise.

random-access-iterator?
random-access-iterator? Xprocedure

Returns #t if X is an iterator on a random-access sewuence or #f otherwise.

iterator
iterator S #!optional INDEXprocedure

Returns an iterator object over sequence S, optionally starting at osition INDEX (an exact integer).

at-end?
at-end? ITERATORprocedure

Returns #t if ITERATOR points past the lat element of its associated sequence or #f otherwise.

advance
advance!
advance ITERATOR #!optional STEPSprocedure
advance! ITERATOR #!optional STEPSprocedure

Returns a new iterator (or modifies the given iterator in case of advance!) pointing to the next element of the associated sequence or to the element at the position I + STEPS, where I is the current index of ITERATOR.

index
index ITERATORprocedure

Returns the exact integer index of the position to which ITERATOR points to.

Iteration constructs

for
for*
for PROC Sprocedure
for* PROC Sprocedure

Invokes PROC for each element in sequence and returns an undefined result. for* operates as for but invokes PROC with the sequence S and an iterator pointing to the current element.

smap
smap*
smap S1 PROC S2procedure
smap S1 PROC S2procedure

Applies PROC to each element in the sequence S2 and returns a new sequence of the same type as S1 constructed of the results returned by PROC.

Other operations

coerce
coerce S1 S2procedure

Returns a new sequence of the same type as S1 containing the elements of S2.

copy
copy Sprocedure

Returns a copy of the sequence S.

is?
is? Xprocedure

Returns a single-argument procedure that returns #t if the argument is equal? to X or #f otherwise.

SRFI-42 comprehensions

(This code was kindly contributed by Thomas Chust)

SRFI-42 comprehensions for sequences are provided using the :seq generator, here an example:

 (string-ec (:seq x "aAbBcC") (if (char-lower-case? x)) x)  ==>  "abc"

This is mostly useful with user-defined sequences created by make-linear-sequence and make-random-access-sequence.

To use this feature, execute

 (require-extension sequence-comprehensions)

Author

felix

License

Copyright (c) 2010-2011, Felix L. Winkelmann and Thomas Chust
All rights reserved. 

Redistribution and use in source and binary forms, with or without 
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. 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.
3. The name of the authors may not be used to endorse or promote products
   derived from this software without specific prior written permission. 

THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``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 AUTHORS 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

0.4
removed replicate, renamed contains? to thereis?, performance tuning
0.3
added replicate, various bugfixes
0.2
added set-operations and some more
0.1
initial release

Contents »