Sequence-Utilities
, written by Matthias
Hölzl, provides common or oft-used operations performed on
<sequence>
s. The whole module is
rather Lispy in flavor, and has the feel of an elegant hack by
the way functions use predicate functions to manipulate lists.
We start off with a group of generic functions that give
boolean responses to type information requests (e.g. "Are you
a <list>
?").
pair? | [Generic] |
Check whether this sequence is a pair.
Synopsis
pair? (arg) => (ans)
Parameters
arg An instance of <object>
.
Return Values
ans An instance of <boolean>
.
Description
This generic function has two specializers, one that takes instances of
<pair>
(and subclasses of it) which returns#t
and one that takes anything else which returns#f
.
null? | [Generic] |
Check whether this sequence is the empty list.
Synopsis
null? (arg) => (ans)
Parameters
arg An instance of <object>
.
Return Values
ans An instance of <boolean>
.
Description
To my mind, this generic function's name is a bit misleading: this returns
#t
if the instance is an<empty-list>
.
list? | [Generic] |
Check whether this sequence is a list.
Synopsis
list? (arg) => (ans)
Parameters
arg An instance of <object>
.
Return Values
ans An instance of <boolean>
.
Description
Returns
#t
if the instance is a<list>
;#f
otherwise.
This section and its subsections describe the functions that create sequences.
This set of functions provides ways to create sequences from other sequences.
xpair | [Function] |
Occasionally useful as a value to be passed to a fold or other higher-order procedure.
Synopsis
xpair (list, elt) => (new-list)
Parameters
list An instance of <list>
.elt An instance of <object>
. The element to add to the list
Return Values
new-list An instance of <list>
.
Description
Xpair
putselt
at the head oflist
.
list* | [Function] |
Likelist
, but cons the first elements onto the last element ofrest
.
Synopsis
list* (#rest rest) => (new-list)
Parameters
rest Instances of <object>
.
Return Values
new-list An instance of <list>
.
Description
I find description by example best here:
list*(1, 2, 3, 4, 5) => #(1, 2, 3, 4 . 5) list*(1, 2, #(3, 4), 5) => #(1, 2, #(3, 4) . 5) list*(1, 2, 3, #(4, 5)) => #(1, 2, 3, 4, 5)
reverse-append | [Generic] |
Prepend a reversed sequence to another sequence.
Synopsis
reverse-append (reversed-head, tail) => (new-sequence)
Parameters
reversed-head An instance of <sequence>
. A reversed sequence to be prepended beforetail
.tail An instance of <sequence>
.
Return Values
new-sequence An instance of <sequence>
.
Description
reverse-append(#[5, 4, 3, 2, 1], #[6, 7, 8]) => #[1, 2, 3, 4, 5, 6, 7, 8]
The next set of functions creates
<sequence>
s from functions.
tabulate | [Function] |
Make a sequence by performing a function on the index.
Synopsis
tabulate (length, func, #key type) => (list)
Parameters
length An instance of <integer>
.func An instance of <function>
.Func
takes one argument: the index (an<integer>
).type:
An instance of <object>
. Defaults to<list>
.
Return Values
list An instance of <mutable-sequence>
.
Description
Make a sequence of type
type
whose i-th element isfunc
(i) for 0 <= i <length
.Type
must be a subtype of<mutable-sequence>
.For example, I want a vector of the annual worth of an account of 10000 USD earning 10 percent annually. The below code creates that vector:
tabulate(10, method(x) 10000 * exp(x * .1) end, type: <vector>)Or, to create a list of factorials, one could write this:
define function factorial(x :: limited(<integer>, min: 0)) => (y :: <integer>) if(x == 0) 1; else reduce1(\*, tabulate(x, curry(\+, 1))); end if; end function factorial; tabulate(6, factorial);
This section describes functions that return parts of sequences.
take | [Generic] |
Returns part of a sequence.
Synopsis
take (collection, k) => (seq)
Parameters
collection An instance of <object>
.k An instance of <integer>
. Determines which part of the sequence to return.
Return Values
seq An instance of <object>
.
Description
if
k
> 0 return a new sequence consisting of the firstk
elements ofcollection
, otherwise return a new sequence consisting of the lastk
elements ofcollection
.For example:
take(#(0, 5, 10, 15, 20, 25, 30), 5) => #(0, 5, 10, 15, 20, 25) take(#(0, 3, 6, 9, 12, 15, 18), -3) => #(12, 15, 18)
drop | [Generic] |
Returns part of a sequence.
Synopsis
drop (collection, k) => (seq)
Parameters
collection An instance of <object>
.k An instance of <integer>
. Determines which part of the sequence to return.
Return Values
seq An instance of <object>
.
Description
if
k
> 0 return a new sequence consisting of all but the firstk
elements ofcollection
, otherwise return a new sequence consisting of all but the lastk
elements ofcollection
.For example:
drop(#(0, 5, 10, 15, 20, 25, 30), 5) => #(25, 30) drop(#(0, 3, 6, 9, 12, 15, 18), -3) => #(0, 3, 6, 9)
last-pair | [Function] |
Return the last pair in a non-empty list.
Synopsis
last-pair (lst) => (last-pair)
Parameters
lst An instance of <pair>
.
Return Values
last-pair An instance of <pair>
.
Description
I find description by example best here, as well:
last-pair(1, 2, 3, 4, 5) => #(5) last-pair(1, 2, 3, #(4, 5)) => #(#(4, 5)) last-pair(1, 2, 3, 4 . 5) => failsThe last example fails because last-pair expects the elements of the list to be pairable ... in this case 5 is not.
heads | [Function] |
A list of all the heads of members of a list.
Synopsis
heads (lists) => (new-list)
Parameters
lists An instance of <list>
. A list of lists
Return Values
new-list An instance of <list>
.
Description
In a list of lists, this function returns a list of the first elements of each of the lists
heads(#(#(1, 5, 10), #(2, 4, 6), #(3, 6, 9))) => #(1, 2, 3)
tails | [Function] |
A list of all the tails of members of a list.
Synopsis
tails (lists) => (new-list)
Parameters
lists An instance of <list>
. A list of lists
Return Values
new-list An instance of <list>
.
Description
In a list of lists, this function returns a list of the all but first elements of each of the lists
tails(#(#(1, 5, 10), #(2, 4, 6), #(3, 6, 9))) => #(#(5, 10), #(4, 6), #(6, 9))
These functions inspect elements of a sequence and return information on them.
satisfies | [Method] |
Find an element, return its index
Synopsis
satisfies (pred, seq, #key failure) => (index)
Parameters
pred An instance of <function>
. The test function to find the element.seq An instance of <sequence>
.failure:
An instance of <object>
. The value returned if a matching element is not found. Defaults to#f
.
Return Values
index An instance of <object>
. The index of the found element.
Description
Locates an element in
seq
that returns a value (i.e. not#f
) frompred
, and returns the index. Note, the index is not necessarily an integer ...<table>
can use non-integer indices.
index | [Method] |
Find an element, return its index
Synopsis
index (elt, seq, #key test, failure) => (index)
Parameters
elt An instance of <object>
. The sought element.seq An instance of <sequence>
.test:
An instance of <object>
. The test function to find the element. Defaults to\=
.failure:
An instance of <object>
. The value returned if a matching element is not found. Defaults to#f
.
Return Values
index An instance of <object>
. The index of the found element.
Description
Very much like the
satisfies
function. This allows the user to specify the element sought, and assumes thetest
is\=
by default.
find | [Method] |
Find an element
Synopsis
find (pred, seq, #key failure) => (obj)
Parameters
pred An instance of <function>
.seq An instance of <sequence>
.failure:
An instance of <object>
. The value returned if a matching element is not found. Defaults to#f
.
Return Values
obj An instance of <object>
. The found element.
Description
The
find
function locates and returns an object in a sequence when that object matches the predicate function passed in aspred
.
find-tail | [Method] |
Gives the rest of a list from a found element.
Synopsis
find-tail (pred, seq, #key failure) => (result)
Parameters
pred An instance of <function>
.seq An instance of <sequence>
.failure:
An instance of <object>
. The value returned if a matching element is not found. Defaults to#f
.
Return Values
result An instance of <object>
. The found list.
Description
The
find-tail
function locates an object in a sequence when that object matches the predicate function passed in aspred
. When that element is found, it, and the rest of the sequence, is returned as theresult
.
precedes? | [Method] |
Verifies that one element comes before another in a sequence.
Synopsis
precedes? (elt-1, elt-2, seq, #key test, not-found) => (precedes?)
Parameters
elt-1 An instance of <object>
. The preceding element.elt-2 An instance of <object>
. The following element.seq An instance of <sequence>
.test:
An instance of <object>
. The test function to find the elements. Defaults to\=
.not-found:
An instance of <object>
. The value returned if either element not found. Defaults to#f
.
Return Values
precedes? An instance of <boolean>
.
Description
Ensures
elt-2
followselt-1
, inseq
, if so, returns#t
.
These higher-order functions require an understanding of the mapping and reducing functions found in the Dylan Reference Manual described on pages 327 and on. What they do is to perform an operation on a sequence to obtain a result.
foldr | [Function] |
Rebuilds a list by applying a function over it.
Synopsis
foldr (cons, nil, lst) => (result)
Parameters
cons An instance of <function>
. A function that takes two arguments and returns a<pair>
.nil An instance of <object>
. Value returned if the list is empty (in most cases, this should be#()
).lst An instance of <list>
.
Return Values
result An instance of <list>
.
Description
This function rebuilds a list by recursively applying a function over the list. For example, to copy a list, one would write:
foldr(pair, #(), #(1, 2, 3, 4, 5)) => #(1, 2, 3, 4, 5)Exercise: what is the result when you replace
pair
withlist
?
foldl | [Function] |
Rebuilds a list by applying a function over it.
Synopsis
foldl (cons, nil, lst) => (result)
Parameters
cons An instance of <function>
. A function that takes two arguments and returns a<pair>
.nil An instance of <object>
. Value returned if the list is empty (in most cases, this should be#()
).lst An instance of <list>
.
Return Values
result An instance of <list>
.
Description
Foldr
in reverse. This function rebuilds a list by recursively applying a function over the list. For example:foldl(method(x, y) pair(factorial(x), y) end, #f, #(1, 2, 3, 4, 5)) => #(120, 24, 6, 2, 1 . #f)Note: the ugly dotted pair at the end is what occurs when
nil
is not#()
.
concatenate-map | [Method] |
Concatenates sequences then maps a function over them.
Synopsis
concatenate-map (func, seq, #rest seqs) => (new-sequence)
Parameters
func An instance of <function>
.seq An instance of <sequence>
.seqs Instances of <object>
.
Return Values
new-sequence An instance of <sequence>
.
Description
Concatenates
seq
and all members ofseqs
together and mapsfunc
over the resulting list. The order of function applications is unspecified.
choose-map | [Method] |
Maps a function over a sequence, then chooses selected elements.
Synopsis
choose-map (pred, func, seq, #rest seqs) => (new-sequence)
Parameters
pred An instance of <function>
.func An instance of <function>
.seq An instance of <sequence>
.seqs Instances of <object>
.
Return Values
new-sequence An instance of <sequence>
.
Description
Map
func
acrosslst
and save up all the results that satisfypred
.
pair-do | [Function] |
Like do, except that it takes multiple argument lists
Synopsis
pair-do (func, lst, #rest lists) => (false)
Parameters
func An instance of <function>
. A function that takes 1 or more instances of<list>
as arguments.lst An instance of <list>
. A list of values that will be used as the first argument tofunc
.lists Instances of <list>
. Each argument should be a<list>
.
Return Values
false An instance of <boolean>
.#f
Description
This function takes a n-ary function, and n instances of
<list>
as arguments. It then appliesfunc
to all of the lists, and then recursively appliesfunc
to all of the sublists of the lists. Contrast this with thedo
function, which is applied to each set of elements of the arguments rather to sublists.
pair-foldl | [Function] |
This function is like foldl
, but works on
sublists.
Synopsis
pair-foldl (cons, nil, lst) => (obj)
Parameters
cons An instance of <function>
. This argument is a function that can take two objects as arguments and returns a new object.nil An instance of <object>
.lst An instance of <list>
.
Return Values
obj An instance of <object>
.
Description
This function is similar to
foldl
, except that it operates on sublists instead of elements. That is, its recursion scheme is as follows: iflst
is#(e1, e2, ..., en)
, then this function returns
cons(#(en), cons(..., cons(#(e2,...en), cons(#(e1,...,en), nil) ...)))
pair-foldr | [Function] |
This function is like foldr
, but works on
sublists.
Synopsis
pair-foldr (cons, nil, lst) => (obj)
Parameters
cons An instance of <function>
. This argument is a function that can take two objects as arguments and returns a new object.nil An instance of <object>
.lst An instance of <list>
.
Return Values
obj An instance of <object>
.
Description
This function is similar to
foldr
, except that it operates on sublists instead of elements. That is, its recursion scheme is as follows: iflst
is#(e1, e2, ..., en)
, then this function returns
cons(#(e1, ..., en), cons(#(e2,...en), cons(..., cons(#(en), nil) ...)))
partition | [Function] |
Returns two lists: one that satisfies a predicate, and one that doesn't.
Synopsis
partition (pred, seq) => (winners, losers)
Parameters
pred An instance of <function>
.seq An instance of <sequence>
.
Return Values
winners An instance of <list>
. The list of elements that satisfy the predicate.losers An instance of <list>
. The list of elements that do not.
Description
This is very much like
choose
found in the Dylan Reference Manual (page 333), except this function also returns the elements that did not match the predicate.
unfold | [Function] |
This function is dual to fold
; instead of
taking some functions and a list and producing a value,
it takes a value and some functions and produces a list.
Synopsis
unfold (pred, f, g, seed) => (new-list)
Parameters
pred An instance of <function>
. This function takes a seed value and returns#t
to terminate the sequence of recursive calls building the list.f An instance of <function>
. This function takes a seed value and produces a list element.g An instance of <function>
. This function takes a seed value and returns a new seed value.seed An instance of <object>
. The initial seed value.
Return Values
new-list An instance of <list>
.
Description
This function will return
#()
ifpred(seed)
is true. Otherwise it builds a pair of the formpair(f(seed), unfold(pred, f, g, g(seed) ))
.Thus, this function will always return a proper list, if it terminates at all.
unfold/tail | [Function] |
This function is similar to unfold
, except
that it can also be used to build an improper list.
Synopsis
unfold/tail (pred, f, g, e, seed) => (new-list)
Parameters
pred An instance of <function>
. This function takes a seed value and returns#t
to terminate the sequence of recursive calls building the list.f An instance of <function>
. This function takes a seed value and produces a list element.g An instance of <function>
. This function takes a seed value and returns a new seed value.e An instance of <function>
. Whenpred
returns#t
this function is called on the seed to return the value of the tail of the last pair of the list.seed An instance of <object>
. The initial seed value.
Return Values
new-list An instance of <list>
.
Description
This function will return
e(seed)
ifpred(seed)
is true. Otherwise it builds a pair of the formpair(f(seed), unfold(pred, f, g, g(seed) ))
.If
e
always returns#()
thenunfold/tail
has the same behavior asunfold
.
Those familiar with Lisp will feel at home here.
Associative lists are <list>
s
that contain <pair>
s of entries
(in a #(key, value)
format). Much like
<table>
s, one make look up the
key to obtain the value information.
assoc | [Function] |
Looks up a value given a key
Synopsis
assoc (elt, seq, #key key, test) => (found)
Parameters
elt An instance of <object>
. The key element to find the value elementseq An instance of <sequence>
.key:
An instance of <object>
. The function used to obtain the key element in the associative list. Defaults tohead
.test:
An instance of <object>
. The function used to compare. Defaults to\=
.
Return Values
found An instance of <object>
. The value element from the found key.
Description
Find the tuple associated with
key
in the association sequenceseq
.
apair | [Function] |
Adds an association to a sequence.
Synopsis
apair (key, datum, aseq, #key cons, add) => (new-aseq)
Parameters
key An instance of <object>
. The key element of the association.datum An instance of <object>
. The value element of the association.aseq An instance of <sequence>
.cons:
An instance of <object>
. The function used to create the association from the key and datum parameters. Defaults topair
.add:
An instance of <object>
. The function used to add the association onto the sequence. Defaults toxpair
.
Return Values
new-aseq An instance of <object>
. The new associative list.
Description
Cons a new pair
#(key, datum)
on the head ofaseq
.
alist-copy | [Function] |
Copies an associative list.
Synopsis
alist-copy (alist, #key key, datum, cons) => (new-aseq)
Parameters
alist An instance of <sequence>
.key:
An instance of <object>
. The function used to obtain the key element from the association. Defaults tohead
.datum:
An instance of <object>
. The function used to obtain the value element. Defaults totail
.cons:
An instance of <object>
. The function used to create the association from the key and datum parameters. Defaults topair
.
Return Values
new-aseq An instance of <object>
. The new associative list.
Description
Copy an "associative list", actually any sequence that can act like an associative list.
alist-delete | [Function] |
Deletes associations from the associative list.
Synopsis
alist-delete (elt, alist, #key key, test) => (new-alist)
Parameters
elt An instance of <object>
. The key element of the association to be removed.alist An instance of <sequence>
.key:
An instance of <object>
. The function used to obtain the key element from the association. Defaults tohead
.test:
An instance of <object>
. The function used to compare keys. Defaults to\=
.
Return Values
new-alist An instance of <object>
. The new associative list.
Description
Delete all members keyed by
elt
fromalist
.
The following bindings (all of which are functions) have not yet been described. I will add these descriptions as time and understanding permit. For now, you must rely on the best documentation available ... the source code in src/common/coll-ext/sequence-utils.dylan.
reduce-l
reduce-r