rushabh-v/FunctionalCollections.jl

Functional and persistent data structures for Julia

FunctionalCollections

Functional and persistent data structures for Julia. This is a work in progress and is currently not optimized for performance.

NOTE: The master branch of FunctionalCollections is for Julia v0.7 and up. For earlier Julia versions please use FunctionalCollections v0.3.x.

Installation

julia> Pkg.add("FunctionalCollections")

julia> using FunctionalCollections

Exports

Collection         | Abbrev
----------------------------
PersistentVector   | pvec
PersistentHashMap  | phmap
PersistentArrayMap |
PersistentSet      | pset
PersistentList     | plist
PersistentQueue    | pqueue

src/FunctionalCollections.jl contains all of the package's exports, though many built-ins are also implemented.

PersistentVector

Persistent vectors are immutable, sequential, random-access data structures, with performance characteristics similar to arrays.

julia> v = @Persistent [1, 2, 3, 4, 5]
Persistent{Int64}[1, 2, 3, 4, 5]

Since persistent vectors are immutable, "changing" operations return a new vector instead of modifying the original.

julia> append(v, [6, 7])
Persistent{Int64}[1, 2, 3, 4, 5, 6, 7]

# v hasn't changed
julia> v
Persistent{Int64}[1, 2, 3, 4, 5]

Persistent vectors are random-access structures, and can be indexed into just like arrays.

julia> v[3]
3

But since they're immutable, it doesn't make sense to define index assignment (v[3] = 42) since assignment implies change. Instead, assoc returns a new persistent vector with some value associated with a given index.

julia> assoc(v, 3, 42)
Persistent{Int64}[1, 2, 42, 4, 5]

Three functions, push, peek, and pop, make up the persistent vector stack interface. push adds a single element (whereas append adds all elements in the given collection, starting from the left), peek returns the last element of the vector, and pop returns a new vector without the last element.

julia> push(v, 6)
Persistent{Int64}[1, 2, 3, 4, 5, 6]

julia> peek(v)
5

julia> pop(v)
Persistent{Int64}[1, 2, 3, 4]

Persistent vectors also support iteration and higher-order sequence operations.

julia> for el in @Persistent ["foo", "bar", "baz"]
           println(el)
       end
foo
bar
baz

julia> map(x -> x * 2, v)
Persistent{Int64}[2, 4, 6, 8, 10]

julia> filter(iseven, v)
Persistent{Int64}[2, 4]

PersistentHashMap

Persistent hash maps are immutable, unordered, associative structures, similar to the built-in Dict type.

julia> name = @Persistent Dict(:first => "Zach", :last => "Allaun")
Persistent{Symbol, String}[last => Allaun, first => Zach]

They can be queried in a manner similar to the dictionaries.

julia> name[:first]
"Zach"

julia> get(name, :middle, "")
""

With persistent vectors, assoc is used to associate a value with an index; with persistent hash maps, you use it to associate a value with an arbitrary key. To dissociate a key/value pair, use dissoc.

julia> fullname = assoc(name, :middle, "Randall")
Persistent{Symbol, String}[last => Allaun, first => Zach, middle => Randall]

julia> dissoc(fullname, :middle)
Persistent{Symbol, String}[last => Allaun, first => Zach]

Base.map is defined for persistent hash maps. The function argument should expect a (key, value) tuple and return a (key, value) tuple. This function will be applied to each key-value pair of the hash map to construct a new one.

julia> mapkeys(f, m::PersistentHashMap) =
	       map(kv -> (f(kv[1]), kv[2]), m)

julia> mapkeys(string, fullname)
Persistent{String, String}[last => Allaun, middle => Randall, first => Zach]

PersistentArrayMap

PersistentArrayMaps are immutable dictionaries implemented as Arrays of key-value pairs. This means that the time complexity of most operations on them is O(n). They can be quickly created, though, and useful at small sizes.

julia> m = PersistentArrayMap((1, "one"))
Persistent{Int64, String}Pair{Int64,String}[1=>"one"]

julia> m2 = assoc(m, 2, "two")
Persistent{Int64, String}Pair{Int64,String}[1=>"one", 2=>"two"]

julia> m == m2
false

julia> dissoc(m2, 2)
Persistent{Int64, String}Pair{Int64,String}[1 => one]

julia> m == dissoc(m2, 2)
true

PersistentSet

PersistentSets are immutable sets. Along with the usual set interface, conj(s::PersistentSet, val) returns a set with an element added (conjoined), and disj(s::PersistentSet, val returns a set with an element removed (disjoined).

TODO:

General

• Ints vs Uints w.r.t. bitwise operations
• children instead of arrayof
• standardize "short-fn" interfaces:
• lastchild instead of arrayof(node)[end]
• peek should become pop, pop should become butlast
• What is Base doing for Arrays w.r.t. boundscheck!, can we drop boundcheck for iteration

# currently
pvec([1,2,3,4,5])
pset(1,2,3,4,5)

# should be
pvec(1,2,3,4,5)
pset(1,2,3,4,5)

• @Persistent macro sugar for hi-jacking built-in syntax:

@Persistent Dict("foo" => 1, "bar" => 2, "baz" => 3)
# creates a phmap

@Persistent [1, 2, 3, 4, 5]
# creates a pvec

PersistentQueue

• queue => pqueue

BitmappedTrie

• comment mask to indicate index-from-1 assumption

PersistentVector

• constant time rest by adding an initial index offset
• quick slicing with initial offset and structure deletion
• pvec mask should take the pvec even though it doesn't use it
• move extra pvec constructor to the type definition

PersistentHashMap

• the repr of values should be printed, not the string
• printing breaks after dissocing