Shōki (正気)

Purely functional, persistent data structures for the JVM.

Table of Contents

• Background
• Installation
• Hierarchy
• Implementations
  • StrictStack<A>
  • StrictQueue<A>
  • HashMap<K, V>
  • HashSet<A>
  • HashMultiSet<A>
  • TreeMap<K, V>
  • TreeSet<A>
  • TreeMultiSet<A>
• License

<a name="background">Background</a>

Shōki is a library offering purely functional, persistent data structures for the JVM.

So why another data structures library? Because writing correct code is hard, and it's especially hard if your data structures consistently advertise false interfaces. The data structures provided by Shōki are built on top of interfaces that promote type-checker participation by leveraging rich types, and encourage correct-by-construction software with obvious usage semantics.

Standard usage of Shōki interfaces should never throw: there are no IndexOutOfBoundsExceptions that result from seemingly innocuous get calls; no UnsupportedOperationExceptions because the interface you're presented with is an absolute fiction, and somewhere under the covers is an immutable collection masquerading as a mutable one; no ClassCastExceptions because a data structure that fundamentally only works in the presence of comparability fails to enforce this essential constraint at compile time. Any of these things happening is considered an error in Shōki, not in user code.

The constraints of the inputs and the outputs are also richly specified via their type signatures. If a lookup cannot be guaranteed to yield a value, it will return a Maybe rather than null so the type-checker can remind you that you may not have received what you wanted. If a value fundamentally cannot be zero, it will very likely be represented by a type that does not even include a "zero" term, so you don't waste mental energy writing code to handle impossible scenarios. If the total size of a collection can logically exceed Integer.MAX_VALUE, its sizeInfo will advertise a type that can realistically represent its size instead of one that might represent a negative value due to overflow.

The target audience for Shōki considers these characteristics not to be fine luxuries, but rather basic quality-of-life essentials. If you think your time is too valuable to be spent staring at four methods with four identical type signatures, trying to remember whether peek or poll throws or returns null, or element or remove alters its underlying structure or doesn't; then you're in good company. Welcome!

<a name="installation">Installation</a>

Shōki alpha releases are currently available in Maven Central. These alpha releases are meant to be of high enough quality as to be reliable in a production environment, while still allowing significant API changes to occur before a 1.0 release.

Add the following dependency to your:

pom.xml (Maven):

<dependency>
    <groupId>com.jnape.palatable</groupId>
    <artifactId>shoki</artifactId>
    <version>1.0-alpha-2</version>
</dependency>

build.gradle (Gradle):

compile group: 'com.jnape.palatable', name: 'shoki', version: '1.0-alpha-2'

<a name="hierarchy">Hierarchy</a>

One of the core design tenants of Shōki's API is that a data structure is modeled as the incremental composition of its orthogonal capabilities and constraints.

Top-level orthogonal building blocks

• Sequence<A>: an Iterable<A> interface that offers the methods Maybe<A> head() and Sequence<A> tail()
• SizeInfo: a coproduct of Unknown or Known<N extends Number>, where Known<N> offers a method N getSize()
• Sizable: an interface that offers a method SizeInfo sizeInfo()
• Membership<A>: an interface that offers a membership test method boolean contains(A)
• RandomAccess<Index, V>: Membership<Index> with an additional lookup method V get(Index)
• Natural: a Number sum type of Zero or NonZero that never overflows and offers basic type-safe arithmetic

Refined data structure interfaces

• Collection<Size extends Number, A>: a Sequence<A> that supports SizeInfo yielding a Known<Size>
• OrderedCollection<Size extends Number, A>: a Collection<Size, A> that offers a reverse() method
• SortedCollection<Size extends Number, A, Ordering>: an OrderedCollection<Size, A> that offers Maybe<A> min(), Maybe<A> max, and SortedCollection<Size, A, Ordering> sort(Comparator<? super Ordering> comparator) methods
• Stack<Size extends Number, A>: an OrderedCollection<Size, A> with a method Stack<Size, A> cons(A) that adds an element to the top of the Stack<Size, A>
• Queue<Size extends Number, A>: an OrderedCollection<Size, A> with a method Queue<Size, A> snoc(A) that adds an element to the bottom of the Queue<Size, A>
• Set<Size extends Number, A>: a Collection<Size, A> that supports Membership<A>
• MultiSet<A>: a Collection<Natural, A> of Tuple2<A, Natural.NonZero> that supports RandomAccess<A, Natural>
• Map<Size extends Number, K, V>: a Collection<Size, Tuple2<K, V>> that supports RandomAccess<K, Maybe<V>>

Shōki is still very much in alpha development, so these specific interfaces are subject to change, but they should at least offer an intuition about the way in which the design is being approached.

<a name="implementations">Implementations</a>

<a name="implementations-StrictStack">StrictStack<A></a>

A StrictStack<A> is a strictly-evaluated Stack<Natural, A> that offers worst-case O(1) space/time for cons, head, and tail.

import com.jnape.palatable.lambda.adt.Maybe;
import com.jnape.palatable.shoki.impl.StrictStack;

import static com.jnape.palatable.shoki.impl.StrictStack.strictStack;

public class Example {

    public static void main(String[] args) {
        StrictStack<String> empty     = strictStack();
        boolean             _true     = empty.isEmpty();
        Maybe<String>       nothing   = empty.head();
        StrictStack<String> alsoEmpty = empty.tail();

        StrictStack<String> fooBarBaz = empty.cons("baz").cons("bar").cons("foo");
        boolean             _false    = fooBarBaz.isEmpty();
        Maybe<String>       justFoo   = fooBarBaz.head();

        StrictStack<String> barBaz  = fooBarBaz.tail();
        Maybe<String>       justBar = barBaz.head();

        StrictStack<String> baz     = barBaz.tail();
        Maybe<String>       justBaz = baz.head();

        StrictStack<String> bazBarFooBaz = baz.consAll(fooBarBaz);
        boolean             __true       = bazBarFooBaz.equals(strictStack("baz", "bar", "foo", "baz"));
    }
}

<a name="implementations-StrictQueue">StrictQueue<A></a>

A StrictQueue<A> is a strictly-evaluated Queue<Natural, A> and Stack<Natural, A> that offers worst-case O(1) space/time for cons, snoc, and head, and amortized O(1) for tail.

import com.jnape.palatable.lambda.adt.Maybe;
import com.jnape.palatable.shoki.impl.StrictQueue;

import static com.jnape.palatable.shoki.impl.StrictQueue.strictQueue;

public class Example {

    public static void main(String[] args) {
        StrictQueue<String> empty     = strictQueue();
        boolean             _true     = empty.isEmpty();
        Maybe<String>       nothing   = empty.head();
        StrictQueue<String> alsoEmpty = empty.tail();

        StrictQueue<String> fooBarBaz     = empty.snoc("foo").snoc("bar").snoc("baz");
        boolean             _false        = fooBarBaz.isEmpty();
        Maybe<String>       justFoo       = fooBarBaz.head();
        StrictQueue<String> alsoFooBarBaz = empty.cons("baz").cons("bar").cons("foo");

        StrictQueue<String> barBaz  = fooBarBaz.tail();
        Maybe<String>       justBar = barBaz.head();

        StrictQueue<String> baz     = barBaz.tail();
        Maybe<String>       justBaz = baz.head();

        StrictQueue<String> bazFooBarBaz = baz.snocAll(fooBarBaz);
        StrictQueue<String> bazBarFooBaz = baz.consAll(fooBarBaz);
        boolean             __true       = bazFooBarBaz.equals(strictQueue("baz", "foo", "bar", "baz"));
    }
}

<a name="implementations-HashMap">HashMap<K, V></a>

A HashMap<K, V> is an ideal hash tree implementation of a Map<Natural, K, V> that offers amortized O(1) space/time for get, put, remove, and contains, and supports custom EquivalenceRelation<K>s and HashingAlgorithm<K>s.

import com.jnape.palatable.lambda.adt.Maybe;
import com.jnape.palatable.lambda.adt.hlist.Tuple2;
import com.jnape.palatable.shoki.impl.HashMap;
import com.jnape.palatable.shoki.impl.HashSet;
import com.jnape.