From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <chojin@lrde.epita.fr>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled 
	version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38])
	by yquem.inria.fr (Postfix) with ESMTP id AFC11BC6B
	for <caml-list@yquem.inria.fr>; Wed, 27 Jun 2007 15:18:10 +0200 (CEST)
Received: from smtp20.orange.fr (smtp20.orange.fr [80.12.242.26])
	by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5RDIAJF023818
	for <caml-list@yquem.inria.fr>; Wed, 27 Jun 2007 15:18:10 +0200
Received: from me-wanadoo.net (localhost [127.0.0.1])
	by mwinf2026.orange.fr (SMTP Server) with ESMTP id 315591C00092
	for <caml-list@yquem.inria.fr>; Wed, 27 Jun 2007 15:18:10 +0200 (CEST)
Received: from [192.168.1.162] (ALagny-153-1-98-23.w90-3.abo.wanadoo.fr [90.3.145.23])
	by mwinf2026.orange.fr (SMTP Server) with ESMTP id 0278D1C00088
	for <caml-list@yquem.inria.fr>; Wed, 27 Jun 2007 15:18:09 +0200 (CEST)
X-ME-UUID: 20070627131810102.0278D1C00088@mwinf2026.orange.fr
Mime-Version: 1.0 (Apple Message framework v752.2)
In-Reply-To: <200706271314.35134.jon@ffconsultancy.com>
References: <200706271314.35134.jon@ffconsultancy.com>
Content-Type: text/plain; charset=ISO-8859-1; delsp=yes; format=flowed
Message-Id: <1A1D6F56-B3DB-4552-969C-9859482175AC@lrde.epita.fr>
Content-Transfer-Encoding: quoted-printable
From: =?ISO-8859-1?Q?Qu=F4c_Peyrot?= <chojin@lrde.epita.fr>
Subject: Re: [Caml-list] The Implicit Accumulator: a design pattern using optional arguments
Date: Wed, 27 Jun 2007 15:18:07 +0200
To: caml-list@yquem.inria.fr
X-Mailer: Apple Mail (2.752.2)
X-Miltered: at discorde with ID 46826392.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; lrde:01 ocaml:01 val:01 val:01 ocaml:01 solver:01 rewrote:01 speedup:01 2007,:98 wrote:01 rec:01 rec:01 clearer:01 caml-list:01 functions:01 


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

>
> I can't find the thread where we were talking about design patterns =20=

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

Could you be more specifics about the performance hit?

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

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

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

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

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

So I rewrote it like that:

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

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

Which gave me more than a 2x speedup while still being able to call a =20=

simple:
let encrypted =3D encrypt str
during normal usage

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

--=20
Best Regards,
Qu=F4c