Sequences

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