home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Moscow ML 1.42 / lib / Array.sig < prev    next >
Encoding:
Text File  |  1997-08-18  |  6.6 KB  |  159 lines  |  [TEXT/Moml]
  1. (* Array -- SML Basis Library *)
  2.  
  3. signature Array = sig
  4.  
  5. prim_EQtype 'a array
  6.  
  7. val maxLen   : int
  8.  
  9. val array    : int * '_a -> '_a array
  10. val tabulate : int * (int -> '_a) -> '_a array
  11. val fromList : '_a list -> '_a array
  12.  
  13. val length  : 'a array -> int
  14. val sub     : 'a array * int -> 'a
  15. val update  : 'a array * int * 'a  -> unit
  16. val extract : 'a array * int * int option -> 'a Vector.vector
  17.  
  18. val copy    : {src: 'a array,  si: int, len: int option,
  19.                dst: 'a array, di: int} -> unit
  20. val copyVec : {src: 'a vector, si: int, len: int option, 
  21.                dst: 'a array, di: int} -> unit
  22.  
  23. val app     : ('a -> unit) -> 'a array -> unit
  24. val foldl   : ('a * 'b -> 'b) -> 'b -> 'a array -> 'b
  25. val foldr   : ('a * 'b -> 'b) -> 'b -> 'a array -> 'b
  26. val modify  : ('a -> 'a) -> 'a array -> unit
  27.  
  28. val appi    : (int * 'a -> unit) -> 'a array * int * int option -> unit
  29. val foldli  : (int * 'a * 'b -> 'b) -> 'b -> 'a array * int * int option -> 'b
  30. val foldri  : (int * 'a * 'b -> 'b) -> 'b -> 'a array * int * int option -> 'b
  31. val modifyi : (int * 'a -> 'a) -> 'a array * int * int option -> unit
  32. end
  33.  
  34. (* Type [ty array] is the type of one-dimensional, mutable, zero-based
  35.    constant-time-access arrays with elements of type ty.  Type ty
  36.    array admits equality even if ty does not.  Arrays a1 and a2 are
  37.    equal if both were created by the same call to a primitive (array,
  38.    tabulate, fromList).
  39.  
  40.    Some functions work on a *slice* of an array:
  41.  
  42.    The slice (a, i, SOME n) denotes the subarray a[i..i+n-1].  That is,
  43.    a[i] is the first element of the slice, and n is the length of the
  44.    slice.  Valid only if 0 <= i <= i+n <= length a.
  45.  
  46.    The slice (a, i, NONE) denotes the subarray a[i..length a-1].  That
  47.    is, the slice denotes the suffix of the array starting at i.  Valid
  48.    only if 0 <= i <= length a.  Equivalent to (a, i, SOME(length a - i)).
  49.  
  50.        slice             meaning 
  51.        ----------------------------------------------------------
  52.        (a, 0, NONE)      the whole array              a[0..len-1]   
  53.        (a, 0, SOME n)    a left subarray (prefix)     a[0..n-1]
  54.        (a, i, NONE)      a right subarray (suffix)    a[i..len-1]
  55.        (a, i, SOME n)    a general slice              a[i..i+n-1] 
  56.  
  57.    [maxLen] is the maximal number of elements in an array.
  58.  
  59.    [array(n, x)] returns a new array of length n whose elements are all x.
  60.    Raises Size if n<0 or n>maxLen.
  61.  
  62.    [tabulate(n, f)] returns a new array of length n whose elements
  63.    are f 0, f 1, ..., f (n-1), created from left to right.  Raises
  64.    Size if n<0 or n>maxLen.
  65.  
  66.    [fromList xs] returns an array whose elements are those of xs.
  67.    Raises Size if length xs > maxLen.
  68.  
  69.    [array0] is a zero-length array.
  70.  
  71.    [length a] returns the number of elements in a.
  72.  
  73.    [sub(a, i)] returns the i'th element of a, counting from 0.  
  74.    Raises Subscript if i<0 or i>=length a.  To make `sub' infix, use
  75.    the declaration 
  76.                              infix 9 sub
  77.  
  78.    [update(a, i, x)] destructively replaces the i'th element of a by x.
  79.    Raises Subscript if i<0 or i>=length a.
  80.  
  81.    [extract(a, i, NONE)] returns a vector of the elements a[i..length a-1] 
  82.    of a.  Raises Subscript if i<0 or i>length a.
  83.  
  84.    [extract(a, i, SOME len)] returns a vector of the elements a[i..i+len-1] 
  85.    of a.  Raises Subscript if i<0 or len<0 or i+len>length a or
  86.    len>Vector.maxLen.
  87.  
  88.    [copy{src, si, len, dst, di}] destructively copies the slice
  89.    (src, si, len) to dst, starting at index di.  More precisely:
  90.    If len=NONE and n=length src, it copies src[si..n-1] to dst[di..di+n-si].
  91.    If len=SOME k, it copies src[si..si+k-1] to dst[di..di+k-1].  
  92.    Works also if src and dst are the same and the segments overlap.
  93.    Raises Subscript if si < 0 or di < 0, 
  94.    or if len=NONE and di + length src - si > length dst,
  95.    or if len=SOME k and k < 0 or si + k > length src or di + k > length dst.
  96.  
  97.    [copyVec{src, si, len, dst, di}] destructively copies the slice
  98.    (src, si, len) to dst, starting at index di.  More precisely:
  99.    If len=NONE and n=length src, it copies src[si..n-1] to dst[di..di+n-si].
  100.    If len=SOME k, it copies src[si..si+k-1] to dst[di..di+k-1].  
  101.    Works also if src and dst are the same and the segments overlap.
  102.    Raises Subscript if si < 0 or di < 0, 
  103.    or if len=NONE and di + length src - si > length dst,
  104.    or if len=SOME k and k < 0 or si + k > length src or di + k > length dst.
  105.  
  106.    [foldl f e a] folds function f over a from left to right.  That is,
  107.    computes f(a[len-1], f(a[len-2], ..., f(a[1], f(a[0], e)) ...)),
  108.    where len is the length of a.
  109.  
  110.    [foldr f e a] folds function f over a from right to left.  That is,
  111.    computes f(a[0], f(a[1], ..., f(a[len-2], f(a[len-1], e)) ...)),
  112.    where len is the length of a.
  113.  
  114.    [app f a] applies f to a[j] for j=0,1,...,length a-1.
  115.  
  116.    [modify f a] applies f to a[j] and updates a[j] with the result
  117.    f(a[j]) for j=0,1,...,length a-1. 
  118.  
  119.    The following iterators generalize the above ones in two ways:
  120.  
  121.     . the index j is also being passed to the function being iterated;
  122.     . the iterators work on a slice (subarray) of an array.
  123.  
  124.    [foldli f e (a, i, SOME n)] folds function f over the subarray
  125.    a[i..i+n-1] from left to right.  That is, computes 
  126.    f(i+n-1, a[i+n-1], f(..., f(i+1, a[i+1], f(i, a[i], e)) ...)).  
  127.    Raises Subscript if i<0 or n<0 or i+n > length a.
  128.  
  129.    [foldli f e (a, i, NONE)] folds function f over the subarray
  130.    a[i..len-1] from left to right, where len =  length a.  That is, 
  131.    computes f(len-1, a[len-1], f(..., f(i+1, a[i+1], f(i, a[i], e)) ...)).  
  132.    Raises Subscript if i<0 or i > length a.
  133.  
  134.    [foldri f e (a, i, SOME n)] folds function f over the subarray
  135.    a[i..i+n-1] from right to left.  That is, computes 
  136.    f(i, a[i], f(i+1, a[i+1], ..., f(i+n-1, a[i+n-1], e) ...)).
  137.    Raises Subscript if i<0 or n<0 or i+n > length a.
  138.  
  139.    [foldri f e (a, i, NONE)] folds function f over the subarray
  140.    a[i..len-1] from right to left, where len = length a.  That is, 
  141.    computes f(i, a[i], f(i+1, a[i+1], ..., f(len-1, a[len-1], e) ...)).
  142.    Raises Subscript if i<0 or i > length a.
  143.  
  144.    [appi f (a, i, SOME n)] applies f to successive pairs (j, a[j]) for
  145.    j=i,i+1,...,i+n-1.  Raises Subscript if i<0 or n<0 or i+n > length a.
  146.  
  147.    [appi f (a, i, NONE)] applies f to successive pairs (j, a[j]) for
  148.    j=i,i+1,...,len-1, where len = length a.  Raises Subscript if i<0
  149.    or i > length a.
  150.  
  151.    [modifyi f (a, i, SOME n)] applies f to (j, a[j]) and updates a[j]
  152.    with the result f(j, a[j]) for j=i,i+1,...,i+n-1.  Raises Subscript
  153.    if i<0 or n<0 or i+n > length a.
  154.  
  155.    [modifyi f (a, i, NONE)] applies f to (j, a[j]) and updates a[j]
  156.    with the result f(j, a[j]) for j=i,i+1,...,len-1.  Raises Subscript
  157.    if i<0 or i > length a.
  158. *)
  159.