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