com.clearly-useful.generic-collection-interface

2012-11-25

overview

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.

justification

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.

design

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.

protocol overview

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

=collection=

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

=seqable=

A thing which may be converted to a seq. This protocol defines the method seq which serves a bit of a double duty: it may be used to create a list-like object from another, but should always return nil when it's result is empty. For example, given a (hypothetical) unordered set which implements collection and seqable: #beginsrc lisp 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 #endsrc

=seq=

requires collection, seqable This protocol provides a list-like abstraction with the methods head and tail.

=associative=

requires collection This protocol provides a dictionary-like abstraction with the methods all-keys, all-values, contains-key-p, and value-for-key.

=countable=

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

=indexable=

requires collection, countable This protocol provides a vector-like abstraction with the method element-at

=reduceable=

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

=foldable=

a thing which can fold itself via coll-fold ditto reducable, includes a parallel implementation for common lisp vectors.

additional functions

additional associative functions

all-keys-and-values getkey

fold-left, fold

exported 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.

notes & 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.

TODO fix hash-table weakness

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

TODO write examples/demo, more docs

better to factor them out among the sub-packages

Author
Jason Aeschliman <j.aeschliman@gmail.com>
License
revised BSD