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, and
```
TAIL ( seq -- seq )
```
puts the tail of the sequence (i.e., without the head) on stack.

There are many ways to create a sequence and they may be displayed using the word

.LIST ( seq --  )

(of course, an infinite list gives a never-ending listing!)

For example, a sequence can be built "by hand". The word

NIL

puts 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
		ok

A 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

HEAD

accesses the head/first item on the list:

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

The word

TAIL

accesses 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
		ok

Now you can see clearly what the difference is between using

CONS

and 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 called
```
NIL
```
```
EMPTY? ( seq -- f )
```
tests if the sequence is empty (this is different from
```
NIL?
```
)
```
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 word

TAKE ( 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
		ok

Alternatively, you can also use word

TAKE-WHILE ( seq xt -- seq )

TAKE-WHILE

uses 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

.LIST

HEAD

needs to take the sequence as an argument, will the sequence be constructed, one element at a time.

Many sequence-related words like

TAKE

TAKE-WHILE

are 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

.LIST

to print a sequence or the output of

TAIL

TAKE

TAKE-WHILE

to 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 ok

What if start > end (i.e. a descending list)? Try to come up with 2 solutions; one that uses

TAKE

and the other using

TAKE-WHILE

. Be reminded that

TAKE-WHILE

requires 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 ok

What 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

Next: Hashes