palatable / shoki Goto Github PK

Computing the size and the hash code adds significant constant overhead for methods like StrictStack#cons, whereas if the size and hash code were computations that could be memoized, they would be amortized O(1) and have a negligible time cost on these hot path operations.

• StrictStack (e24c679)
• StrictQueue (4fee23b)
• HashMap (f47a9be)
• HashSet (f47a9be)
• HashMultiSet (0ae7fbd)

Dependent on Diet (#9)

Currently both StrictStack and StrictQueue use an amortized O(1) time cost and O(1) space cost for their sizes. If StrictStack could gain an O(1) time/space complexity, and if StrictQueue delegated to StrictStack, it would achieve the same complexity. This should be doable with a single additional wrapper node in StrictStack that was carried the size along with the spine.

min/max heaps seem like a reasonable next addition. Okasaki's binomial heap should translate nicely.

Since shoki data structures are immutable, this should type-check:

interface Animal {}
class Dog implements Animal {}
class Cat implements Animal {}

StrictStack<Animal> animals = Shoki.strictStack(StrictStack.<Dog>strictStack());

...and perform no additional allocations.

union, difference, intersection, etc. for MultiSet. Depends on #16.

An array-backed immutable sequence would natively support random access Natural -> Maybe a and would be very fast indeed, provided it could be made safe such that the array was fully encapsulated by the data type. This would mean that no public construction patterns should allow wrapping of an array: arrays should be fully existentialized behind a series of exported minimal interactions. As an example:

public static Vector<A> create(Consumer<Consumer<A>> withAdd) {
    // ...
}

This interface would receive a Consumer that would itself receive a Consumer representing an add invocation, so a valid argument might do something like:

Vector<Integer> ints = create(add -> {
    add.accept(1);
    add.accept(2);
    add.accept(3);
});

Each add would result in the internal array being updated, and after withAdd was finished, some flag would be flipped to specify the array is no longer candidate for update, so if someone did something accidental and caustic, like leaked add into an atomic reference, add could not be used after initialization to violate the immutable properties of the Vector.

This data type would likely be eventually supplanted by a BAMT, so it may or may not be worth adding in the short term.

Add a changelog

LazyLists, lists with lazy, memoized tail's, are generally useful and specifically useful as the backbone for RTDs.

If MultiSet can subtype Map, life gets better.

Add a SortedMap interface with a canonical TreeMap implementation backed by a red/black tree

Once ImmutableStack is done, obviously.

Similarly to EquivalenceRelations patterns, and reuse them across types.

SortedCollections should offer slice methods that rely on poset inequalities (e.g. java.util.NavigableMap#headMap/tailMap)

Maybe as a separate library, but they're needed

• HashMap
• HashSet
• HashMultiSet
• StrictStack
• StrictQueue

StrictStack#sizeInfo, for example, calls abs(size(this)); size returns long. This has to use an adder that auto-widens the numeric type; probably BigInteger to be safe.