(********************************************************************)
(*  OCaml code from the book ``Learn Programming with OCaml''       *)
(*  See https://usr.lmf.cnrs.fr/lpo/                                *)
(*                                                                  *)
(*  Sylvain Conchon and Jean-Christophe Filliâtre                   *)
(*  Copyright 2025 Université Paris-Saclay and CNRS                 *)
(*                                                                  *)
(*  Openly licensed via CC BY SA 4.0                                *)
(*  See https://creativecommons.org/licenses/by-sa/4.0/deed.en      *)
(********************************************************************)

(* Program 31 on page 202
   Persistent Arrays *)

type 'a t = 'a data ref
and 'a data =
  | Arr of 'a array
  | Diff of int * 'a * 'a t

let init n f = ref (Arr (Array.init n f))

let rec reroot pa = match !pa with
  | Arr a ->
      a
  | Diff (i, v, pa') ->
      let a = reroot pa' in
      let old = a.(i) in
      a.(i) <- v;
      pa := Arr a;
      pa' := Diff (i, old, pa);
      a

let length pa = Array.length (reroot pa)

let get pa i = (reroot pa).(i)

let iteri f pa = Array.iteri f (reroot pa)

let set pa i v =
  let a = reroot pa in
  let old = a.(i) in
  a.(i) <- v;
  let res = ref (Arr a) in
  pa := Diff (i, old, res);
  res

This document was generated using caml2html