# Sequences

A sequence is a list (possibly infinite) which is accessed sequentially with the words:

HEAD ( seq -- * )

puts the first item from the sequence on the stack, andTAIL ( seq -- seq )

puts the tail of the sequence (i.e., without the head) on stack.

.LIST ( seq -- )(of course, an infinite list gives a never-ending listing!) For example, a sequence can be built "by hand". The word

NILputs an empty list on the stack. The word

CONS ( seq * -- seq )adds a head to a sequence and requires two arguments; the first argument is the target sequence and the second argument (*) is the new head to be added:

nil 0 cons 1 cons 2 cons .list 2 1 0 okA sequence of numbers can also be built using the word

... ( a b -- seq )(be extra careful as this sequence is infinite by default!). It requires 2 arguments and the elements inside the sequence follow the arithmetic progression defined by them:

1 2 ... .list 1 2 3 4 5 6 (keeps on going!)Or, a sequence can be built using both methods:

1 3 ... "hello" cons .list hello 1 3 5 7 9 11 (keeps on going!)Note that the previous sequence is mixed - it contains both numbers and a textual head. The word

HEADaccesses the head/first item on the list:

1 2 ... head . 1 ok nil 0 cons 1 cons 2 cons head . 2 okThe word

TAILaccesses the remainder of the list without its head:

1 2 ... 10 take tail .list 2 3 4 5 6 7 8 9 10 ok nil 0 cons 1 cons 2 cons tail .list 1 0 okNow you can see clearly what the difference is between using

CONSand using

...to build sequences in terms of the head and tails.

The following words can also help you with sequences:

NIL? ( seq -- f )

tests if the sequence is equal to the special empty list calledNIL

EMPTY? ( seq -- f )

tests if the sequence is empty (this is different fromNIL?

)SEQ?

tests if the item on the top of the stack is a sequence

## Truncating a Sequence

Many times, you may want to create a finite list but not "by hand". There are a couple of ways to do this.

The wordTAKE ( seq n -- seq )takes only the first N elements from a sequence:

0 5 ... 10 take .list 0 5 10 15 20 25 30 35 40 45 okAlternatively, you can also use word

TAKE-WHILE ( seq xt -- seq ).

TAKE-WHILEuses an XT to determine if it should accept further elements from the input list. It truncates the list as soon as the XT returns

FALSE

: 100< 100 < ; 0 10 ... ' 100< take-while .list 0 10 20 30 40 50 60 70 80 90 ok

## Lazy Nature of Infinite Sequences

In Smojo, all infinite sequences are**lazy**, which means it does not place every elements immediately onto the stack or anywhere in the program. Instead, an object describing the infinite sequence is placed onto the stack. Only when words such as

.LISTor

HEADneeds to take the sequence as an argument, will the sequence be constructed, one element at a time. Many sequence-related words like

TAKEor

TAKE-WHILEare also lazy. These words will not perform their tasks until they are forced to (e.g. by

.LIST) This property of the laziness of infinite sequences and related words can make Smojo highly efficient when processing or transferring an extremely long data sequence or even an infinite sequence (e.g. data continuously collected by a sensor). Also, with laziness it is possible to represent an indefinite amount of data. Typically, we want to process only some, not all of this data. You should try using the word

.instead of

.LISTto print a sequence or the output of

TAIL,

TAKE,

TAKE-WHILEto see what is actually on the stack.

## Quiz

### Question 1

Write a word.. ( s e -- seq )which takes 2 numbers, start (s) and end (e) and produces a sequence of numbers from start to end, with skip of 1. For example:

20 25 .. .list 20 21 22 23 24 25 okWhat if start > end (i.e. a descending list)? Try to come up with 2 solutions; one that uses

TAKEand the other using

TAKE-WHILE. Be reminded that

TAKE-WHILErequires using an XT.

Using take:

: .. ( s e -- seq ) >R dup R@ > if -1 else 1 then >R \ s dup dup R> + ... swap \ seq s R> swap - abs 1 + take ; 1 1 .. .list \ 1 1 2 .. .list \ 1 2 1 3 .. .list \ 1 2 3 3 1 .. .list \ 3 2 1 2 1 .. .list \ 2 1

Using take-while:

: .. ( s e -- seq ) { s e } s s s e > if 1- else 1+ then ... \ seq s e > if [: e >= ;] else [: e <= ;] then take-while ; 1 1 .. .list \ 1 1 2 .. .list \ 1 2 1 3 .. .list \ 1 2 3 3 1 .. .list \ 3 2 1 2 1 .. .list \ 2 1

### Question 2

Improve both your solutions to Question 1 so that your word..can take 3 numbers, start end and skip. For example:

20 30 2 .. .list 20 22 24 26 28 30 okWhat happens if the end value is not on the arithmetic progression?

Using take:

: .. ( s e skip -- seq ) { skip } >R dup R@ > if -1 else 1 then skip * >R \ s dup dup R> + ... swap \ seq s R> swap - abs skip / 1 + take ; 20 30 2 .. .list \ 20 22 24 26 28 30 20 30 3 .. .list \ 20 23 26 29 30 20 2 .. .list \ 30 28 26 24 22 20 30 20 3 .. .list \ 30 27 24 21

Using take-while:

: .. ( s e skip -- seq ) >R { e } dup dup e > if -1 else 1 then dup { direction } R> * + ... \ seq direction 1 = if [: e <= ;] else [: e >= ;] then take-while ; 20 30 2 .. .list \ 20 22 24 26 28 30 20 30 3 .. .list \ 20 23 26 29 30 20 2 .. .list \ 30 28 26 24 22 20 30 20 3 .. .list \ 30 27 24 21