7.1.10 Collections

(require 'collect)

Routines for managing collections. Collections are aggregate data structures supporting iteration over their elements, similar to the Dylan(TM) language, but with a different interface. They have elements indexed by corresponding keys, although the keys may be implicit (as with lists).

New types of collections may be defined as YASOS objects (see Yasos). They must support the following operations:

• (collection? self) (always returns #t);
• (size self) returns the number of elements in the collection;
• (print self port) is a specialized print operation for the collection which prints a suitable representation on the given port or returns it as a string if port is #t;
• (gen-elts self) returns a thunk which on successive invocations yields elements of self in order or gives an error if it is invoked more than (size self) times;
• (gen-keys self) is like gen-elts, but yields the collection’s keys in order.

They might support specialized for-each-key and for-each-elt operations.

Function: collection? obj

A predicate, true initially of lists, vectors and strings. New sorts of collections must answer #t to collection?.

Procedure: map-elts proc collection1 …

Procedure: do-elts proc collection1 …

proc is a procedure taking as many arguments as there are collections (at least one). The collections are iterated over in their natural order and proc is applied to the elements yielded by each iteration in turn. The order in which the arguments are supplied corresponds to te order in which the collections appear. do-elts is used when only side-effects of proc are of interest and its return value is unspecified. map-elts returns a collection (actually a vector) of the results of the applications of proc.

Example:

(map-elts + (list 1 2 3) (vector 1 2 3))
   ⇒ #(2 4 6)

Procedure: map-keys proc collection1 …

Procedure: do-keys proc collection1 …

These are analogous to map-elts and do-elts, but each iteration is over the collections’ keys rather than their elements.

Example:

(map-keys + (list 1 2 3) (vector 1 2 3))
   ⇒ #(0 2 4)

Procedure: for-each-key collection proc

Procedure: for-each-elt collection proc

These are like do-keys and do-elts but only for a single collection; they are potentially more efficient.

Function: reduce proc seed collection1 …

A generalization of the list-based reduce-init (see Lists as sequences) to collections.

Examples:

(reduce + 0 (vector 1 2 3))
   ⇒ 6
(reduce union '() '((a b c) (b c d) (d a)))
   ⇒ (c b d a).

Reduce called with two arguments will work as does the procedure of the same name from See Common List Functions.

Function: any? pred collection1 …

A generalization of the list-based some (see Lists as sequences) to collections.

Example:

(any? odd? (list 2 3 4 5))
   ⇒ #t

Function: every? pred collection1 …

A generalization of the list-based every (see Lists as sequences) to collections.

Example:

(every? collection? '((1 2) #(1 2)))
   ⇒ #t

Function: empty? collection

Returns #t iff there are no elements in collection.

(empty? collection) ≡ (zero? (size collection))

Function: size collection

Returns the number of elements in collection.

Function: Setter list-ref

See Setters for a definition of setter. N.B. (setter list-ref) doesn’t work properly for element 0 of a list.

Here is a sample collection: simple-table which is also a table.

(define-predicate TABLE?)
(define-operation (LOOKUP table key failure-object))
(define-operation (ASSOCIATE! table key value)) ;; returns key
(define-operation (REMOVE! table key))          ;; returns value

(define (MAKE-SIMPLE-TABLE)
  (let ( (table (list)) )
    (object
     ;; table behaviors
     ((TABLE? self) #t)
     ((SIZE self) (size table))
     ((PRINT self port) (format port "#<SIMPLE-TABLE>"))
     ((LOOKUP self key failure-object)
      (cond
       ((assq key table) => cdr)
       (else failure-object)
       ))
     ((ASSOCIATE! self key value)
      (cond
       ((assq key table)
        => (lambda (bucket) (set-cdr! bucket value) key))
       (else
        (set! table (cons (cons key value) table))
        key)
       ))
     ((REMOVE! self key);; returns old value
      (cond
       ((null? table) (slib:error "TABLE:REMOVE! Key not found: " key))
       ((eq? key (caar table))
        (let ( (value (cdar table)) )
          (set! table (cdr table))
          value)
        )
       (else
        (let loop ( (last table) (this (cdr table)) )
          (cond
           ((null? this)
            (slib:error "TABLE:REMOVE! Key not found: " key))
           ((eq? key (caar this))
            (let ( (value (cdar this)) )
              (set-cdr! last (cdr this))
              value)
            )
           (else
            (loop (cdr last) (cdr this)))
           ) ) )
       ))

     ;; collection behaviors
     ((COLLECTION? self) #t)
     ((GEN-KEYS self) (collect:list-gen-elts (map car table)))
     ((GEN-ELTS self) (collect:list-gen-elts (map cdr table)))
     ((FOR-EACH-KEY self proc)
      (for-each (lambda (bucket) (proc (car bucket))) table)
      )
     ((FOR-EACH-ELT self proc)
      (for-each (lambda (bucket) (proc (cdr bucket))) table)
      ) ) ) )