ndantam/sycamore

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

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

sycamore's Issues

Unit tests and Quicklisp

Hey!

Do you have any kind of unit tests written for this?

If yes, then did you consider making an issue on https://github.com/quicklisp/quicklisp-projects/ to get this added to Quicklisp?

~phoe

Key cannot be found after insertion even though comparer returns 0

I'm converting from fset to sycamore because I need the performance, but I'm hitting a problem which might look related to sycamore.

To find the problem, I try to look up every value I insert after inserting it. I then fetch the comparer and checks that it returns 0 as they are equal to avoid a false positive where the equal function is wrong. The key is a cons of a fixnum and a clim:standard-point, e.g. (0 . #<CLIM:STANDARD-POINT 0 7>), but I've seen it for other things where the keys are lists of plain symbols too.

The code below prints (0 . #<STANDARD-POINT 0 7>) not found, but comparer says 0

I write here before investigating further in case I've misunderstood something obvious.

(defun with (map key value)
  (let ((result (sycamore:tree-map-insert map key value)))
    (test-map result)
    result))

(defun test-map (map)
  (declare (optimize (debug 3)))
  (dolist (key (sycamore:tree-map-keys map) map)
    (unless (sycamore:tree-map-contains map key)
      (let* ((comparer (sycamore::tree-map-compare map))
             (comp (funcall comparer (cons (copy key) 'foo) (cons (copy key) 'bar))))
        (format t "~A not found, but comparer says ~A~%" key comp)
        (break)))))

EDIT: This is using SBCL 2.3.7 on Linux 6.6.6.
EDIT2: The value is added and visible when I inspect the map.