A fast, purely functional data structure library

sycamore

SYCAMORE
========

A fast, purely functional data structure library in Common Lisp.

API Documentation: http://ndantam.github.io/sycamore

Features
========
* Fast, purely functional weight-balanced binary trees.
  - http://en.wikipedia.org/wiki/Weight-balanced_tree
  - Leaf nodes are simple-vectors, greatly reducing tree height.
* Interfaces for tree Sets and Maps (dictionaries).
* Ropes
  - http://en.wikipedia.org/wiki/Rope_(data_structure)
* Purely functional pairing heaps
  - http://en.wikipedia.org/wiki/Pairing_heap
* Purely functional amortized queue

Installation
============

* Sycamore uses ASDF (https://common-lisp.net/project/asdf/)
* See `INSTALL` file for details

Examples
========

See also `./example.lisp`

Sets
----

Define an ordering function:

    CL-USER> (defun compare (a b)
               (cond ((< a b) -1)
                     ((> a b) 1)
                     (t 0)))

    COMPARE

Create a set for integers:

    CL-USER> (sycamore:tree-set #'compare 1 2 -10 40)

    #<TREE-SET (-10 1 2 40)>

Insertion:

    CL-USER> (sycamore:tree-set-insert (sycamore:tree-set #'compare 1 2)
                                       0)
    #<TREE-SET (0 1 2)>

Removal:

    CL-USER> (sycamore:tree-set-remove (sycamore:tree-set #'compare 1 2 0)
                                       0)
    #<TREE-SET (1 2)>

Union operation:

    CL-USER> (sycamore:tree-set-union (sycamore:tree-set #'compare 1 2)
                                      (sycamore:tree-set #'compare 1 0 3))

    #<TREE-SET (0 1 2 3)>

Intersection operation:

    CL-USER> (sycamore:tree-set-intersection (sycamore:tree-set #'compare 1 2)
                                             (sycamore:tree-set #'compare 1 0 3))

    #<TREE-SET (1)>

Difference operation:

    CL-USER> (sycamore:tree-set-difference (sycamore:tree-set #'compare 1 2)
                                           (sycamore:tree-set #'compare 1 0 3))

    #<TREE-SET (2)>

Map set:

    CL-USER> (sycamore:map-tree-set 'list #'1+
                                    (sycamore:tree-set #'compare 1 0 10 2))

    (1 2 3 11)

Fold set:

    CL-USER> (sycamore:fold-tree-set (lambda (list item) (cons item list))
                                     nil
                                     (sycamore:tree-set #'compare 1 0 10 2))

    (10 2 1 0)

Ropes
-----

Create a Rope:

    CL-USER> (sycamore:rope "Hello" #\Space 'World!)

    #<ROPE "Hello WORLD!">

Also works on lists:

    CL-USER> (sycamore:rope (list "Hello" #\Space 'World!))

    #<ROPE "Hello WORLD!">

And arrays:

    CL-USER> (sycamore:rope (vector "Hello" #\Space 'World!))

    #<ROPE "Hello WORLD!">

Rope to string:

    CL-USER> (sycamore:rope-string (sycamore:rope "Hello" #\Space 'World!))

    "Hello WORLD!"

Print a rope:

    CL-USER> (sycamore:rope-write (sycamore:rope "Hello" #\Space 'World!)
                                  :escape nil :stream *standard-output*)

    Hello WORLD!

Alternatives
============

There are many other Common Lisp data structure libraries.  Here are a
few alternatives and their trade-offs relative to Sycamore.

FSet
----
https://common-lisp.net/project/fset/Site/FSet-CL.html

FSet implements finite sets with a CLOS-based set interface, while
Sycamore's finite sets take a parameter for a comparison function.
Both used weight-balanced trees with minor algorithmic differences.
Generic vs. explicit comparison functions is both an aesthetic and
performance issue.  FSet's generic comparison functions do not need to
be passed explicitly, while Sycamore's explicit comparison function
parameter makes it easier to compare the same type differently if
needed, e.g., lexicographic vs. fast string comparison.

Included benchmarks show that Sycamore is 30-50% faster than FSet.

CL-Containers
-------------
https://github.com/gwkkwg/cl-containers

CL-Containers is stateful/mutable/imperative, while Sycamore is
purely-functional/persistent.

Lisp Interface Library (LIL)
----------------------------
https://github.com/fare/lisp-interface-library

Lisp Interface Library (LIL) provides abstracted data structures using
Interface Passing Style, while Sycamore provides a few concrete data
structures. LIL's Interface Passing Style presumably improves
flexibility at the cost of runtime overhead and API complexity.
Sycamore's explicit data structures have low-overhead, optimized
implementations and a simple, documented API.


References
==========

* Okasaki, Chris. "Purely Functional Data Structures." Cambridge
  University Press. June 1999. ISBN: 978-0521663502.

* Boehm, H.J., Atkinson, R. and Plass, M., 1995. Ropes: an alternative
  to strings. Software: Practice and Experience, 25(12), pp.1315-1330.

* Adams, Stephen., 1992. Implementing sets efficiently in a functional
  language. University of Southampton. Tech Report CSTR 92-10.


Name
====
http://en.wikipedia.org/wiki/Platanus_occidentalis


alexandria

cl-ppcre

Sycamore is a purely functional data structure library in Common
Lisp.  It include fast, weight-balanced binary trees, set and
map (dictionary) interfaces, pairing heaps, and amortized queues.

sycamore

Upstream URL

Author

License

sycamore

Version:

License:

Authors:

Dependencies:

Weakly Dependencies:

Dependencies (4)

Dependents (1)