Two kinds of combinator
The whole cost model hangs off the split between the flavours. The
structural combinators (++ concatenates, :+ appends
one element, plus take, reverse, slice) change the shape: each builds a lazy node in O(1)
and copies nothing. The elementwise combinators (map,
filter, fold, anything that takes a lambda) run it over every element,
eagerly, and hand back a flat, array-backed FArray (or a single value, for a
fold).
That laziness is the trade. A bare array would be a hair quicker at a single indexed read (one
type-check that int[] doesn't carry), but it can't compare or print itself:
IArray(1, 2, 3).toString is [I@5a07e868
and == is identity. FArray wraps the array in an object,
so it gives that hair back and gets value equals, hashCode and toString, plus a collection you
can assemble any way you please, in constant time, paying for a flat array only when you ask for one.
Here's the cost of each:
| operation | cost | what it builds |
|---|---|---|
| +: prepend · :+ append | O(1) | a Prepend / Append node |
| ++ concat | O(1) | a Concat node |
| take · drop · slice | O(1) | a SliceNode |
| reverse | O(1) | a ReverseNode |
| updated | O(1) | an Updated node |
| padTo | O(1) | a Pad node |
| FArray.range | O(1) | a RangeNode (elements never allocated) |
| apply(i) · head · last | O(1) on a leaf · O(depth) on a node chain | nothing |
| map · filter · flatMap · fold | O(n) | a flat array; you hold a leaf after |
The reason that table is almost all O(1) is that the structural nodes are lazy: a Concat or a
SliceNode records an intention, it doesn't do the work. Nothing is computed until you read. So if
you ++ twenty arrays together and then call take(2), the traversal walks two elements into the
tree and stops; the other nineteen concatenations never materialize.
And what you do pay amortizes. Cons a million elements on one at a time (prepend, linked-list
style) and you've built a million-deep tree of O(1) nodes; the first elementwise combinator (a
map, a sum, a foldLeft, which is Stream.reduce with a seed)
flattens the whole thing into one contiguous primitive array in a single pass, and every read after
that is array-speed. The flat array is the preferred shape, and computing restores it.
One consequence gets a page of its own: driven as a
literal cons-list, FArray keeps pace with List at List's own game.
Two more ops belong to the O(1) family and rarely get counted: updated(i, x) is an Updated
node (a view of the original with one slot overridden, no copy of the other n−1 elements) and
padTo(n, x) is a Pad node that answers reads past the end with the pad element. Both
materialize only when a downstream op forces flat data. The set-like trio (diff, intersect,
plus transpose/permutations for the combinatorics) are eager and measured in the full suite:
ordinary wins, no special mechanism.
Sorting
Sorting is where a raw array should win outright. FArray sorts directly on the
materialized array, with a run-detecting mergesort and no boxed indices. It still takes an
Ordering (Scala's Comparator) like everything else — it just recognizes the standard primitive
instances and routes them to a native unboxed array sort, so the common case skips the
per-comparison compare call entirely: