On Thu, 23 May 2013 09:34:32 -0700
Edgar Friendly <notifications@github.com> wrote:

> > @@ -639,11 +645,30 @@ let replace ~str ~sub ~by =
> >  
> >  
> >  let nreplace ~str ~sub ~by =
> > -  let parts = nsplit str ~by:sub in
> > -  String.concat by parts
> > +   if sub = "" then invalid_arg "nreplace: cannot replace all
> > empty substrings" ;
> > +   let find_sub pos = try find_from str pos sub with Not_found ->
> > -1 in  
> > +   (* allows loop to be tail recursive *)
> > +   let sublen = length sub in
> > +   let strlen = length str in
> > +   let buffer = Buffer.create strlen in
> 
> We might be able to pre-compute the size of this buffer and use a
> string instead, although at the cost of some temp data structure
> recording the work to be done.  Would need to benchmark to find out
> if worthwhile.

I have not much experience with benchmarking, but a possible
implementation:

let nreplace ~str ~sub ~by =
  let strlen = String.length str
  and sublen = String.length sub
  and bylen  = String.length by in

  (* compare to sub at position i in str *)
  let compare i =
    let rec compare' j =
      if j >= sublen then true
      else if str.[i+j] <> sub.[j] then false
      else compare' (j+1)
    in
    compare' 0
  in
  (* collect all positions where we need to replace *)
  let rec collect todo i =
    if i >= strlen then todo
    else if compare i
    then collect (i::todo) (i+sublen)
    else collect todo (i+1)
  in
  let todo = collect [] 0 in

  (* create destination string *)
  let dst = String.create (strlen + List.length todo * (bylen - sublen)) in

  (* do the replacement *)
  let srci, dsti =
    (* todo is in reverse order, therefore fold right. *)
    List.fold_right
      begin fun i (srci,dsti) ->
        let skiplen = i-srci in
        String.blit str srci dst dsti skiplen;
        String.blit by 0 dst (dsti+skiplen) bylen;
        (srci+skiplen+sublen, dsti+skiplen+bylen)
      end
      todo
      (0,0)
  in
  assert (strlen - srci = String.length dst - dsti);
  String.blit str srci dst dsti (strlen - srci);
  dst