Subsequences and slices
Factor handbook » The language » Collections » Sequence operations

Prev:Appending sequences
Next:Reshaping sequences


There are two ways to extract a subrange of elements from a sequence. The first approach creates a new sequence of the same type as the input, which does not share storage with the underlying sequence. This takes time proportional to the number of elements being extracted. The second approach creates a slice, which is a virtual sequence (see Virtual sequences) sharing storage with the original sequence. Slices are constructed in constant time.

Some general guidelines for choosing between the two approaches:
If you are using mutable state, the choice has to be made one way or another because of semantics; mutating a slice will change the underlying sequence.
Using a slice can improve algorithmic complexity. For example, if each iteration of a loop decomposes a sequence using first and rest, then the loop will run in quadratic time, relative to the length of the sequence. Using rest-slice changes the loop to run in linear time, since rest-slice does not copy any elements. Taking a slice of a slice will “collapse” the slice so to avoid the double indirection, so it is safe to use slices in recursive code.
Accessing elements from a concrete sequence (such as a string or an array) is often faster than accessing elements from a slice, because slice access entails additional indirection. However, in some cases, if the slice is immediately consumed by an iteration combinator, the compiler can eliminate the slice allocation and indirection altogether.
If the slice outlives the original sequence, the original sequence will still remain in memory, since the slice will reference it. This can increase memory consumption unnecessarily.


Subsequence operations
Extracting a subsequence:
subseq ( from to seq -- subseq )

subseq-as ( from to seq exemplar -- subseq )

head ( seq n -- headseq )

tail ( seq n -- tailseq )

head* ( seq n -- headseq )

tail* ( seq n -- tailseq )


Removing the first or last element:
rest ( seq -- tailseq )

but-last ( seq -- headseq )


Taking a sequence apart into a head and a tail:
unclip ( seq -- rest first )

unclip-last ( seq -- butlast last )

cut ( seq n -- before after )

cut* ( seq n -- before after )


Slice operations
The slice data type:
slice

slice? ( object -- ? )


Extracting a slice:
<slice> ( from to seq -- slice )

head-slice ( seq n -- slice )

tail-slice ( seq n -- slice )

head-slice* ( seq n -- slice )

tail-slice* ( seq n -- slice )


Removing the first or last element:
rest-slice ( seq -- slice )

but-last-slice ( seq -- slice )


Taking a sequence apart into a head and a tail:
unclip-slice ( seq -- rest-slice first )

unclip-last-slice ( seq -- butlast-slice last )

cut-slice ( seq n -- before-slice after-slice )


Replacing slices with new elements:
replace-slice ( new from to seq -- seq' )