## Immutable Sequences

Types for immutable sequences (IS) have the form

IS[I, E] // I is index type ; E is element type

where

• I is the type of indices for the sequence – it can be either `Z` or Slang `@bits` or `@range` types, and
• E is the type of elements in the sequence – it can be any Slang type that is immutable (this ensures that immutable structures always have immutable elements (recursively)).

### Immutable Sequence Methods

Method Description
`ISZ(e1, ..., en)` create a sequence
`IS.create(n,e)` seq. of size n with default element e
`s(i)` lookup element at index i
`s.isEmpty, s.nonEmpty` test for emptiness, non-emptiness
`s(i1 ~> e1, ..., ik ~> ek)` update at index i with value e
`s.size` return size (number of elements)
`s.indices` return Slang range of indices of s

### Immutable Sequence Infix Operations

Infix Operation Description
`++` concatentate
`+:`, `:+` prepend, append
`-`, remove single element
`--`, remove multiple elements
`==`, `!=` equality, inequality

Table Immutable Sequence Methods and Table Immutable Sequence Infix Operations summarize the methods and infix operations associated with immutable sequences

Note

ToDo, From John: Fix table references and document how to do this in Sphinx documentation. Note From Gage Determine how to in Hugo’s framework now. (RESOLVED)

Below are some examples of declaring an immutable sequence of strings indexed by integers.

``````
// Creating Immutable Sequences

// an Immutable Sequence of String indexed by Z
val s01: IS[Z,String] = IS[Z, String]("a", "b", "c")

// using the Slang type alias ISZ for Z-indexed immutable sequences
val s02: ISZ[String] = ISZ[String]("q", "r", "s")

val s02a = ISZ("q", "r", "s")  // type can often be inferred
``````

Because sequences indexed by integers are so common, Slang provides the type alias `ISZ[E]` for `IS[Z,E]`, illustrated above. The Slang compiler and IDE can often automatically infer a sequence type, but it is good practice to explicitly declare the type.

The `create` method can also be used to create a sequence of elements that all have the same value.

``````
// Creating Immutable Sequences -- automatically generate repeating element with ".create"

// IS.create(s,v) - create a sequence of size s, where each index holds value v

val s03 = IS.create(4,"c")
assert(s03 == ISZ("c", "c", "c", "c"))   // structural equality
``````

Recall that Slang uses structural equality (illustrated by the last line above).

Slang uses `s(i)` to look up the value in sequence `s` at index position `i`, which is the same as Scala, but it uses different a systax for updating, i.e., `s(i ~> e)` – creates a copy of sequence `s` where the value at index `i` is the value of expression `e`.

``````
// Indexing and updating sequences

// recall: val s01: IS[Z,String] = IS[Z, String]("a", "b", "c")
assert(s01(1) == "b")   // lookup value at index 1; 0-based indexing
assert(s01.size == 3 && s01(2) == "c")   // highest index is 1 less than size

// recall: val s03 = IS.create(4,"c")
var s04 = s03(3 ~> "d")  // update - actually, create new sequence s04 like s03 except index 3 element is "d"
s04 = s04(0 ~> "a",1 ~> "b")  // create new version of s04 where elements at indices 0 and 1 are changed
assert(s04 == ISZ("a","b","c","d"))

s04(0 ~> "x")                        // reminder: update on immutable sequences produces new sequence
assert(s04 != ISZ("x","b","c","d"))  //  ...does not update in place
assert(s04 == ISZ("a","b","c","d"))
``````

Scala sequences use 0-based indexing by default (one can set a custom non-zero-based indexing scheme, see below) and that `size` method returns the number of elements in the sequence (not the highest index value).

Immutable sequences can be “updated” (not truly updated; a copy is produced) using the `~>` operation. Multiple updates can be stated in one go.

Slang provides the methods `isEmpty`, `nonEmpty` (like Scala) for checking “empty-ness” and `isInBound` for checking if a possible index value is in bounds for a particular sequence.

``````
// Checking empty-ness and that index values are in bounds

// recall: val s01: IS[Z,String] = IS[Z, String]("a", "b", "c")
// recall: val s03 = IS.create(4,"c")

val s05 = ISZ[String]()   // empty sequence
assert(s05.isEmpty)       // test empty-ness
assert(s01.nonEmpty)      // test non-empty-ness

assert(!s01.isInBound(3)) // check if index value is in bounds (3 is not in bounds for s01)
assert(s03.isInBound(3))  // 3 is in bounds for s03
``````

Slang’s single element `-` and multiple element `--` removal operations are similar to set difference in that they remove element(s) anywhere in the sequence based on value.

``````
// Removal operations: "-" (single element) and "--" (multiple element)

// recall: val s01: IS[Z,String] = IS[Z, String]("a", "b", "c")
assert(s01 - "a" == ISZ("b", "c")) // removing an element

assert(ISZ("z","a") - "a" == ISZ("z"))  // removing is based on element value, not index position
assert(ISZ("a","a","a") - "a" == ISZ())

// recall: assert(s04 == ISZ("a","b","c","d"))
assert(s04 -- ISZ("b","c") == ISZ("a","d"))  // removing multiple elements
``````

Slang provides FP-oriented methods like `map`, `flatMap`, `filter`, `withFilter` in a form very similar to Scala’s.

``````
// map, filter, etc. on sequences

val s06 = ISZ(1,2,3,4).map(n => n + 1)  // using map with Slang's anonymous function n => ...
assert(s06 == ISZ(2,3,4,5))
assert(s06.filter(n => n > 3) == ISZ(4,5))  // keep only the elements that satisfy the predicate passed to filter
``````

Slang sequences support Scala-style iterators. In the following example, `e` binds to each element of the indexed sequence of characters `s1`.

``````
// Iterators for sequences

// recall: assert(s04 == ISZ("a","b","c","d"))
var s07 = ISZ[String]()
for (e <- s04) { // iterating over all elements of s04
s07 = e +: s07  // adding elements to front of s07 to reverse s04
}
assert(s07 == ISZ("d","c","b","a"))   // s04 reversed
``````

If one needs to work indices directly, the `.indices` method can be used produce a Slang range which can iterated over.

``````
// Iterating over sequences using ".indices"

// recall: assert(s04 == ISZ("a","b","c","d"))
var s08 = ISZ[(Z,String)]()  // s08 holds and empty sequence of pairs of indices (type Z) and String
for (i <- s04.indices) {    // iterating over all indices of s04
s08 = s08 :+ (i,s04(i))    // add pair of index and element to the end of s08
}
assert(s08 == ISZ((0,"a"),(1,"b"),(2,"c"),(3,"d")))
``````

The implementation of Slang’s immutable sequences can be found in IS.scala in Sirem runtime library.

Note

Todo, From John, To Robby:

Consider addressing the following advances topics in a concluding section.

• Point to and briefly describe the Slang implentation of sequences.
• Describe the use of the utility class ISZopstation?).
• Talk about using toSeq to convert to Scala sequences, e.g., as might be needed in a Scala extension of Slang that is working with Slang sequences.

## Mutable Sequences

Types for Mutable Sequences (MS) have a form essentially identical to that for Immutable Sequences (the only difference is that mutable sequences can hold mutable or immutable elements):

MS[I, E] // I is index type ; E is element type

where

• I is the type of indices for the sequence – it can be either `Z` or Slang `@bits` or `@range` types, and
• E is the type of elements in the sequence – it can be any mutable or immutable Slang type

The examples below illutrate that:

• Mutable sequences are created using the same syntactic style as immutable sequences,
• Despite the syntactic similarities, immutable and mutable sequences are not considered to be equal even though their contents are equal,
• methods are provide to convert between immutable and mutable sequences.
``````
// Creating Mutable Sequences

val s12 = MSZ("a", "b", "c") // a Mutable Sequence of String indexed by Z

// recall: val s01: IS[Z,String] = IS[Z, String]("a", "b", "c")
assert(s01 != s12)  // mutable and immutable sequences are not considered to have equal values (equality always fails)

// use .toMS and .toIS to convert between immutable and mutable sequences
assert(s01.toMS == s12)  // s01.toMS converts s01 from immutable sequence to mutable
assert(s01 == s12.toIS)  // s12.toIS converts s12 from mutable to immutable sequence
``````

Note

ToDo, From John, To Robby: Add text providing the rationale for why “immutable and mutable sequences are not considered to be equal even though their contents are equal”.

As expected, mutable and immutable sequences differ primarily in the notion of updating. The assignment command form `ms(i) = e` destructively updates mutable sequence `ms` and index position `i` (can be an arbitrary expression) with the value of `e`. However, the expression form `ms(i ~> e)` does not update `ms`; it returns a new mutable sequence with index value `i` mapping to value of `e`.

``````
// Updating Mutable Sequences

// recall: val s12 = MSZ("a", "b", "c")
s12(0) = "c"    // destructive update
s12(1) = "c"    // destructive update

assert(s12 == MSZ.create(3, "c"))  // s12 has all "c"'s now

s12(1 ~> "d")   // not a destructive update; produces a new MSZ with index 1 holding "d"

assert(s12 == MSZ.create(3, "c"))  // s12 still has the same value

assert(s12(1 ~> "d") == MSZ("c","d","c"))  // create a new version based on s12
``````

To avoid creating alias which makes verification more challenging, Slang adopts a copy-semantics for assignment of mutable sequences.

``````
// Implicit copying of Mutable Sequences to avoid aliasing

val s13 = s12       // make a copy of s12 for s13
assert(s13 == s12)  // s12 and s13 are equal due to structural equality

s13(0) = "a"        // update s13
assert(s13 != s12)  // due to the copy made, only s13 is updated
``````