Subscribe Free

Join 2670+ others. No spamming.
I promise!

We are currently under high development. Follow us at github.

Looking for Python Tutorials?
Check these awesome tutorials



JuliaCollections / FunctionalCollections.jl


Functional and persistent data structures for Julia



Build Status FunctionalCollections

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


julia> Pkg.add("FunctionalCollections")

julia> using FunctionalCollections


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.


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]

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)

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"]

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

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


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, ASCIIString}[:last => "Allaun", :first => "Zach"]

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

julia> name[:first]

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, ASCIIString}[:last => "Allaun", :first => "Zach", :middle => "Randall"]

julia> dissoc(fullname, :middle)
Persistent{Symbol, ASCIIString}[:last => "Allaun", :first => "Zach"] 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{ASCIIString, ASCIIString}["last" => "Allaun", "first" => "Zach", "middle" => "Randall"]


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> using PersistentDataStructures

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

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

julia> m == m2

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

julia> m == dissoc(m2, 2)


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).



  • 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

# should be
  • @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


  • queue => pqueue


  • comment mask to indicate index-from-1 assumption


  • 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


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