Module Sequence-Utilities

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.

Predicate Functions

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

argAn instance of <object>.

Return Values

ansAn 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

argAn instance of <object>.

Return Values

ansAn 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

argAn instance of <object>.

Return Values

ansAn instance of <boolean>.

Description

Returns #t if the instance is a <list>; #f otherwise.

Creational Functions

This section and its subsections describe the functions that create sequences.

Sequence Creational Functions using 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

listAn instance of <list>.
eltAn instance of <object>. The element to add to the list

Return Values

new-listAn instance of <list>.

Description

Xpair puts elt at the head of list.


list*[Function]

Like list, but cons the first elements onto the last element of rest.

Synopsis

list* (#rest rest) => (new-list)

Parameters

restInstances of <object>.

Return Values

new-listAn 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-headAn instance of <sequence>. A reversed sequence to be prepended before tail.
tailAn instance of <sequence>.

Return Values

new-sequenceAn instance of <sequence>.

Description

reverse-append(#[5, 4, 3, 2, 1], #[6, 7, 8]) => #[1, 2, 3, 4, 5, 6, 7, 8]
	    

Higher-Order Sequence Creational Functions

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

lengthAn instance of <integer>.
funcAn instance of <function>. Func takes one argument: the index (an <integer>).
type:An instance of <object>. Defaults to <list>.

Return Values

listAn instance of <mutable-sequence>.

Description

Make a sequence of type type whose i-th element is func(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);
              

Sequence Slicing

This section describes functions that return parts of sequences.


take[Generic]

Returns part of a sequence.

Synopsis

take (collection, k) => (seq)

Parameters

collectionAn instance of <object>.
kAn instance of <integer>. Determines which part of the sequence to return.

Return Values

seqAn instance of <object>.

Description

if k > 0 return a new sequence consisting of the first k elements of collection, otherwise return a new sequence consisting of the last k elements of collection.

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

collectionAn instance of <object>.
kAn instance of <integer>. Determines which part of the sequence to return.

Return Values

seqAn instance of <object>.

Description

if k > 0 return a new sequence consisting of all but the first k elements of collection, otherwise return a new sequence consisting of all but the last k elements of collection.

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

lstAn instance of <pair>.

Return Values

last-pairAn 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) => fails
              

The 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

listsAn instance of <list>. A list of lists

Return Values

new-listAn 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

listsAn instance of <list>. A list of lists

Return Values

new-listAn 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))
	      

Finding Sequence Elements

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

predAn instance of <function>. The test function to find the element.
seqAn instance of <sequence>.
failure:An instance of <object>. The value returned if a matching element is not found. Defaults to #f.

Return Values

indexAn instance of <object>. The index of the found element.

Description

Locates an element in seq that returns a value (i.e. not #f) from pred, 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

eltAn instance of <object>. The sought element.
seqAn 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

indexAn 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 the test is \= by default.


find[Method]

Find an element

Synopsis

find (pred, seq, #key failure) => (obj)

Parameters

predAn instance of <function>.
seqAn instance of <sequence>.
failure:An instance of <object>. The value returned if a matching element is not found. Defaults to #f.

Return Values

objAn 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 as pred.


find-tail[Method]

Gives the rest of a list from a found element.

Synopsis

find-tail (pred, seq, #key failure) => (result)

Parameters

predAn instance of <function>.
seqAn instance of <sequence>.
failure:An instance of <object>. The value returned if a matching element is not found. Defaults to #f.

Return Values

resultAn 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 as pred. When that element is found, it, and the rest of the sequence, is returned as the result.


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-1An instance of <object>. The preceding element.
elt-2An instance of <object>. The following element.
seqAn 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 follows elt-1, in seq, if so, returns #t.

Mapping and Reducing Functions

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

consAn instance of <function>. A function that takes two arguments and returns a <pair>.
nilAn instance of <object>. Value returned if the list is empty (in most cases, this should be #()).
lstAn instance of <list>.

Return Values

resultAn 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 with list?


foldl[Function]

Rebuilds a list by applying a function over it.

Synopsis

foldl (cons, nil, lst) => (result)

Parameters

consAn instance of <function>. A function that takes two arguments and returns a <pair>.
nilAn instance of <object>. Value returned if the list is empty (in most cases, this should be #()).
lstAn instance of <list>.

Return Values

resultAn 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

funcAn instance of <function>.
seqAn instance of <sequence>.
seqsInstances of <object>.

Return Values

new-sequenceAn instance of <sequence>.

Description

Concatenates seq and all members of seqs together and maps func 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

predAn instance of <function>.
funcAn instance of <function>.
seqAn instance of <sequence>.
seqsInstances of <object>.

Return Values

new-sequenceAn instance of <sequence>.

Description

Map func across lst and save up all the results that satisfy pred.


pair-do[Function]

Like do, except that it takes multiple argument lists

Synopsis

pair-do (func, lst, #rest lists) => (false)

Parameters

funcAn instance of <function>. A function that takes 1 or more instances of <list> as arguments.
lstAn instance of <list>. A list of values that will be used as the first argument to func.
listsInstances of <list>. Each argument should be a <list>.

Return Values

falseAn instance of <boolean>. #f

Description

This function takes a n-ary function, and n instances of <list> as arguments. It then applies func to all of the lists, and then recursively applies func to all of the sublists of the lists. Contrast this with the do 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

consAn instance of <function>. This argument is a function that can take two objects as arguments and returns a new object.
nilAn instance of <object>.
lstAn instance of <list>.

Return Values

objAn 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: if lst 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

consAn instance of <function>. This argument is a function that can take two objects as arguments and returns a new object.
nilAn instance of <object>.
lstAn instance of <list>.

Return Values

objAn 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: if lst 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

predAn instance of <function>.
seqAn instance of <sequence>.

Return Values

winnersAn instance of <list>. The list of elements that satisfy the predicate.
losersAn 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

predAn instance of <function>. This function takes a seed value and returns #t to terminate the sequence of recursive calls building the list.
fAn instance of <function>. This function takes a seed value and produces a list element.
gAn instance of <function>. This function takes a seed value and returns a new seed value.
seedAn instance of <object>. The initial seed value.

Return Values

new-listAn instance of <list>.

Description

This function will return #() if pred(seed) is true. Otherwise it builds a pair of the form pair(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

predAn instance of <function>. This function takes a seed value and returns #t to terminate the sequence of recursive calls building the list.
fAn instance of <function>. This function takes a seed value and produces a list element.
gAn instance of <function>. This function takes a seed value and returns a new seed value.
eAn instance of <function>. When pred returns #t this function is called on the seed to return the value of the tail of the last pair of the list.
seedAn instance of <object>. The initial seed value.

Return Values

new-listAn instance of <list>.

Description

This function will return e(seed) if pred(seed) is true. Otherwise it builds a pair of the form pair(f(seed), unfold(pred, f, g, g(seed) )) .

If e always returns #() then unfold/tail has the same behavior as unfold.

Associative Lists

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

eltAn instance of <object>. The key element to find the value element
seqAn instance of <sequence>.
key:An instance of <object>. The function used to obtain the key element in the associative list. Defaults to head.
test:An instance of <object>. The function used to compare. Defaults to \=.

Return Values

foundAn instance of <object>. The value element from the found key.

Description

Find the tuple associated with key in the association sequence seq.


apair[Function]

Adds an association to a sequence.

Synopsis

apair (key, datum, aseq, #key cons, add) => (new-aseq)

Parameters

keyAn instance of <object>. The key element of the association.
datumAn instance of <object>. The value element of the association.
aseqAn instance of <sequence>.
cons:An instance of <object>. The function used to create the association from the key and datum parameters. Defaults to pair.
add:An instance of <object>. The function used to add the association onto the sequence. Defaults to xpair.

Return Values

new-aseqAn instance of <object>. The new associative list.

Description

Cons a new pair #(key, datum) on the head of aseq.


alist-copy[Function]

Copies an associative list.

Synopsis

alist-copy (alist, #key key, datum, cons) => (new-aseq)

Parameters

alistAn instance of <sequence>.
key:An instance of <object>. The function used to obtain the key element from the association. Defaults to head.
datum:An instance of <object>. The function used to obtain the value element. Defaults to tail.
cons:An instance of <object>. The function used to create the association from the key and datum parameters. Defaults to pair.

Return Values

new-aseqAn 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

eltAn instance of <object>. The key element of the association to be removed.
alistAn instance of <sequence>.
key:An instance of <object>. The function used to obtain the key element from the association. Defaults to head.
test:An instance of <object>. The function used to compare keys. Defaults to \=.

Return Values

new-alistAn instance of <object>. The new associative list.

Description

Delete all members keyed by elt from alist.

Functions Not Yet Described

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.