Strategies for nested data in Julia

SplitApplyCombine.jl provides high-level, generic tools for manipulating data - particularly focussing on data in nested containers. An emphasis is placed on ensuring split-apply-combine strategies are easy to apply, and work reliably for arbitrary iterables and in an optimized way with the data structures included in Julia's standard library.

The tools come in the form of high-level functions that operate on iterable or indexable containers in an intuitive and simple way, extending Julia's in-built map, reduce and filter commands to a wider range of operations. Just like these Base functions, the functions here like invert, group and innerjoin are able to be overloaded and optimized by users and the maintainers of other packages for their own, custom data containers.

One side goal is to provide sufficient functionality to satisfy the need to manipulate "relational" data (meaning tables and dataframes) with basic in-built Julia data containers like Vectors of NamedTuples and higher-level functions in a "standard" Julia style. Pay particular to the invert family of functions, which effectively allows you to switch between a "struct-of-arrays" and an "array-of-structs" interpretation of your data. I am exploring the idea of using arrays of named tuples for a fast table package in another package under development called MinimumViableTables), which adds acceleration indexes but otherwise attempts to use a generic "native Julia" interface.

You can install the package by typing Pkg.add("SplitApplyCombine") at the REPL.

Below are some simple examples of how a select subset of the tools can be used to split, manipulate, and combine data. A complete API reference is included at the end of this README.

julia> using SplitApplyCombine

julia> only([3]) # return the one-and-only element of the input (included in Julia 1.4)
3

julia> splitdims([1 2 3; 4 5 6]) # create nested arrays
3-element Array{Array{Int64,1},1}:
 [1, 4]
 [2, 5]
 [3, 6]

julia> combinedims([[1, 4], [2, 5], [3, 6]]) # flatten nested arrays
2×3 Array{Int64,2}:
 1  2  3
 4  5  6

 julia> invert([[1,2,3],[4,5,6]]) # invert the order of nesting
3-element Array{Array{Int64,1},1}:
 [1, 4]
 [2, 5]
 [3, 6]

julia> group(iseven, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) # split elements into groups
2-element Dictionary{Bool,Array{Int64,1}}
 false │ [1, 3, 5, 7, 9]
  true │ [2, 4, 6, 8, 10]

julia> groupreduce(iseven, +, 1:10) # like above, but performing reduction
2-element Dictionary{Bool,Int64}
 false │ 25
  true │ 30

julia> innerjoin(iseven, iseven, tuple, [1,2,3,4], [0,1,2]) # combine two datasets - related to SQL `inner join`
6-element Array{Tuple{Int64,Int64},1}:
 (1, 1)
 (2, 0)
 (2, 2)
 (3, 1)
 (4, 0)
 (4, 2)

julia> leftgroupjoin(iseven, iseven, tuple, [1,2,3,4], [0,1,2]) # efficient groupings from two datasets
Dict{Bool,Array{Tuple{Int64,Int64},1}} with 2 entries:
  false => Tuple{Int64,Int64}[(1, 1), (3, 1)]
  true  => Tuple{Int64,Int64}[(2, 0), (2, 2), (4, 0), (4, 2)]

The primary interface for manipulating tabular data is the relational algebra. A relation is typically defined as an (unordered) collection of (unique) (named) tuples. If relations are collections of rows, and tables are to be viewed as relations, then I suggest that tables should be viewed as collections of rows (and in particular they should iterate rows and return an entire row from getindex, if defined).

While simple, this already allows quite a bit of relational algebra to occur. One can then filter rows of a table, map rows of a table (to project, rename or create columns), and use zip and product iterables for more complex operations. The goal below will be to discuss functions which work well for general iterables and will be useful for a table that iterates rows. As a prototype to keep in mind for this work, I consider an AbstractVector{<:NamedTuple} to be a good model of (strongly-typed) a table/dataframe. Specialized packages may provide convenient macro-based DSLs, a greater range of functions, and implementations that focus on things such as out-of-core or distributed computing, more flexible acceleration indexing, etc. Here I'm only considering the basic, bare-bones API that may be extended and built upon by other packages.

This package recently switched from using the dictionaries in Base to those in the Dictionaries.jl package, particularly for the group family of functions.

The package currently implements and exports only, splitdims, splitdimsview, combinedims, combinedimsview, mapview, filterview, mapmany, flatten, group, groupinds, groupview, groupreduce, innerjoin and leftgroupjoin, as well as the @_ macro. Expect this list to grow.

Returns the single, one-and-only element of the collection iter. If it contains zero elements or more than one element, an error is thrown.

julia> only([3])
3

julia> only([])
ERROR: ArgumentError: Collection must have exactly one element (input was empty)
Stacktrace:
 [1] only(::Array{Any,1}) at /home/ferris/.julia/v0.7/SAC/src/only.jl:4

julia> single([3, 10])
ERROR: ArgumentError: Collection must have exactly one element (input contained more than one element)
Stacktrace:
 [1] only(::Array{Int64,1}) at /home/ferris/.julia/v0.7/SAC/src/only.jl:10

Split a multidimensional array into nested arrays of arrays, splitting the specified dimensions dims to the "outer" array, leaving the remaining dimension in the "inner" array. By default, the last dimension is split into the outer array.

julia> splitdims([1 2; 3 4])
2-element Array{Array{Int64,1},1}:
 [1, 3]
 [2, 4]

julia> splitdims([1 2; 3 4], 1)
2-element Array{Array{Int64,1},1}:
 [1, 2]
 [3, 4]

Like splitdimsview(array, dims) except creating a lazy view of the nested struture.

The inverse operation of splitdims - this will take a nested array of arrays, where each sub-array has the same dimensions, and combine them into a single, flattened array.

julia> combinedims([[1, 2], [3, 4]])
2×2 Array{Int64,2}:
 1  3
 2  4

Like combinedims(array) except creating a lazy view of the flattened struture.

Take a nested container a and return a container where the nesting is reversed, such that invert(a)[i][j] === a[j][i].

Currently implemented for combinations of AbstractArray, Tuple and NamedTuple. It is planned to add AbstractDict in the future.

julia> invert([[1,2,3],[4,5,6]]) # invert the order of nesting
3-element Array{Array{Int64,1},1}:
 [1, 4]
 [2, 5]
 [3, 6]

julia> invert((a = [1, 2, 3], b = [2.0, 4.0, 6.0])) # Works between different data types
3-element Array{NamedTuple{(:a, :b),Tuple{Int64,Float64}},1}:
 (a = 1, b = 2.0)
 (a = 2, b = 4.0)
 (a = 3, b = 6.0)

A mutating version of invert, which stores the result in out.

Like map, but presents a view of the data contained in iter. The result may be wrapped in an lazily-computed output container (generally attempting to preserve arrays as AbstractArray, and so-on).

For immutable collections (like Tuple and NamedTuple), the operation may be performed eagerly.

julia> a = [1,2,3];

julia> b = mapview(iseven, a)
3-element MappedArray{Bool,1,typeof(iseven),Array{Int64,1}}:
 false
  true
 false

julia> a[1] = 2;

julia> b
3-element MappedArray{Bool,1,typeof(iseven),Array{Int64,1}}:
  true
  true
 false

Like filter, but presents a view of the data contained in arr. Data in arr is not copied, and modifications to the resulting view are propagated to the original array.

julia> a = [1, 2, 3];

julia> b = filterview(isodd, a)
2-element view(::Vector{Int64}, [1, 3]) with eltype Int64:
 1
 3

julia> b[2] = 10;

julia> a
3-element Vector{Int64}:
  1
  2
 10

julia> b
2-element view(::Vector{Int64}, [1, 3]) with eltype Int64:
  1
 10

Like map, but f(x...) for each x ∈ zip(iters...) may return an arbitrary number of values to insert into the output.

julia> mapmany(x -> 1:x, [1,2,3])
6-element Array{Int64,1}:
 1
 1
 2
 1
 2
 3

(Note that, semantically, filter could be thought of as a special case of mapmany.)

Takes a collection of collections a and returns a collection containing all the elements of the subcollecitons of a. Equivalent to mapmany(identity, a).

julia> flatten([1:1, 1:2, 1:3])
6-element Array{Int64,1}:
 1
 1
 2
 1
 2
 3

Takes the Cartesian outer product of two containers and evaluates f on all pairings of elements.

For example, if a and b are vectors, this returns a matrix out such that out[i,j] = f(a[i], b[j]) for i in keys(a) and j in keys(b).

Note this interface differs slightly from Iterators.product where f = tuple is assumed.

julia> product(+, [1,2], [1,2,3])
2×3 Array{Int64,2}:
 2  3  4
 3  4  5

Like product, but return a view of the Cartesian product of a and b where the output elements are f evaluated with the corresponding of a and b.

julia> productview(+, [1,2], [1,2,3])
2×3 ProductArray{Int64,2,typeof(+),Array{Int64,1},Array{Int64,1}}:
 2  3  4
 3  4  5

These operations help you split the elements of a collection according to an arbitrary function which maps each element to a group key.

Group the elements x of the iterable iter into groups labeled by by(x), transforming each element . The default implementation creates a Dictionaries.Dictionary of Vectors, but of course a table/dataframe package might extend this to return a suitable (nested) structure of tables/dataframes.

Also a group(by, f, iters...) method exists for the case where multiple iterables of the same length are provided.

julia> group(iseven, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
2-element Dictionary{Bool,Array{Int64,1}}
 false │ [1, 3, 5, 7, 9]
  true │ [2, 4, 6, 8, 10]

julia> names = ["Andrew Smith", "John Smith", "Alice Baker", "Robert Baker",
                "Jane Smith", "Jason Bourne"]
6-element Array{String,1}:
 "Andrew Smith"
 "John Smith"
 "Alice Baker"
 "Robert Baker"
 "Jane Smith"
 "Jason Bourne"

julia> group(last, first, split.(names))
3-element Dictionary{SubString{String},Array{SubString{String},1}}
  "Smith" │ SubString{String}["Andrew", "John", "Jane"]
  "Baker" │ SubString{String}["Alice", "Robert"]
 "Bourne" │ SubString{String}["Jason"]

For indexable collections container, returns the indices/keys associated with each group.

NOTE: Recently renamed from groupinds.

julia> groupfind(iseven, [3,4,2,6,5,8])
2-element Dictionary{Bool,Array{Int64,1}}
 false │ [1, 5]
  true │ [2, 3, 4, 6]

Similar to group(by, iter) but the grouped elements are a view of the original collection. Uses groupinds to construct the appropriate container.

julia> v = [3,4,2,6,5,8]
6-element Array{Int64,1}:
 3
 4
 2
 6
 5
 8

julia> groups = groupview(iseven, v)
2-element GroupDictionary{Bool,SubArray{Int64,1,Array{Int64,1},Tuple{Array{Int64,1}},false},Array{Int64,1},Dictionary{Bool,Array{Int64,1}}}
 false │ [3, 5]
  true │ [4, 2, 6, 8]

julia> groups[false][:] .= 99
2-element view(::Array{Int64,1}, [1, 5]) with eltype Int64:
 99
 99

julia> v
6-element Array{Int64,1}:
 99
  4
  2
  6
 99
  8

Applies a mapreduce-like operation on the groupings labeled by passing the elements of iter through by. Mostly equivalent to map(g -> reduce(op, g; init=init), group(by, f, iter)), but designed to be more efficient. If multiple collections (of the same length) are provided, the transformations by and f occur elementwise.

We also export groupcount, groupsum and groupprod as special cases of the above, to determine the number of elements per group, their sum, and their product, respectively.

julia> groupreduce(iseven, +, 1:10)
Dictionary{Bool,Int64} with 2 entries:
  false │ 25
  true  │ 30

julia> groupcount(iseven, 1:10)
Dictionary{Bool,Int64} with 2 entries:
  false │ 5
  true  │ 5

Performs a relational-style join operation between iterables left and right, returning a collection of elements f(l, r) for which comparison(lkey(l), rkey(r)) is true where l ∈ left, r ∈ right.

julia> innerjoin(iseven, iseven, tuple, ==, [1,2,3,4], [0,1,2])
6-element Array{Tuple{Int64,Int64},1}:
 (1, 1)
 (2, 0)
 (2, 2)
 (3, 1)
 (4, 0)
 (4, 2)

Creates a collection if groups labelled by lkey(l) where each group contains elements f(l, r) which satisfy comparison(lkey(l), rkey(r)). If there are no matches, the group is still created (with an empty collection).

This operation shares similarities with an SQL left outer join, but is more similar to LINQ's GroupJoin.

julia> leftgroupjoin(iseven, iseven, tuple, ==, [1,2,3,4], [0,1,2])
Dictionary{Bool,Array{Tuple{Int64,Int64},1}} with 2 entries:
  false │ Tuple{Int64,Int64}[(1, 1), (3, 1)]
  true  │ Tuple{Int64,Int64}[(2, 0), (2, 2), (4, 0), (4, 2)]