(* Author: Claudio Vittorio Russo, Department of Computer Science, University of Edinburgh, Scotland Copyright: 1998. All rights reserved.*)(* The signature Array specifies a structure implementing fixed-size arrays.*)signature Array = sig type 'a array; val init:'a -> ('a array); val sub: ('a array) -> int -> 'a; val update: ('a array) -> int -> 'a -> ('a array) end;(* The structure ArrayZero implementing arrays of size 2^0. *)structure ArrayZero = struct type 'a array = 'a; val init = fn x => x; val sub = fn a => fn i => a; val update = fn a => fn i => fn x => x end;(* The functor ArraySucc mapping an implementation of arrays of size 2^n to an implementation of arrays of size 2^(n+1)*)functor ArraySucc (A:Array) = struct type 'a array = ('a A.array) * ('a A.array); val init = fn x => (A.init x, A.init x) val sub = fn (even,odd) => fn i => if (i mod 2) = 0 then A.sub even (i div 2) else A.sub odd (i div 2); val update = fn (even,odd) => fn i => fn x => if (i mod 2) = 0 then (A.update even (i div 2) x, odd) else (even, A.update odd (i div 2) x) end;(* The function mkArray: applying mkArray to an integer n (n >=0) returns an abstract implementation of arrays of size 2^n *)fun mkArray 0 = [structure ArrayZero as Array] | mkArray n = let structure A as Array = mkArray (n-1) in [structure ArraySucc(A) as Array] end;fun two 0 = 1| two n = 2 * two (n-1);val n = 10;val max = two n;fun iter f b 0 = b | iter f b n = f (iter f b (n-1)) n;structure A as Array = mkArray n;val a = A.init 0;(* test every entry is initialised to zero *)val test1 = if iter (fn l => fn n => l andalso (A.sub a n) = 0) true max then "OK" else "FAIL";val a = iter (fn a => fn n => A.update a n n) a max;val l = iter (fn l => fn n => (A.sub a n)::l) [] max(* test every entry has been updated *)val test2 = if iter (fn l => fn n => l andalso (A.sub a n) = n) true max then "OK" else "FAIL";
(* Author: Claudio Vittorio Russo, Department of Computer Science, University of Edinburgh, Scotland
Copyright: 1998. All rights reserved.
*)
(* The signature Array specifies a structure implementing fixed-size arrays.
*)
signature Array =
sig type 'a array;
val init:'a -> ('a array);
val sub: ('a array) -> int -> 'a;
val update: ('a array) -> int -> 'a -> ('a array)
end;
(* The structure ArrayZero implementing arrays of size 2^0. *)
structure ArrayZero =
struct
type 'a array = 'a;
val init = fn x => x;
val sub = fn a => fn i => a;
val update = fn a => fn i => fn x => x
end;
(* The functor ArraySucc mapping an implementation
of arrays of size 2^n to an implementation of arrays of size 2^(n+1)
*)
functor ArraySucc (A:Array) =
struct
type 'a array = ('a A.array) * ('a A.array);
val init = fn x => (A.init x, A.init x)
val sub = fn (even,odd) => fn i =>
if (i mod 2) = 0
then A.sub even (i div 2)
else A.sub odd (i div 2);
val update = fn (even,odd) => fn i => fn x =>
if (i mod 2) = 0
then (A.update even (i div 2) x, odd)
else (even, A.update odd (i div 2) x)
end;
(* The function mkArray: applying mkArray to an integer n
(n >=0) returns an abstract implementation of arrays of size 2^n
*)
fun mkArray 0 = [structure ArrayZero as Array]
| mkArray n = let structure A as Array = mkArray (n-1)
in
[structure ArraySucc(A) as Array]
end
;
fun two 0 = 1
| two n = 2 * two (n-1);
val n = 10;
val max = two n;
fun iter f b 0 = b | iter f b n = f (iter f b (n-1)) n;
structure A as Array = mkArray n;
val a = A.init 0;
(* test every entry is initialised to zero *)
val test1 = if iter (fn l => fn n => l andalso (A.sub a n) = 0) true max
then "OK"
else "FAIL";
val a = iter (fn a => fn n => A.update a n n) a max;
val l = iter (fn l => fn n => (A.sub a n)::l) [] max
(* test every entry has been updated *)
val test2 = if iter (fn l => fn n => l andalso (A.sub a n) = n) true max
then "OK"
else "FAIL";