Re: [Caml-list] The Implicit Accumulator: a design pattern using optional arguments

["Quôc Peyrot" <chojin@lrde.epita.fr>]

On Jun 27, 2007, at 2:14 PM, Jon Harrop wrote:

>
> I can't find the thread where we were talking about design patterns  
> recently
> but I'd like to note a design pattern that works nicely in OCaml.  
> I'll call
> it "The Implicit Accumulator".
>
> ML programmers often use nested auxiliary functions or separate  
> functions to
> handle base cases. For example, writing rev in terms of rev_append:
>
> # let rec rev_append l1 l2 = match l1 with
>     | [] -> l2
>     | a :: l -> rev_append l (a :: l2);;
> val rev_append : 'a list -> 'a list -> 'a list = <fun>
> # let rev l = rev_append l [];;
> val rev : 'a list -> 'a list = <fun>
>
> Provided performance is unimportant, you can make the accumulator  
> implicit in
> OCaml by specifying the default value in an optional argument  
> instead of
> having a separate function:
>
> # let rec rev ?(back=[]) = function
>     | [] -> back
>     | h::t -> rev ~back:(h::back) t;;
> val rev : ?back:'a list -> 'a list -> 'a list = <fun>

Could you be more specifics about the performance hit?

> When you don't want the auxiliary (rev_append) function, I think  
> this style
> results in shorter and clearer code. I used it in the "search"  
> function of my
> Sudoku solver, for example:

It's funny that you speak about this, because I recently (few days  
ago) used
a pattern similar to yours, but to actually improve performances.
I had something like that (which is quite different than my actual  
code, but
the idea is the same):

let encrypt str =
   let len = String.length str in
   let encrypted = String.create len in
   (* ... *)
   encrypted

(*...*)
for i = 0 to 10000000 do
   let encrypted = encrypt str in
   (* do something on the result *)
done

Which is slow due to the string allocation happening each time we  
call "encrypt"

So I rewrote it like that:

let encrypt ?encrypted str =
   let len = String.length str in
   let result = match encrypted with
     | None -> String.create len
     | Some s -> s
   in
   (* ... *)
   result

(* ... *)
let encrypted = String.create (String.length str) in
for i = 0 to 1000000000 do
   let encrypted = encrypt ~encrypted str in
   (* ... *)
done

Which gave me more than a 2x speedup while still being able to call a  
simple:
let encrypted = encrypt str
during normal usage

I was quite happy with this solution, but maybe there is something  
more elegant to do?
(I'm still in the process of learning good optimization patterns in  
ocaml which preserve readability)

-- 
Best Regards,
Quôc