fun iterdn n m s f = if n<m then s else iterdn (n-1) m (f(n,s)) f

signature HEAP = sig
    exception Address
    exception OutOfMemory
    type address = int
    type index = int
    val new     : int -> address  (* Address, OutOfMemory *)
    val sub     : address -> index -> int  (* Address *) 
    val update  : address -> index -> int -> unit  (* Address *) 
    val release : int -> unit
    val show    : unit -> (address * int) list
end
structure Heap :> HEAP = struct
    val size = 1000
    val array = Array.array(size,~1)
    val lar = ref ~1  (* last allocated address *)
    exception Address
    exception OutOfMemory
    type address = int
    type index = int
    fun new n = if n<1 then raise Address
                else if !lar+n >= size then raise OutOfMemory
                     else #1(!lar+1, lar:= !lar+n)
    fun check a = if a<0 orelse a > !lar then raise Address else a
    fun sub a i = Array.sub(array, check(a+i))
    fun update a i x = Array.update(array, check(a+i), x)
    fun release a = lar:= (if a=0 then a else check a) - 1
    fun show () = iterdn (!lar) 0 nil 
                  (fn (a,es) => (a, Array.sub(array,a)) :: es)
end 

open Heap  

fun new' xs = let
    val a = new (length xs)
in
    foldl (fn (x,i) => (update a i x ; i+1)) 0 xs ;
    a
end

fun putList nil = ~1
  | putList (x::xr) = new'[x, putList xr]

fun getList a = if a = ~1 then nil
		else sub a 0 :: getList(sub a 1)

fun updateList a n x = if a = ~1 orelse n<0 then raise Subscript
		       else if n=0 then update a 0 x
			    else updateList (sub a 1) (n-1) x