data-structures | chickadee

Outdated CHICKEN release

This is a manual page for an old and unsupported version of CHICKEN. If you are still using it, please consider migrating to the latest version. You can find the manual for the latest release here.

Unit data-structures

This unit contains a collection of procedures related to data structures. This unit is used by default, unless the program is compiled with the -explicit-use option.

Lists

alist-ref

alist-ref KEY ALIST #!optional TEST DEFAULTprocedure: Looks up KEY in ALIST using TEST as the comparison function (or eqv? if no test was given) and returns the cdr of the found pair, or DEFAULT (which defaults to #f).

alist-update

alist-update KEY VALUE ALIST #!optional TESTprocedure
alist-update! KEY VALUE ALIST #!optional TESTprocedure: If the list ALIST contains a pair of the form (KEY . X), then this procedure replaces X with VALUE and returns ALIST. If ALIST contains no such item, then alist-update returns ((KEY . VALUE) . ALIST). The optional argument TEST specifies the comparison procedure to search a matching pair in ALIST and defaults to eqv?. alist-update! is the destructive version of alist-update.

atom?

atom? Xprocedure: Returns #t if X is not a pair. This is identical to not-pair? from Unit srfi-1 but kept for historical reasons.

rassoc

rassoc KEY LIST #!optional TESTprocedure: Similar to assoc, but compares KEY with the cdr of each pair in LIST using TEST as the comparison procedures (which defaults to eqv?.

butlast

butlast LISTprocedure: Returns a fresh list with all elements but the last of LIST.

chop

chop LIST Nprocedure

Returns a new list of sublists, where each sublist contains N elements of LIST. If LIST has a length that is not a multiple of N, then the last sublist contains the remaining elements.

(chop '(1 2 3 4 5 6) 2) ==> ((1 2) (3 4) (5 6))
(chop '(a b c d) 3)     ==> ((a b c) (d))

compress

compress BLIST LISTprocedure

Returns a new list with elements taken from LIST with corresponding true values in the list BLIST.

(define nums '(99 100 110 401 1234))
(compress (map odd? nums) nums)      ==> (99 401)

flatten

flatten LIST1 ...procedure: Returns LIST1 ... concatenated together, with nested lists removed (flattened).

intersperse

intersperse LIST Xprocedure: Returns a new list with X placed between each element.

join

join LISTOFLISTS #!optional LISTprocedure

Concatenates the lists in LISTOFLISTS with LIST placed between each sublist. LIST defaults to the empty list.

(join '((a b) (c d) (e)) '(x y)) ==> (a b x y c d x y e)
(join '((p q) () (r (s) t)) '(-))  ==> (p q - - r (s) t)

join could be implemented as follows:

(define (join lstoflsts #!optional (lst '()))
  (apply append (intersperse lstoflists lst)) )

tail?

tail? X LISTprocedure: Returns true if X is one of the tails (cdr's) of LIST.

Queues

list->queue

list->queue LISTprocedure: Returns LIST converted into a queue, where the first element of the list is the same as the first element of the queue. The resulting queue may share memory with the list and the list should not be modified after this operation.

make-queue

make-queueprocedure: Returns a newly created queue.

queue?

queue? Xprocedure: Returns #t if X is a queue, or #f otherwise.

queue-length

queue-length QUEUEprocedure: Returns the current number of items stored in QUEUE.

queue->list

queue->list QUEUEprocedure: Returns QUEUE converted into a list, where the first element of the list is the same as the first element of the queue. The resulting list is freshly allocated and does not share memory with the queue object.

queue-add!

queue-add! QUEUE Xprocedure: Adds X to the rear of QUEUE.

queue-empty?

queue-empty? QUEUEprocedure: Returns #t if QUEUE is empty, or #f otherwise.

queue-first

queue-first QUEUEprocedure: Returns the first element of QUEUE. If QUEUE is empty an error is signaled

queue-last

queue-last QUEUEprocedure: Returns the last element of QUEUE. If QUEUE is empty an error is signaled

queue-remove!

queue-remove! QUEUEprocedure: Removes and returns the first element of QUEUE. If QUEUE is empty an error is signaled

queue-push-back!

queue-push-back! QUEUE ITEMprocedure: Pushes an item into the first position of a queue, i.e. the next queue-remove! will return ITEM.

queue-push-back-list!

queue-push-back-list! QUEUE LISTprocedure: Pushes the items in item-list back onto the queue, so that (car LIST) becomes the next removable item.

Sorting

merge

merge LIST1 LIST2 LESS?procedure
merge! LIST1 LIST2 LESS?procedure: Joins two lists in sorted order. merge! is the destructive version of merge. LESS? should be a procedure of two arguments, that returns true if the first argument is to be ordered before the second argument.

sort

sort SEQUENCE LESS?procedure
sort! SEQUENCE LESS?procedure: Sort SEQUENCE, which should be a list or a vector. sort! is the destructive version of sort.

sorted?

sorted? SEQUENCE LESS?procedure: Returns true if the list or vector SEQUENCE is already sorted.

topological-sort

topological-sort DAG PREDprocedure

Sorts the directed acyclic graph dag DAG so that for every edge from vertex u to v, u will come before v in the resulting list of vertices.

DAG is a list of sublists. The car of each sublist is a vertex. The cdr is the adjacency list of that vertex, i.e. a list of all vertices to which there exists an edge from the car vertex. pred is procedure of two arguments that should compare vertices for equality.

Time complexity: O (|V| + |E|)

(topological-sort
       '((shirt tie belt)
         (tie jacket)
         (belt jacket)
         (watch)
         (pants shoes belt)
         (undershorts pants shoes)
         (socks shoes))
       eq?)

=>

(socks undershorts pants shoes watch shirt belt tie jacket)

If a cycle is detected during the sorting process, an exception of the condition kinds (exn runtime cycle) is thrown.

Strings

conc

conc X ...procedure

Returns a string with the string-represenation of all arguments concatenated together. conc could be implemented as

(define (conc . args)
  (apply string-append (map ->string args)) )

->string

->string Xprocedure: Returns a string-representation of X.

string-chop

string-chop STRING LENGTHprocedure

Returns a list of substrings taken by chopping STRING every LENGTH characters:

(string-chop "one two three" 4)  ==>  ("one " "two " "thre" "e")

string-chomp

string-chomp STRING #!optional SUFFIXprocedure: If STRING ends with SUFFIX, then this procedure returns a copy of its first argument with the suffix removed, otherwise returns STRING unchanged. SUFFIX defaults to "\n".

string-compare3

string-compare3 STRING1 STRING2procedure
string-compare3-ci STRING1 STRING2procedure: Perform a three-way comparison between the STRING1 and STRING2, returning either -1 if STRING1 is lexicographically less than STRING2, 0 if it is equal, or 1 if it s greater. string-compare3-ci performs a case-insensitive comparison.

string-intersperse

string-intersperse LIST #!optional STRINGprocedure

Returns a string that contains all strings in LIST concatenated together. STRING is placed between each concatenated string and defaults to " ".

(string-intersperse '("one" "two") "three")

is equivalent to

(apply string-append (intersperse '("one" "two") "three"))

string-split

string-split STRING #!optional DELIMITER-STRING KEEPEMPTYprocedure

Split string into substrings delimited by any of the characters given in the delimiter string. If no delimiters are specified, a string comprising the tab, newline and space characters is assumed. If the parameter KEEPEMPTY is given and not #f, then empty substrings are retained:

(string-split "one  two  three") ==> ("one" "two" "three")
(string-split "foo:bar::baz:" ":" #t) ==> ("foo" "bar" "" "baz" "")
(string-split "foo:bar:baz,quux,zot" ":," ) ==> ("foo" "bar" "baz" "quux" "zot")

string-translate

string-translate STRING FROM #!optional TOprocedure: Returns a fresh copy of STRING with characters matching FROM translated to TO. If TO is omitted, then matching characters are removed. FROM and TO may be a character, a string or a list. If both FROM and TO are strings, then the character at the same position in TO as the matching character in FROM is substituted.

string-translate*

string-translate* STRING SMAPprocedure

Substitutes elements of STRING according to SMAP. SMAP should be an association-list where each element of the list is a pair of the form (MATCH . REPLACEMENT). Every occurrence of the string MATCH in STRING will be replaced by the string REPLACEMENT:

(string-translate*
  "<h1>this is a \"string\"</h1>"
  '(("<" . "&lt;") (">" . "&gt;") ("\"" . "&quot;")) )
=>  "&lt;h1&gt;this is a &quot;string&quot;&lt;/h1&gt;"

substring=?

substring=? STRING1 STRING2 #!optional START1 START2 LENGTHprocedure
substring-ci=? STRING1 STRING2 #!optional START1 START2 LENGTHprocedure: Returns #t if the strings STRING1 and STRING2 are equal, or #f otherwise. The comparison starts at the positions START1 and START2 (which default to 0), comparing LENGTH characters (which defaults to the minimum of the remaining length of both strings).

substring-index

substring-index WHICH WHERE #!optional STARTprocedure
substring-index-ci WHICH WHERE #!optional STARTprocedure: Searches for first index in string WHERE where string WHICH occurs. If the optional argument START is given, then the search starts at that index. substring-index-ci is a case-insensitive version of substring-index.

reverse-string-append

reverse-string-append LISTprocedure: (apply string-append (reverse LIST))

Combinators

any?

any? Xprocedure: Ignores its argument and always returns #t. This is actually useful sometimes.

constantly

constantly X ...procedure

Returns a procedure that always returns the values X ... regardless of the number and value of its arguments.

(constantly X) <=> (lambda args X)

complement

complement PROCprocedure

Returns a procedure that returns the boolean inverse of PROC.

(complement PROC) <=> (lambda (x) (not (PROC x)))

compose

compose PROC1 PROC2 ...procedure

Returns a procedure that represents the composition of the argument-procedures PROC1 PROC2 ....

(compose F G) <=> (lambda args
                      (call-with-values
                         (lambda () (apply G args))
                         F))

(compose) is equivalent to values.

conjoin

conjoin PRED ...procedure

Returns a procedure that returns #t if its argument satisfies the predicates PRED ....

((conjoin odd? positive?) 33)   ==>  #t
((conjoin odd? positive?) -33)  ==>  #f

disjoin

disjoin PRED ...procedure

Returns a procedure that returns #t if its argument satisfies any predicate PRED ....

((disjoin odd? positive?) 32)    ==>  #t
((disjoin odd? positive?) -32)   ==>  #f

each

each PROC ...procedure

Returns a procedure that applies PROC ... to its arguments, and returns the result(s) of the last procedure application. For example

(each pp eval)

is equivalent to

(lambda args 
  (apply pp args)
  (apply eval args) )

(each PROC) is equivalent to PROC and (each) is equivalent to void.

flip

flip PROCprocedure

Returns a two-argument procedure that calls PROC with its arguments swapped:

(flip PROC) <=> (lambda (x y) (PROC y x))

identity

identity Xprocedure: Returns its sole argument X.

list-of?

list-of? PREDprocedure

Returns a procedure of one argument that returns #t when applied to a list of elements that all satisfy the predicate procedure PRED, or #f otherwise.

((list-of? even?) '(1 2 3))   ==> #f
((list-of? number?) '(1 2 3)) ==> #t

o

o PROC ...procedure: A single value version of compose (slightly faster). (o) is equivalent to identity.

Binary searching

binary-search

binary-search SEQUENCE PROCprocedure: Performs a binary search in SEQUENCE, which should be a sorted list or vector. PROC is called to compare items in the sequence, should accept a single argument and return an exact integer: zero if the searched value is equal to the current item, negative if the searched value is less than the current item, and positive otherwise. Returns the index of the found value or #f otherwise.

Previous: Unit expand

Next: Unit ports

chickadee » data-structures

Identifier search

TOC »

Contents »