Re: Factor

Factor has had virtual sequences for a long time. A virtual sequence is typically lazy and can compute an element when asked for it, or look it up in another sequence, rather than build all the elements up front. It only needs to provide the sequence operations that describe its contents.

That lets us use normal sequence words like nth, each, map, and reduce with ranges, reversed views, windows into arrays, and even collections of combinations. I thought it would be fun to look at the different kinds we have accumulated over the years.

Note: In the examples below, >array materializes the elements into an array so the printed output shows their contents. >string does the same for character sequences. In some of the examples, the elements are themselves views like slices, we use [ >array ] map to materialize each one. These conversions are just for display; words such as nth, each, map, etc. can work directly with the virtual sequence.

Computed elements

We can start with sequences whose elements follow a simple formula:

USING: arrays prettyprint ranges sequences ;

IN: scratchpad 5 <iota> >array .
{ 0 1 2 3 4 }

IN: scratchpad 2 10 2 <range> >array .
{ 2 4 6 8 10 }

IN: scratchpad 4 "hello" <repetition> >array .
{ "hello" "hello" "hello" "hello" }

An iota stores its length, a range stores the information needed to compute its arithmetic progression, and a repetition stores a length and one element. Repeating a mutable object repeats the reference to that object.

The ranges vocabulary also has convenient constructors such as [a..b], [a..b), and [1..b] for inclusive and exclusive endpoints. And math.bits lets us treat an integer as a sequence of bits:

USE: math.bits

IN: scratchpad 0b10110 5 <bits> >array .
{ f t t f t }

Here the least significant bit comes first. <binary-bits> provides the same ordering using 0 and 1 instead of booleans.

Selecting and rearranging elements

Many virtual sequences are views of existing data. Two particularly useful ones, <slice> and <reversed>, are part of the core sequences vocabulary:

IN: scratchpad 1 4 { 10 20 30 40 50 } <slice> <reversed> >array .
{ 40 30 20 }

The slice selects indices 1 through 3, and the reversed view reads those indices in the opposite order. Neither view copies the elements. They also support writing through to a mutable backing sequence:

USE: kernel

IN: scratchpad { 10 20 30 } clone
               dup <reversed> 99 0 rot set-nth .
{ 10 20 99 }

Changing index zero of the reversed view changes the last element of the original array.

There are several other ways to select or rearrange existing elements:

For example, a step of two selects every other element (equivalent to [::2] in Python):

USE: sequences.extras

IN: scratchpad f f 2 { 10 20 30 40 50 } <step-slice> >array .
{ 10 30 50 }

The two f values select the default start and end. A column view picks an element from each row:

USE: columns

IN: scratchpad { { 1 2 3 } { 4 5 6 } } 1 <column> >array .
{ 2 5 }

The related <flipped> word builds a sequence of column views, giving us a transposed view of a rectangular matrix. It allocates the outer collection of views while sharing the row data.

Groups and windows

Sometimes the elements of a virtual sequence are themselves views. The grouping vocabulary provides non-overlapping groups and overlapping clumps:

USE: grouping

IN: scratchpad { 1 2 3 4 5 } 2 <groups> [ >array ] map .
{ { 1 2 } { 3 4 } { 5 } }

IN: scratchpad { 1 2 3 4 5 } 3 <clumps> [ >array ] map .
{ { 1 2 3 } { 2 3 4 } { 3 4 5 } }

A group can be shorter at the end; a clump has the requested size. Their elements are slices, which is why these examples convert each element to an array. The <circular-slice> and <circular-clumps> constructors extend the idea to windows that wrap around the end.

The sequences.windowed vocabulary has trailing windows, including shorter ones at the beginning:

USE: sequences.windowed

IN: scratchpad { 1 2 3 4 5 } 3 <windowed-sequence>
               [ >array ] map .
{ { 1 } { 1 2 } { 1 2 3 } { 2 3 4 } { 3 4 5 } }

And grouping.extras provides <prefixes> and <suffixes> for the nonempty initial and final slices of a sequence:

USE: grouping.extras

IN: scratchpad { 1 2 3 } <prefixes> [ >array ] map .
{ { 1 } { 1 2 } { 1 2 3 } }

IN: scratchpad { 1 2 3 } <suffixes> [ >array ] map .
{ { 1 2 3 } { 2 3 } { 3 } }

Repeating and combining sequences

We can make a sequence appear longer by reusing its elements. The sequences.repeating vocabulary offers two different arrangements:

USING: sequences.repeating strings ;

IN: scratchpad "abc" 8 <cycles> >string .
"abcabcab"

IN: scratchpad "abc" 3 <element-repeats> >string .
"aaabbbccc"

<cycles> takes the desired total length. <cycles-from> also accepts a starting offset. <element-repeats> takes the number of times to repeat each element.

Other views assemble data from multiple sources:

Here are a few examples:

USING: sequences.cords sequences.interleaved sequences.merged
sequences.padded sequences.zipped ;

IN: scratchpad { 1 2 } { 3 4 } cord-append >array .
{ 1 2 3 4 }

IN: scratchpad { 1 2 3 } { 10 20 30 40 } <2merged> >array .
{ 1 10 2 20 3 30 }

IN: scratchpad { 1 2 3 } { 10 20 } <zipped> >array .
{ { 1 10 } { 2 20 } }

IN: scratchpad "abc" CHAR: - <interleaved> >string .
"a-b-c"

IN: scratchpad { 1 2 3 } 5 0 <padded-head> >array .
{ 0 0 1 2 3 }

The assocs vocabulary also provides <enumerated>, a view of index/value pairs that works as both a sequence and an association. <zip-index> in sequences.extras provides a sequence of index/value pairs as well.

Transforming values

Views can transform values as they are read. The sequences.modified vocabulary provides scaling, offsets, and elementwise sums:

USE: sequences.modified

IN: scratchpad { 1 2 3 } 10 <scaled> 1 <offset> >array .
{ 11 21 31 }

IN: scratchpad { { 1 2 3 } { 10 20 } } <summed> >array .
{ 11 22 3 }

The summed view extends to the longest input, treating missing elements as zero. Scaled and offset views can also translate writes back to their underlying sequence; writing through a scaled view requires a nonzero scale factor.

For complex numbers, sequences.complex interprets adjacent real values as real and imaginary components, while sequences.complex-components exposes those components from a sequence of complex numbers.

Products and combinations

Some virtual sequences represent collections that could be much larger than their inputs. The sequences.product vocabulary provides a Cartesian product:

USE: sequences.product

IN: scratchpad { { "red" "blue" } { 1 2 3 } }
               <product-sequence> >array .
{
    { "red" 1 }
    { "red" 2 }
    { "red" 3 }
    { "blue" 1 }
    { "blue" 2 }
    { "blue" 3 }
}

Similarly, math.combinatorics provides <permutations>, <k-permutations>, and <combinations>:

USE: math.combinatorics

IN: scratchpad { "a" "b" "c" } 2 <combinations> >array .
{ { "a" "b" } { "a" "c" } { "b" "c" } }

IN: scratchpad { "a" "b" "c" } <permutations> length .
6

These can compute a selected result without constructing every result before it. Iterating over the entire sequence still takes work proportional to the number of results, and >array asks to store all of them.

Sharing data and materializing results

A view shares data with its source. Even sequences.frozen, which prevents writes through the view, can observe changes made through the original array:

USE: sequences.frozen

IN: scratchpad { 1 2 3 } clone dup <frozen>
               swap 99 0 rot set-nth >array .
{ 99 2 3 }

Keeping a small slice can therefore keep a much larger backing sequence alive. Nested views add indexing work, and some views allocate an element, such as a pair or a slice, when it is requested.

Implementing a virtual sequence

There is a useful implementation detail behind these examples. The core virtual-sequence mixin supports views that translate an index into an index and another sequence using virtual@. A wrapped-sequence already supplies a backing sequence and delegates its length. Reversing one takes very little code:

USING: accessors kernel math sequences ;

TUPLE: backwards < wrapped-sequence ;
C: <backwards> backwards

M: backwards virtual@
    seq>> [ length swap - 1 - ] keep ;

virtual-exemplar supplies the sequence used to choose result types for operations such as map. Computed sequences, such as ranges and combinations, can instead implement the sequence protocol directly. The broader idea of a virtual sequence covers both approaches.

The same machinery appears in specialized structures: composed quotations in quotations, strided storage in arrays.shaped, BLAS vectors in math.blas.vectors, gap buffers, and insertion views in sequences.inserters.

Have ideas for other virtual sequences that would be useful in Factor? Let us know!