(* persistent arrays implemented in the usual way (Baker's method) *)

type t = data ref
and data =
  | Array of int array 
  | Diff of int * int * t
      
let create n v = ref (Array (Array.create n v))
let init n f = ref (Array (Array.init n f))
  
let rec get t i = match !t with
  | Array a -> a.(i)
  | Diff (j, v, t') -> if i == j then v else get t' i
      
let set t i v = match !t with
  | Array a as n ->
      let old = a.(i) in
      a.(i) <- v;
      let res = ref n in
      t := Diff (i, old, res);
      res
  | Diff _ ->
      ref (Diff (i, v, t))


(** experiment with maps for the diffs -> does not work 

module Ptmap = Map.Make(struct type t = int let compare = compare end)

type t = data ref
and data =
  | Array of int array 
  | Diff of int Ptmap.t * t
      
let create n v = ref (Array (Array.create n v))
let init n f = ref (Array (Array.init n f))
  
let rec get t i = match !t with
  | Array a -> a.(i)
  | Diff (m, t') -> (try Ptmap.find i m with Not_found -> get t' i)
      
let set t i v = match !t with
  | Array a ->
      let old = a.(i) in
      a.(i) <- v;
      let res = ref (Array a) in
      t := Diff (Ptmap.add i old Ptmap.empty, res);
      res
  | Diff (m, t') ->
      ref (Diff (Ptmap.add i v m, t'))

**)