The Standard ML Basis Library


The MONO_ARRAY signature


Synopsis

signature MONO_ARRAY
structure Word8Array :> MONO_ARRAY
  where type vector = Word8Vector.vector
  where type elem = Word8.word
structure CharArray :> MONO_ARRAY
  where type vector = CharVector.vector
  where type elem = char
structure WideCharArray :> MONO_ARRAY  (* OPTIONAL *)
  where type vector = WideCharVector.vector
  where type elem = WideChar.char
structure BoolArray :> MONO_ARRAY  (* OPTIONAL *)
  where type vector = BoolVector.vector
  where type elem = bool
structure IntArray :> MONO_ARRAY  (* OPTIONAL *)
  where type vector = IntVector.vector
  where type elem = int
structure WordArray :> MONO_ARRAY  (* OPTIONAL *)
  where type vector = WordVector.vector
  where type elem = word
structure RealArray :> MONO_ARRAY  (* OPTIONAL *)
  where type vector = RealVector.vector
  where type elem = real
structure LargeIntArray :> MONO_ARRAY  (* OPTIONAL *)
  where type vector = LargeIntVector.vector
  where type elem = LargeInt.int
structure LargeWordArray :> MONO_ARRAY  (* OPTIONAL *)
  where type vector = LargeWordVector.vector
  where type elem = LargeWord.word
structure LargeRealArray :> MONO_ARRAY  (* OPTIONAL *)
  where type vector = LargeRealVector.vector
  where type elem = LargeReal.real
structure Int<N>Array :> MONO_ARRAY  (* OPTIONAL *)
  where type vector = Int{N}Vector.vector
  where type elem = Int{N}.int
structure Word<N>Array :> MONO_ARRAY  (* OPTIONAL *)
  where type vector = Word{N}Vector.vector
  where type elem = Word{N}.word
structure Real<N>Array :> MONO_ARRAY  (* OPTIONAL *)
  where type vector = Real{N}Vector.vector
  where type elem = Real{N}.real

The MONO_ARRAY signature is a generic interface to monomorphic arrays, mutable sequences with constant-time access and update. Monomorphic arrays allow more compact representations than the analogous polymorphic arrays over the same element type.

Arrays have a special equality property: two arrays are equal if they are the same array, i.e., created by the same call to a primitive array constructor such as array, fromList, etc.; otherwise they are not equal. This also holds for arrays of zero length.


Interface

eqtype array
type elem
type vector
val maxLen : int
val array : int * elem -> array
val fromList : elem list -> array
val tabulate : int * (int -> elem) -> array
val length : array -> int
val sub : array * int -> elem
val update : array * int * elem -> unit
val vector : array -> vector
val copy    : {src : array, dst : array, di : int} -> unit
val copyVec : {src : vector, dst : array, di : int} -> unit

val appi : (int * elem -> unit) -> array -> unit
val app  : (elem -> unit) -> array -> unit
val modifyi : (int * elem -> elem) -> array -> unit
val modify  : (elem -> elem) -> array -> unit
val foldli : (int * elem * 'b -> 'b-> 'b -> array -> 'b
val foldri : (int * elem * 'b -> 'b-> 'b -> array -> 'b
val foldl  : (elem * 'b -> 'b-> 'b -> array -> 'b
val foldr  : (elem * 'b -> 'b-> 'b -> array -> 'b
val findi : (int * elem -> bool)
              -> array -> (int * elem) option
val find  : (elem -> bool) -> array -> elem option
val exists : (elem -> bool) -> array -> bool
val all : (elem -> bool) -> array -> bool
val collate : (elem * elem -> order)
                -> array * array -> order

Description

type vector
The corresponding monomorphic vector type. We denote the length of a vector vec of type vector by |vec|.

val maxLen : int
The maximum length of arrays supported by this implementation. Attempts to create larger arrays will result in the Size exception being raised.

array (n, init)
creates a new array of length n; each element is initialized to the value init. If n < 0 or maxLen < n, then the Size exception is raised.

fromList l
creates a new array from l, whose length is length l and with the i(th) element of l used as the i(th) element of the array. If the length of the list is greater than maxLen, then the Size exception is raised.

tabulate (n, f)
creates an array of n elements, where the elements are defined in order of increasing index by applying f to the element's index. This is equivalent to the expression:
fromList (List.tabulate (n, f))
If n < 0 or maxLen < n, then the Size exception is raised.

length arr
returns |arr|, the number of elements in the array arr.

sub (arr, i)
returns the i(th) element of the array arr. If i < 0 or |arr| <= i, then the Subscript exception is raised.

update (arr, i, x)
sets the i(th) element of the array arr to x. If i < 0 or |arr| <= i, then the Subscript exception is raised.

vector arr
generates a vector from arr. Specifically, if vec is the resulting vector, we have |vec| = |arr| and, for 0 <= i < |arr|, element i of vec is sub (arr, i).

copy {src, dst, di}
copyVec {src, dst, di}
These functions copy the entire array or vector src into the array dst, with the i(th) element in src, for 0 <= i < |src|, being copied to position di + i in the destination array. If di < 0 or if |dst| < di+|src|, then the Subscript exception is raised.
Implementation note:

In copy, if dst and src are equal, we must have di = 0 to avoid an exception, and copy is then the identity.



appi f arr
app f arr
These apply the function f to the elements of an array in left to right order (i.e., increasing indices). The more general appi function supplies both the element and the element's index to the function f. The expression app f arr is equivalent to:
      appi (f o #2) arr
      


modifyi f arr
modify f arr
These apply the function f to the elements of an array in left to right order (i.e., increasing indices), and replace each element with the result of applying f. The more general modifyi function supplies both the element and the element's index to the function f. The expression modify f arr is equivalent to:
      modifyi (f o #2) arr
      


foldli f init arr
foldri f init arr
foldl f init arr
foldr f init arr
These fold the function f over all the elements of an array, using the value init as the initial value. The functions foldli and foldl apply the function f from left to right (increasing indices), while the functions foldri and foldr work from right to left (decreasing indices). The more general functions foldli and foldri supply f with the array index of the corresponding element.

The indexed versions could be implemented as:

fun foldli f init seq = let
      val len = length seq
      fun loop (i, b) =
            if i = len then b
            else loop(i+1,f(i,sub(seq,i),b))
      in
        loop(0,init)
      end

fun foldri f init seq = let
      val len = length seq
      fun loop (i, b) =
            if i = ~1 then b
            else loop(i-1,f(i,sub(seq,i),b))
      in
        loop(len-1,init)
      end

The expression foldl f init arr is equivalent to:

foldli (fn (_, a, x) => f(a, x)) init arr
The analogous equivalences hold for foldri and foldr.

findi f arr
find f arr
These apply f to each element of the array arr, from left to right (i.e., increasing indices), until a true value is returned. If this occurs, the functions return the element; otherwise, they return NONE. The more general version findi also supplies f with the array index of the element and, upon finding an entry satisfying the predicate, returns that index with the element.

exists f arr
applies f to each element x of the array arr, from left to right (i.e., increasing indices), until f x evaluates to true; it returns true if such an x exists and false otherwise.

all f arr
applies f to each element x of the array arr, from left to right (i.e., increasing indices), until f x evaluates to false; it returns false if such an x exists and true otherwise. It is equivalent to not(exists (not o f) arr)).

collate f (a1, a2)
performs lexicographic comparison of the two arrays using the given ordering f on elements.

See Also

Array, MONO_ARRAY_SLICE, MONO_VECTOR, MONO_VECTOR_SLICE

Discussion

If an implementation provides a structure matching MONO_ARRAY for some element type ty, it must provide the corresponding monomorphic structure matching MONO_VECTOR with the vector types in the two structures identified.


[ Top | Parent | Contents | Index | Root ]

Generated October 02, 2003
Last Modified June 11, 2000
Comments to John Reppy.


This document may be distributed freely over the internet as long as the copyright notice and license terms below are prominently displayed within every machine-readable copy.

Copyright © 2003 AT&T and Lucent Technologies. All rights reserved.

Permission is granted for internet users to make one paper copy for their own personal use. Further hardcopy reproduction is strictly prohibited. Permission to distribute the HTML document electronically on any medium other than the internet must be requested from the copyright holders by contacting the editors. Printed versions of the SML Basis Manual are available from Cambridge University Press. To order, please visit www.cup.org (North America) or www.cup.cam.ac.uk (outside North America).