Rebol Programming/Language Features/Series

Introducing series

Series were introduced to Rebol by its designer to represent sequences of values. The most typical series in Rebol are blocks.

Naturally, it would be quite nifty if you could access, manipulate, and refer to individual entries within a series.

Well, it just so happens that Rebol provides a quite extensive "data access technology" for accomplishing this.

Let's look at a first example which will help to sharpen our intuitive idea as to what a series looks like.

The following is a Rebol block which has two entries:

   series1: [1 2] ; == [1 2]

You might read this as

“

The word series1 refers to a block having 2 entries, both of which happen to refer to integers.

”

Since any block has zero or more entries (you did know that a block can have nothing in it, n'est-ce pas?), and since as a point of fact this particular block happens to have 2 entries, you would be quite correct to say that the block can be treated as a series.

And of course, looking at this, you might wonder, how do you do things like "ask" what the second entry's value is? Or maybe you want to know if the n'th entry in a particular series exists? Or maybe you wish to change a particular entry within a series.

You can do all this and much more in Rebol.

So let's take a look at how we can access data in a series within Rebol.

Data access methods

In Rebol we can use several methods. The method using the first, second, etc. functions:

   first series1 ; == 1

The method using the path notation:

   series1/1 ; == 1

The method using the pick function:

   pick series1 1 ; == 1

Using variables for data access

Let's suppose, that we have got a variable (e.g. i),

   i: 2

that shall be used to access a specific entry within a series. How can this be done?

Although the method using the first function doesn't look useful for this, it can be used too. The details are described in the subsequent sections.

The method using the path notation is:

   series1/:i ; == 2

The method using the pick function:

   pick series1 i ; == 2

Why series/i doesn't work?

Actually, series/i does work, but it doesn't interpret the word i as a variable. Example:

   i: 20
   series23: [1 i 3]
   series23/i ; == 3

Description: when the interpreter encountered the series23/i expression, it tried to find the word i in series23, i.e. it took the word as a value, not as a variable. The value returned is the value next to the value, that has been found.

But since core 2.6.0 series/(i) is implemented:

   i: 1
   series23: [1 i 3]
   series23/(i) ; == 1

By placing the word i into parentheses, the parenthesized expression is evaluated and the value of the third entry of the series is returned.

Changing series

Sometimes we need to change a series. Let's suppose, that we want to change series1. The first method uses the change function:

   series1: [1 2]
   change series1 3
   series1 ; == [3 2]

The path notation method:

   series1: [3 2]
   series1/1: 1 ; == [1 2]

The poke function method:

   series1: [1 2]
   poke series1 1 3 ; == [3 2]

Using variables

If we have got a variable i as above, we can still use the change method. The details are discussed in the subsequent sections.

The path notation method:

   series1: [3 2]
   i: 2
   series1/:i: 4

The poke method:

   series1: [3 2]
   i: 2
   poke series1 i 4 ; == [3 4]

Data access method differences

The three data access methods listed above exhibit different behaviour in special situations. Let's prepare series2 to see the differences:

   series2: [1 2]
   f: does [""]
   poke series2 1 :f

The first function access method

When we try to access an entry that doesn't exist, an error is caused:

   third series2
   ** Script Error: Out of range or past end
   ** Near: third series2

When we access a function using this method, the function is the result:

   type? first series2 ; == function!

The path notation access method

When we try to get the value of an entry that doesn't exist, we obtain the none value:

   series2/3 ; == none

When we access a function using the path method, the function is evaluated:

   type? series2/1 ; == string!

The pick function access method

When we try to get the value of an entry that doesn't exist, we obtain the none value:

   pick series2 3 ; == none

When we access a function using the pick method, the function is the result:

   type? pick series2 1 ; == function!

Why does Rebol need so many access methods?

Actually it doesn't, but the methods work differently as has been shown and that is why we can choose the method that is the most appropriate for our task.

If we prefer the most strict bound checking, we may prefer first.

If we need automatic evaluation of functions or automatic searching, we may prefer the path access.

If we want a simple access method, that doesn't evaluate functions, we may choose pick.

Length of a series

A series can have many entries. It may be useful to know the actual number for a given series. We can use the length? native to find it:

   length? [1 2 3] ; == 3

On the other hand, it is even possible, that a series does not have any entry. There is a Rebol native empty? which tells us, whether a series "does not have any entry". In that case the length? native yields zero:

   series3: []     ; == []
   empty? series3  ; == true
   length? series3 ; == 0

From head to tail and back again

Sometimes we need to access series sequentially instead of using indexed access. Rebol series can be accessed sequentially without a need to use any additional datatype.

To move sequentially "one entry at a time" in a non-empty series we can use the next native. The next native yields a series with the first entry "skipped". The second entry of the original series becomes the first entry of the new series.

   series8: [1 2 3 4]     ; == [1 2 3 4]
   series9: next series8  ; == [2 3 4]

The first, second, etc. entries of the new series are the same, as the second, third, etc. entries of the original series:

   series9/1 ; == 2
   series8/2 ; == 2
   series9/2: 5 ; == [2 5 4]
   series8/3 ; == 5

In the new series we can use even the skipped entries: (R2 only)

   series9/-1 ; == 1

The length of the new series is equal to the length of the original series minus one:

   length? series8 ; == 3
   length? series9 ; == 2

Instead of skipping one entry at a time, we can skip more entries at once using the skip action. A Rebol description of the skip action for non-negative offset:

   skip-def: func [
       {Skips some places of a series}
       series [series!]
       offset [integer!] {Can be positive, or zero.}
   ][
       loop offset [
           series: next :series
       ]
       :series
   ]
   series8: [1 2 3 4]            ; == [1 2 3 4]
   series10: skip-def series8 2  ; == [3 4]

If we skip zero entries, we obtain the original series:

   series8: [1 2 3 4]            ; == [1 2 3 4]
   same? series8 skip series8 0  ; == true

If we skip all entries of a series, we obtain an empty series called its tail:

   tail-def: func [
       {Returns the tail of a series.}
       series [series!]
   ][
       skip :series length? :series
   ]
   tail-def [1 2 3] ; == []

Here is a definition of a function that determines whether a series is a tail:

   tail?-def: func [
       {Finds out, if a given series is a tail}
       series [series!]
   ][
       empty? :series
   ]

   tail?-def [1 2 3]  ; == false
   tail?-def []       ; == true

Skipping further from tail using the next function, doesn't have any effect:

   same? next tail [1 2 3] tail [1 2 3] ; == true

We can use the back action to skip one entry backwards, which means the reverse of next:

   series11: tail [1 2 3 4]   ; == []
   series12: back series11    ; == [4]

Let's enhance the skip-def to use negative offset values:

   skip-def: func [
       {Skips some places of a series}
       series [series!]
       offset [integer!] {Can be positive, zero, or negative.}
   ][
       either positive? offset [
           loop offset [
               series: next :series
           ]
       ][
           loop negate offset [
               series: back :series
           ]
       ]
       :series
   ]

   series11: tail [1 2 3 4]         ; == []
   series13: skip-def series11 -2   ; == [3 4]

The series we obtain from a given series by skipping the maximum possible number of entries backwards is called the head of the given series. Any subsequent back call doesn't skip any further and yields the head too:

   series14: next [1 2 3]    ; == [2 3]
   head series14             ; == [1 2 3]
   same? back head series14 head series14 ; == true

We can use the above definition to provide a Rebol function determining if a series is a head:

   head?-def: func [
       {Returns true for a head series.}
       series [series!]
   ][
       same? :series back :series
   ]

   head?-def [] ; == true

With a help of head? we can even provide the Rebol description of head:

   head-def: func [
       {Returns the head of a series.}
       series [series!]
   ][
       while [not head? :series] [series: back :series]
       :series
   ]

The number of the "backward" entries increased by one can be obtained as a result of the index? native:

   index? next [1 2] ; == 2

Referring to values

Let's discover a less natural property of series. A series can refer twice (or more times) to a given value. The following function creates a block referring to a given value exactly twice:

   twice: func [value [any-type!]] [
       head insert/dup make block! 2 get/any 'value 2
   ]

Let's test the properties of the function we defined:

   series3: twice 1 ; == [1 1]
   same? first series3 second series3 ; == true

   series4: twice 'o1 ; == [o1 o1]
   same? first series4 second series4 ; == true

   o2: make object! [attribute: "OK"]
   series5: twice o2
   ; == [
   ;    make object! [
   ;        attribute: "OK"
   ;    ]
   ;    make object! [
   ;        attribute: "OK"
   ;    ]]
   same? first series5 second series5 ; == true
   o2/attribute: "Surprise?"
   series5
   ; == [
   ;    make object! [
   ;        attribute: "Surprise?"
   ;    ]
   ;    make object! [
   ;        attribute: "Surprise?"
   ;    ]]

By analogy, one value can be referenced by two series:

   o3: make object! [attribute: "OK"]
   series6: reduce [o3 1]
   ; == [
   ;     make object! [
   ;         attribute: "OK"
   ;     ] 1]

   series7: reduce [o3 2]
   ; == [
   ;     make object! [
   ;         attribute: "OK"
   ;     ] 2]
   o3/attribute: "Surprised Again?"
   series6
   ; == [
   ;     make object! [
   ;         attribute: "Surprised Again?"
   ;     ] 1]
   series7
   ; == [
   ;    make object! [
   ;        attribute: "Surprised Again?"
   ;    ] 2]

Properties of the change action

If we want to change a series, we can use the change action. Change can be said to change the series; it causes the affected entry to refer to another value. On the other hand, change doesn't affect the values:

   a: make object! [attribute: "OK"]

   series15: twice a
   ; == [
   ;     make object! [
   ;         attribute: "OK"
   ;     ]
   ;     make object! [
   ;         attribute: "OK"
   ;     ]]

   change series15 2
   ; == [
   ;     make object! [
   ;         attribute: "OK"
   ;     ]]

   series15
   ; == [2
   ;     make object! [
   ;         attribute: "OK"
   ;     ]]
   probe a
   ;     make object! [
   ;         attribute: "OK"
   ;     ]

change doesn't return the original series. It skips the affected entries to facilitate subsequent changes.

Comparing entries and series

For any series we can use the copy action to create a new series referring to the same values. A copy of a series is not the same series as the original, though:

   series16: reduce [make object! [attribute: "OK"]]
   ; == [
   ;     make object! [
   ;         attribute: "OK"
   ;     ]]

   series17: copy series16
   ; == [
   ;     make object! [
   ;         attribute: "OK"
   ;     ]]

   same? series16 series17   ; == false
   change series16 1         ; == []
   series16                  ; == [1]
   series17
   ; == [
   ;     make object! [
   ;         attribute: "OK"
   ;     ]]

We have seen an example of a situation, when two distinct series entries refer to one Rebol value, or a situation, when two distinct series (prepared using e.g. the skip function) share some entries. Although series entries do not behave as stand-alone entities in Rebol, we can specify an individual entry by specifying a series and a number of the entry in the series. Thus, we can find out, if two entries (references) specified are the same. The function doing this can be found at References.

Since we are able to compare entries, we can say, that non-empty series having the same datatype are the same, if they consist of the same entries. The trouble with this method is, that it is not usable for empty series, because in an empty series there is no entry we could use for the comparison purposes.

We call two series mutually independent, if they neither share any entries, nor they can be derived from one "mother" series using the skip function. In Rebol this definition can be written as follows:

   independent?: func [
       {Find out, if two series are mutually independent.}
       series1 [series!]
       series2 [series!]
   ] [
       not same? head :series1 head :series2
   ]
   series19: [1 2 3]                ; == [1 2 3]
   series20: next series19          ; == [2 3]
   series21: copy series19          ; == [1 2 3]
   independent? series19 series20   ; == false
   independent? series19 series21   ; == true

Observation: a series and its copy are mutually independent.

Cumulative properties of series operations

A cumulative property of change/only: change/only changes the reference of its argument Series. From this description is immediately obvious, that change/only affects all series sharing the reference in question.

We can create a new reference using the insert action.

   series22: [1 2 3]         ; == [1 2 3]
   length? series22          ; == 3
   insert/only series22 0    ; == [1 2 3]
   series22                  ; == [0 1 2 3]
   length? series22          ; == 4

We can use insert to define the meaning of the same? action for empty series. We say, that two empty series are the same, if insert used for the first series causes the second series to become non-empty too.

The description of the insert/only work: insert/only defines a new entry in the series, enlarging the number of entries in the series by one. The newly inserted entry becomes the first entry of the series, while the numbers of the other entries in the series are therefore higher by one. insert/only causes the newly created entry to refer to its value argument. Note, that insert/only doesn't change Index of any series! It skips the inserted entry to facilitate subsequent inserts.

The cumulative property of insert/only: for all series dependent on the series affected by insert/only holds: the dependent series is enlarged by one entry too, moreover, if the index of the dependent series is lower than the index of the affected series, its first entry remains the same, if the index of the dependent series is equal to the index of the affected series, the first entry of the series after insert will be the newly inserted reference and if the index of the dependent series is higher than the index of the affected series, then the first entry of the dependent series will be the entry preceding the original first entry.

For lowering the number of entries in a series we can use the remove and clear actions. Probably every reader is now able to use the above described methods for exploring the cumulative properties of these. I shall leave that as an exercise for the reader.

Series with fast index access versus series with fast remove/insert operations

Series with fast index access

Rebol blocks are examples of series with fast index access. That means, that operations like

   pick series index

have the same speed regardless of:

• the length of the series
• the value of the index

Generally, all Rebol series except for Rebol lists are of this type.

Advantages

• the speed of index access (pick, poke, skip, at, length?, index?, offset?, etc.)

Disadvantages

• general remove/insert operations are "slow", the time needed to perform a remove/insert operation is proportional to the length of the series in general case
• after any insert/remove operation the index of all related series remains the same, which means, that after an insert or a remove operation a series actually refers to different entries than before such an operation:

   s: [1 2 3 4 5 6]
   t: skip s 2 ; == [3 4 5 6]
   remove s
   t ; == [4 5 6]

• due to the above property, it is even possible to obtain past-tail series, i.e. series having an index that is actually not "available" in the given series

Series with fast insert/remove

As already mentioned, there is only one Rebol series type having this property. It is the list! datatype.

Advantages

• remove/insert operations are fast
• after an insert operation, all Rebol lists remain "unaffected" in that they point to the entry they pointed to before the insert operation was performed
• after a remove operation, all Rebol lists (except for the ones directly affected, having a removed entry as the first) remain "unaffected" in that they point to the entry they did point to before the remove operation was performed
• no list can be caused to become past-tail

Disadvantages

• due to the way how Rebol lists are implemented in R2 currently, a removal of the first element of a list causes the list to become a "list having an invalid (removed) position"; but see my list prototype below coping with this problem without a significant slow-down of any operation; the prototype adjusts such lists to point to the first subsequent valid entry instead of the removed one
• general index operations are "slow"; time needed to perform such operations is proportional to the length of the list in the general case

List prototype

Since lists are not present in R3, and due to the above mentioned problem with removed entries I decided to implement a list prototype that can improve the situation.

use [] [
    list-proto: make object! [
        ; the position of a list is not an integer index,
        ; it is a list entry
        position: none

        ; to have fast tail tail? head head?
        ; we need to know the position of the list tail
        tail: none
    ]

    list-entry-proto: make object! [
        ; every list entry refers to a value
        ; the tail entry always refers to NONE
        value: none

        ; for every list entry we want to know,
        ; where the previous entry is

        ; for convenience we define,
        ; that the previous entry of a head entry
        ; is the tail entry

        ; to be able to detect the deleted entries
        ; we define, that the previous entry
        ; of a deleted entry is NONE
        previous: none

        ; for every list entry we want to know,
        ; where the subsequent entry is

        ; for convenience we define,
        ; that the subsequent entry of the tail entry
        ; is the head entry
        subsequent: none
    ]

    set 'make-empty-list func [
        {create an empty list}
    ] [
        make list-proto [
            position: tail: make list-entry-proto []

            ; head entry is the tail entry for empty lists 
            tail/subsequent: tail/previous: tail
        ]
    ]

    set 'tail-s func [
        {return the tail of a list}
        list [object!]
    ] [
        make list-proto [position: tail: list/tail]
    ]

    set 'head-s func [
        {return the head of a list}
        list [object!]
    ] [
        make list-proto [
            tail: list/tail
            position: tail/subsequent
        ]
    ]

    set 'last-s func [
        {returns the last value of a list}
        list [object!]
    ] [
        return get/any in list/tail/previous 'value
    ]

    adjust-position: func [
        {this function adjusts the list position to not refer to a removed entry}
        list [object!] {the list to check/adjust}
        /local current valid subsequent
    ] [
        ; note:
        ; even though this function uses two while cycles,
        ; it is implemented so,
        ; that its running time is insignificant

        ; explanation:
        ; for the adjust-position call to take O(n) time
        ; it is necessary to perform n removes,
        ; and after the adjustment,
        ; all subsequent calls to the adjust-position function
        ; become O(1) again
        ; this means, that the adjust-position call adds just
        ; O(1) time to every remove call,
        ; in addition to the O(1) time needed for every adjust-position call
        ; when the list position is valid

        ; we look for the first valid entry
        current: list/position
        while [
            ; test, if the current entry is a removed entry
            none? current/previous
        ] [current: current/subsequent]
        valid: current

        ; now we "clean" the removed entries
        ; to not have to traverse them any more
        current: list/position
        while [
            ; test, if the current entry is a removed entry
            none? current/previous
        ] [
            subsequent: current/subsequent

            ; doing the cleanup
            current/subsequent: valid

            current: subsequent
        ]

        ; adjust the list position to be valid
        list/position: valid
    ]

    set 'head?-s func [
        {returns TRUE if at head}
        list [object!]
    ] [
        adjust-position list

        list/position = list/tail/subsequent
    ]

    set 'tail?-s func [
        {returns TRUE if at tail}
        list [object!]
    ] [
        adjust-position list

        list/position = list/tail
    ]

    set 'index?-s func [
        {returns the index of a list}
        list [object!]
        /local current index
    ] [
        adjust-position list

        current: list/position
        index: 1
        while [
            ; the current entry is not head
            current/previous <> list/tail
        ] [
            index: index + 1
            current: current/previous
        ]
        index
    ]

    set 'length?-s func [
        {returns the length of a list}
        list [object!]
        /local current length
    ] [
        adjust-position list

        current: list/position
        length: 0
        while [
            ; the current entry is not tail
            current <> list/tail
        ] [
            length: length + 1
            current: current/subsequent
        ]
        length
    ]

    set 'skip-s func [
        {returns the list forward or backward from the current position}
        list [object!]
        offset [integer!]
        /local current
    ] [
        adjust-position list

        current: list/position
        either negative? offset [
            ; traversing the list towards its head
            while [
                all [
                    ; not at the head?
                    current/previous <> list/tail

                    offset < 0
                ]
            ] [
                current: current/previous
                offset: offset + 1
            ]
        ] [
            ; traversing the list towards its tail
            while [
                all [
                    ; not at the tail?
                    current <> list/tail

                    offset > 0
                ]
            ] [
                current: current/subsequent
                offset: offset - 1
            ]
        ]
        make list-proto [
            position: current
            tail: list/tail
        ]
    ]

    set 'first-s func [
        {returns the first value of a list}
        list [object!]
    ] [
        adjust-position list

        return get/any in list/position 'value
    ]

    set 'remove-s func [
        {removes an element from a list}
        list [object!]
        /local current
    ] [
        adjust-position list

        current: list/position
        either current = list/tail [
            ; no removal needed, just return the argument
            list
        ] [
            ; adjust links
            current/previous/subsequent: current/subsequent
            current/subsequent/previous: current/previous

            ; mark the current element as removed
            current/previous: none

            ; return the next position
            make list-proto [
                position: current/subsequent
                tail: list/tail
            ]
        ]
    ]

    set 'insert-only func [
        {insert one value into a list}
        list [object!]
        value [any-type!]
    ] [
        adjust-position list

        make list-proto [
            ; create a new list entry
            position: make list-entry-proto [
                previous: list/position/previous
                subsequent: list/position
            ]

            error? set/any in position 'value get/any 'value

            ; adjust links
            position/previous/subsequent: position
            position/subsequent/previous: position

            tail: list/tail
        ]
    ]

    set 'change-only func [
        {change a value in a list}
        list [object!]
        value [any-type!]
        /local new-entry
    ] [
        adjust-position list

        if list/position = list/tail [
            ; we are at tail, change is not possible
            do make error! "out of range"
            ; (alternatively, we may insert a new entry, if preferred)
        ]

        error? set/any in list/position 'value get/any 'value

        ; return the list at the next position
        make list-proto [
            position: list/position/subsequent
            tail: list/tail
        ]
    ]   
]