Skip to content

ericgoffster/collections

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 

Repository files navigation

This is a targeted java library aimed at immutable collections.
It is released under the "granite guarantee".

This code is licensed under Mozilla Public License Version 2.0.

A java library for the implementation and manipulation of immutable collections.

What is immutability?

Immutability is the foundation of functional programming.

A pure function is side-effect free.   Arguments and internal state
remain unchanged.   Side effects are a major source of bugs.

Immutable objects can be shared.   Thiscan* help with memory considerations.

Immutable objects are concurrent.   You pay no performance cost whatsoever
in sharing an object across many threads.

I will focus on one particular example to illustrate:

ImmList l1 = ImmCollections.asList(1, 2, 3, 4, 5);
ImmList l2 = ImmCollections.asList(6, 7, 8, 9, 10);
ImmList l3 = l1.insertListAt(3, l2);
   
At this point:
l1 == [1, 2, 3, 4, 5]
l2 == [6, 7, 8, 9, 10]
l3 == [1, 2, 3, 6, 7, 8, 9, 10, 4, 5]

Because of clever structure sharing, the insertListAt operation was also
fairly fast, even if the size of l1 or l2 o both were very large.
The insertListAt operation is O(log |l1|) + O(log |l2|).

There is no need at all for list "builders" as you might find in other immutable libraries such as guava.

Because all of these list operations are performant, we can implement things like immutable sets and maps
that use this immutable list.  These sets and maps are frequently fairly trivial.

Pros:
    Fast repeated operations that are normal not fast, insertAt, removeAt, exclude, replace, reverse
    Fast conversion to java collections
    Granite guarantee:
            Compact library
            No breaking changes
            No reliance on third party libraries that do not have the granite guaranteed
        
Cons:
    The space required to implement a list is O(n log n), not O(n)
    ImmList.get(i)  is O(log n), not O(1)

About

Targeted library aimed only at java collections - based on the granite guarantee

Resources

Stars

Watchers

Forks

Packages

No packages published

Languages