From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id E2CE5BBAF for ; Fri, 23 Oct 2009 21:56:01 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnIBAC+n4UrRVd7JkGdsb2JhbACCIjGOf4kcPwEBAQEJCQwHEwOuFYE7hlKIaAEDAwWEOgQ X-IronPort-AV: E=Sophos;i="4.44,614,1249250400"; d="scan'208";a="36911196" Received: from mail-pz0-f201.google.com ([209.85.222.201]) by mail3-smtp-sop.national.inria.fr with ESMTP; 23 Oct 2009 21:56:00 +0200 Received: by pzk39 with SMTP id 39so6461248pzk.15 for ; Fri, 23 Oct 2009 12:55:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:date:message-id:subject :from:to:content-type; bh=lLJiX8fSLjPEwRSRk08mS2oxXg2Q+UcvjU21vjl4csU=; b=cCou6FVls03PUKiSTDXat6X/4X7dzYTw8NoEgm3KuuEEZXuv5lLjeQnga11o3jsP4w X0SGxqvEu1ve8+t0hgQwbSlrdtTlOWQUGUc5L7WsD89B7WNHmMp4JlzhqXSEM+uPRjgM ZD8YaYfkj7UW0/Yay1jSXl1EanOOgMRNdB1Ws= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:date:message-id:subject:from:to:content-type; b=OResYk4UjgURhou1/uLnpSIdzGtgOsUbbQcTcWXr8BdBElhgLmYr9nMpTKh9+TeQKp uFS9qbG2b5fFbUH0WZH+NTRQPZK78ZIavrWLhDuUINKh8wRZoykrBY3cXTF5Hkmly6tM ShkkN2Sd4l1yHOiaUw02cZtGHHEyZ7V4leGfA= MIME-Version: 1.0 Received: by 10.141.50.4 with SMTP id c4mr1824816rvk.291.1256327759473; Fri, 23 Oct 2009 12:55:59 -0700 (PDT) Date: Fri, 23 Oct 2009 12:55:59 -0700 Message-ID: Subject: tip for tail recursive map From: pikatchou pokemon To: caml-list@yquem.inria.fr Content-Type: multipart/alternative; boundary=000e0cd1511cd32d8f04769f9915 X-Spam: no; 0.00; recursive:01 ocaml:01 recursive:01 closures:01 closures:01 stack:01 stack:01 rec:01 rec:01 functions:01 functions:01 tail:01 tail:01 short:01 short:01 --000e0cd1511cd32d8f04769f9915 Content-Type: text/plain; charset=ISO-8859-1 hi everyone, I know this topic has been discussed several times, but I don't think I have seen the solution I use for functions of the List module which are not tail recursive. I thought sharing the tip could be nice. I will take an example, List.map. When rewritten in CPS map becomes: let rec map k f = function | [] -> k [] | x :: rl -> map (fun res -> k ((f x) :: res)) f rl The trick consists in "unfolding" this function manually, in order to allocate less closures: let rec map k f = function | [] -> k [] | x :: rl -> let x = f x in match rl with | [] -> k [x] | y :: rl -> let y = f y in match rl with | [] -> k [x ; y] | z :: rl -> let z = f z in match rl with | [] -> k [x ; y ; z] | t :: rl -> let t = f t in map (fun res -> k (x :: y :: z :: t :: res)) f rl Performances are roughly equivalent to List.map on short and medium size lists (at least on my machine), but as it's tail recursive it doesn't blow the stack on long lists. Please note that performances are not as good as the "Obj.magic" version of map on very long lists. However, this does the job for me, I have a fast map on short and medium size lists (< 10000 elements) but still working on larger ones. Hope this helps ! --000e0cd1511cd32d8f04769f9915 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable hi everyone,

I know this topic has been discussed several times, but= I don't think I have seen the solution I use for functions of the List= module which are not tail recursive.
I thought sharing the tip could be= nice.
I will take an example, List.map.
When rewritten in CPS map becomes:
=
let rec map k f =3D function
=A0 | []=A0=A0=A0 -> k []
=A0 | x= :: rl -> map (fun res -> k ((f x) :: res)) f rl

The trick con= sists in "unfolding" this function manually, in order to allocate= less closures:

let rec map k f =3D function
=A0 | [] -> k []
=A0 | x :: rl -&= gt;
=A0=A0=A0=A0=A0 let x =3D f x in
=A0=A0=A0=A0=A0 match rl with=A0=A0=A0=A0=A0 | [] -> k [x]
=A0=A0=A0=A0=A0 | y :: rl ->
=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 let y =3D f y in
=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0 match rl with
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 | [] -> k [x ; y]
=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0 | z :: rl ->
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0 let z =3D f z in
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0 match rl with
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0 | [] -> k [x ; y ; z]
=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 | t :: rl ->
=A0=A0=A0 =A0=A0=A0 =A0=A0=A0 let t =3D f t in
=A0=A0=A0 =A0=A0=A0 =A0= =A0=A0 map (fun res -> k (x :: y :: z :: t :: res)) f rl

Performa= nces are roughly equivalent to List.map on short and medium size lists (at = least on my machine), but as
it's tail recursive it doesn't blow= the stack on long lists.
Please note that performances are not as good as the "Obj.magic" = version of map on very long lists.
However, this does the job for me, I = have a fast map on short and medium size lists (< 10000 elements) but still working on larger ones.

Hope this helps !
--000e0cd1511cd32d8f04769f9915--