generic collection interface for common lisp

1overview

Warning: This system is not yet at 1.0, and the interfaces will change as I use them more and work out design problems. Buyer beware! This system provides several related protocols and a few functions for collection manipulation in common lisp, and implementations for built-in types. It includes an interface for clojure-style reducers. While this system may be used to simply consume collections, it does not contain many utility functions for doing so, as it is intended to be used by implementors that wish to provide a clean interface to their own collection classes. As a convenience, interface packages are provided for each of the protocols defined which export only the symbols relevant to that protocol. (see com.clearly-useful.generic-collection-interface.lisp) None of the symbols exported by this system clash with common lisp.

2justification

There are many quality data structure libraries for common lisp, but they have disparate interfaces, and swapping in a new collection type to existing code can be painful. This library is an attempt to provide a sufficiently generic set of protocols so that code written to them may use any data structure appropriate to the task at hand without difficulty.

3design

The design of this library is modelled quite a bit after clojure, but it is written to integrate with common lisp. None of the symbols exported by this package clash with the cl package, and the code follows cl naming conventions. There are several packages related to this one that simply export a subset of it's interface. These packages are to help implementors who don't want to import the entire collection interface just to implement a certain aspect of it.

4protocol overview

This package defines several protocols for working with collections, some of which are interrelated.

4.1collection

This is the base protocol for the library.A collection responds to two methods:

empty -> produce an empty collection empty-p -> whether the collection is empty

4.2seqable

A thing which may be converted to a seq. This protocoldefines the method seq which serves a bit of a double duty: itmay be used to create a list-like object from another, but shouldalways return nil when it's result is empty. For example, given a(hypothetical) unordered set which implements collection andseqable:a ;=> {2 1 3}(empty a) ;=> {}(empty-p a) ;=> nil(empty-p (empty a)) ;=> t(seq a) ; => (3 2 1) or similar(seq (empty a)) ;=> nil

4.3seq

requires collection, seqableThis protocol provides a list-like abstraction withthe methods head and tail.

4.4associative

requires collectionThis protocol provides a dictionary-like abstraction with themethods all-keys, all-values, contains-key-p, andvalue-for-key.

4.5countable

requires collectionA collection that may be counted.counted-p -> bool, whether count-elements is o(1)count-elements -> number

4.6indexable

requires collection, countableThis protocol provides a vector-like abstractionwith the method element-at

4.7reduceable

a thing which can reduce itself via coll-reduceused to implement clojure-style reducers.

4.8foldable

a thing which can fold itself via coll-foldditto reducable, includes a parallel implementationfor common lisp vectors.

5additional functions

5.1additional associative functions

all-keys-and-valuesgetkey

5.2fold-left, fold

6exported symbols

See package.lisp for a list of all exported symbols.

For in depth information each protocol and their associated symbols, visit the links to the individual protocol systems above.

The file builtins.lisp contains the protocol implementations for many built-in common lisp types.

7notes & todos

the file test.lisp defines some data structures, each implementing one of the three major protocols & confirms that they translate among each other correctly.

7.1TODOfix hash-table weakness

(empty h-t) not yet aware of hash table weakness

7.2TODOwrite examples/demo, more docs

better to factor them out among thesub-packages