OLD OLD OLD OLD OLD rewrite in progress

Home — Manual — Issues

Accretions is a collection of data structures that aren’t present in standard Common Lisp. Of course, we already have lists, and most CL implementations have performant hash tables, yet there remain other data structures essential to certain applications that are missing from the standard. Accretions is my collection of good (or, at least useful) implementations of them. If I’ve needed it more than once, and the code is good enough, here is where it winds up. ^[1]

Accretions would not exist without the essential work of Donald Knuth, Robert Sedgewick, Jon Bentley, Doug Hoyte, and others.

Certainly, Accretions isn’t alone in its implementations. With the slightly possible exception of ternary search trees, everything in here must already exist, scattered somewhere on the web. ^[2] Performance isn’t always discussed, however, and it’s never clear how tight or loose the code is. Here in Accretions, each algorithm or container comes with at least some analysis of how well it’s likely to perform in practice. It hopes to be a little faster, maybe a little more efficient, and maybe a little more consistent than other implementations out there.

Strictly speaking?

Nothing. Individual lisp files can be compiled or evaluated as you need. Accretions is written to the Common Lisp specification, and relies on no external systems or packages in its source.

Loosely speaking?

If you want to use the asd system definitions that come with Accretions (of course you do), you’ll need ASDF 3.1.2 or later (along with associated systems like UIOP). This should be no problem, every major lisp environment is already including even later versions ASDF, and has been for years.

Very loosely speaking?

If you want to run the tests that are packaged in Accretions, then you’ll need the FiveAM test framework. It’s available via Quicklisp, so if you have that, FiveAM is but a quickload away.

Bags

Also known as Multisets, these are simple unordered collections of items.

Ternary Search Trees

A really nice collection filling the space somewhere between hash tables and tries; great for dictionaries! The Accretions implementation allows for any key sequence, not just strings. It provides the functionality of a trie without the unfortunate space overhead. ^[3]

Red-Black Trees

Notes on 2-3 and red-black go here.

Hash Tables

The Common Lisp standard is built around an implementation-provided sxhash function that cannot be replaced ^[4] and a hash space built around it using fixnums and lists. Accretions offers a hash table implementation that allows for updating hash algorithms, evaluating alternate algorithms (e.g., Murmur, CityHash, FarmHash) as well as functions provided by the client.

Quicklisp

I’ll submit this for distribution via Quicklisp once I feel it’s good enough.

More Containers

Or more algorithms? Feel free to suggest something!

I’ve experimented with functional data structures (as described by Osazaki) and it’s true, they have very promising characteristics in persistence and safety. I really like them for that. However, their overhead in space (albiet temporary) can be prohibitive for larger applications, and so I’ll revisit this another time if I can. Especially, I encountered some very interesting approaches, including treating data as streams instead of contiguous blobs of memory that really bear further investigation.

Okay, so go hit the Manual!

Accretions is available under the MIT Open Source License.

Copyright © 2018, 2019 Robert S. Krzaczek

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

The software is provided “as is”, without warranty of any kind, express or implied, including but not limited to the warranties of merchantability, fitness for a particular purpose and noninfringement. In no event shall the authors or copyright holders be liable for any claim, damages or other liability, whether in an action of contract, tort or otherwise, arising from, out of or in connection with the software or the use or other dealings in the software.