CS223, 4/30/2010
Lecture 14

Imperative Features of SML: Arrays
----------------------------------

Arrays:
See Paulson, Section 8.6 (pp 335-340).
See Array module spec in Basis Library documentation.
  http://www.standardml.org/Basis/array.html

Module Array:

   eqtype 'a array   -- arrays are polymorphic

Creating arrays:

   val array : int * 'a -> 'a array
   val fromList :'a list -> 'a array
   val tabulate : int * (int -> 'a) -> 'a array   

Length of an array

   val length : 'a array -> int

Accessing elements of an array

   val sub : 'a array * int -> 'a

Updating elements of an array

   val update: 'a array * int * 'a -> unit
   
Bulk array operations:

   (* mutating map *)
   val modify : ('a -> 'a) -> 'a array -> unit

   val app  : ('a -> unit) -> 'a array -> unit, 
   val appi : (int * 'a -> unit) -> 'a array -> unit

   val foldl, foldr :   ('a * 'b -> 'b) -> 'b -> 'a arry -> 'b
   val foldli, foldri : (int * 'a * 'b -> 'b) -> 'b -> 'a arry -> 'b

Search, tests

   val find : ('a -> bool) -> 'a array -> 'a option
   val findi : (int * 'a -> bool) -> 'a array -> (int * 'a) option

   val exists: ('a -> bool) -> 'a array -> bool
   val all :   ('a -> bool) -> 'a array -> bool

--------------------
SML also has vectors

   http://www.standardml.org/Basis/array.html

Vectors are supported syntactically by vector expressions and patterns:

   - val v = #[1,2,3]
   val v = #[1,2,3] : int vector

   - fun vfst #[x,y,z] = x
   val f = fn : 'a vector -> 'a

   - vfst v;
   val it = 1 : int

--------------------
Related library modules are:

1. Slices
   ArraySlice : SLICE_SLICE    -- "slice" of an array
   VectorSlice : VECTOR_SLICE  -- "slice" of an array

2. Monomorphic Arrays and Vectors (packed representations)

   MONO_ARRAY
     CharArray : MONO_ARRAY
     RealArray : MONO_ARRAY
   MONO_VECTOR
     CharVector : MONO_VECTOR

   MONO_ARRAY_SLICE
   MONO_VECTOR_SLICE

3. Strings are a special case of mono-vector:
   String :> STRING 
     type string = CharVector.vector

   SubString :> SUBSTRING  -- analogue of vector slices

4. Two dimentional arrays

   Array2 : ARRAY2


----------------------
Applications of arrays

1. Paulson gives "functional arrays" as an example using arrays.

2. Hash tables ([smlnj] is the SML/NJ installation directory)

Used to implement finite maps and sets.

   [smlnj]/smlnj-lib/Util/hash-table-rep.sml
   [smlnj]/smlnj-lib/Util/hash-table.sml


================================================================================
Imperative Features of ML: I/O

Multiple levels of I/O functionality

* readers and writers

* functional stream I/O  (buffered)

* imperative I/O (buffered)

  The basic interface for Imperative I/O is described in:

    http://www.standardml.org/Basis/imperative-io.html#IMPERATIVE_IO:SIG:SPEC

  I/O has two flavors: Text and Binary

    [http://www.standardml.org/Basis/text-io.html]

    signature TEXT_IO
    structure TextIO :> TEXT_IO
      (extends IMPERATIVE_IO)

    [http://www.standardml.org/Basis/bin-io.html]
    signature BIN_IO
    structure BinIO : BIN_IO

* String conversion -- facilities for converting from strings to
  values (rudimentary value parsing)

    structure StringCvt :> STRING_CVT

* Pretty printing

    SML/NJ Library Pretty Printing
    [smlnj]/smlnj-lib/PP

-------------------