From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 25F0E7FACD for ; Mon, 29 Sep 2014 06:09:51 +0200 (CEST) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of anthony.tavener@gmail.com) identity=pra; client-ip=209.85.220.170; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="anthony.tavener@gmail.com"; x-sender="anthony.tavener@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of anthony.tavener@gmail.com designates 209.85.220.170 as permitted sender) identity=mailfrom; client-ip=209.85.220.170; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="anthony.tavener@gmail.com"; x-sender="anthony.tavener@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-vc0-f170.google.com) identity=helo; client-ip=209.85.220.170; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="anthony.tavener@gmail.com"; x-sender="postmaster@mail-vc0-f170.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtcBAB7bKFTRVdyqm2dsb2JhbABgg2FNDoJ9tkOPHYFoh1MCfAgWAREBAQEBAQYLCwkULIQDAQEBAwESEQQZARsSCwEDAQsGBQsNDR0CAiEBAREBBQEKEgYTEgIOiAcBAwkIDZ0/boswgXKDEIhBChknAwpnhjkBEQEFDo1ggiwEB4J4gVMFhRQCA4Y2hxuDNYI+gjuCEIFijTOEVhgphTMeLwEBgkgBAQE X-IPAS-Result: AtcBAB7bKFTRVdyqm2dsb2JhbABgg2FNDoJ9tkOPHYFoh1MCfAgWAREBAQEBAQYLCwkULIQDAQEBAwESEQQZARsSCwEDAQsGBQsNDR0CAiEBAREBBQEKEgYTEgIOiAcBAwkIDZ0/boswgXKDEIhBChknAwpnhjkBEQEFDo1ggiwEB4J4gVMFhRQCA4Y2hxuDNYI+gjuCEIFijTOEVhgphTMeLwEBgkgBAQE X-IronPort-AV: E=Sophos;i="5.04,617,1406584800"; d="scan'208";a="81208944" Received: from mail-vc0-f170.google.com ([209.85.220.170]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 29 Sep 2014 06:09:49 +0200 Received: by mail-vc0-f170.google.com with SMTP id hy10so661792vcb.29 for ; Sun, 28 Sep 2014 21:09:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=Hm+aQjdRMYN4qS7OnDS+9bHfICy/XFeTcKB6z9LMx3E=; b=BXzkw0o0OD3P2D8/t9UOqYNpZS6U17aic1jjaSssxbgTLxfLT+RmqvCpitSo2EVyYh IZc7loGSQrgQfIXtHojNS6fpTUFwsAhh6ZSLZOIYqmC7kHGCm2WxoGL24dfQLl6HJrSW 5gG2ERl25AmrcWqeCNoZBbhI6kLSgbTsxnugJVGWE50SU+lkdun4vpVRwqNAPplLLRqq s1LDzhLNIHaxVeRIxiolnymm5O4KavVF84BH6dvghqQqNxOwHvr3dljkF2MiX6uI8kjD 5CEq7OAW5iT8Lw1eEgHXS7dAvB9gQQTlVigxDWaesqjBfk25DNEWgSeurvpVAE4a22sZ T2sQ== MIME-Version: 1.0 X-Received: by 10.52.184.7 with SMTP id eq7mr23457958vdc.0.1411963788388; Sun, 28 Sep 2014 21:09:48 -0700 (PDT) Received: by 10.220.159.133 with HTTP; Sun, 28 Sep 2014 21:09:48 -0700 (PDT) In-Reply-To: References: <87bnpzpm0l.fsf@gmail.com> Date: Sun, 28 Sep 2014 22:09:48 -0600 Message-ID: From: Anthony Tavener To: Shuai Wang Cc: Yaron Minsky , "caml-list@inria.fr" Content-Type: multipart/alternative; boundary=bcaec5485acc0aee5f05042c7071 Subject: Re: [Caml-list] Why List.map does not be implemented tail-recursively? --bcaec5485acc0aee5f05042c7071 Content-Type: text/plain; charset=UTF-8 A remark about the "reverse" list operations... I find that it often turns out that I'll have an even number of these reverse operations. So even if I need to maintain the final list order, it can be for free. For example, List.rev_map, followed by a List.rev_append... everything is tail-recursive without adding extra list-reversals, and the final order is maintained. On Sun, Sep 28, 2014 at 8:31 PM, Shuai Wang wrote: > Wow, List.rev_map f (List.rev li) looks very elegant, thank you all for > the helpful materials! I should definitely try Core lib soon. > > I have been working on a binary program analysis project for over half a > year in OCaml, and it is really enjoyable to write OCaml code! > hope I can open source the analysis tool eventually and contribute to the > community :) > > Best, > Shuai > > > > On Sun, Sep 28, 2014 at 4:26 PM, Yaron Minsky > wrote: > >> Indeed, the implementation from that post did make it into >> Core_kernel. Here's the link: >> >> >> https://github.com/janestreet/core_kernel/blob/release-112.01.00/lib/core_list.ml#L380 >> >> y >> >> On Sun, Sep 28, 2014 at 3:45 PM, Malcolm Matalka >> wrote: >> > https://blogs.janestreet.com/optimizing-list-map/ >> > >> > And from the horse's mouth: >> > >> > https://groups.google.com/forum/#!msg/fa.caml/YaLYqkpn928/1jdo8a0K6AEJ >> > >> > Shuai Wang writes: >> > >> >> Hello list, >> >> >> >> >> >> I am working on some stack_overflow exception in our recent project >> written >> >> in OCaml >> >> and eventually it turns out that this exception is thrown by List.map >> >> function. >> >> >> >> By seeing the source code of OCaml's List module >> >> < >> https://code.ohloh.net/file?fid=P5Us_txNCMHIhpdfML6OZ8QN4Zs&cid=Jigg8RAfQdg&s=ocaml%20list.ml&pp=0&fp=305967&fe=ml&ff=1&filterChecked=true&mp=1&ml=1&me=1&md=1#L3 >> >, >> >> it seems that map function >> >> does not be implemented tail-recursively: >> >> >> >> let rec map f = function >> >> [] -> [] >> >> | a::l -> let r = f a in r :: map f l >> >> >> >> >> >> >> >> So my question is: >> >> >> >> *Why would OCaml's implementation List.map like this? * >> >> >> >> In my humble option, it definitely should be written in a >> tail-recursive >> >> way, >> >> and it not, stack_overflow would be unavoidable. >> >> For example in order to handle the exception, >> >> I abandon the code using List.map and rewrite it into a tail-recursive >> help >> >> function. >> >> >> >> Best, >> >> Shuai >> > >> > -- >> > Caml-list mailing list. Subscription management and archives: >> > https://sympa.inria.fr/sympa/arc/caml-list >> > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners >> > Bug reports: http://caml.inria.fr/bin/caml-bugs >> > > --bcaec5485acc0aee5f05042c7071 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
A remark about the "reverse" list operations... = I find that it often turns out that I'll have an even number of these r= everse operations. So even if I need to maintain the final list order, it c= an be for free.

For example, List.rev_map, followed by a= List.rev_append... everything is tail-recursive without adding extra list-= reversals, and the final order is maintained.

On Sun, Sep 28, 2014 at 8:31 PM, Sh= uai Wang <wangshuai901@gmail.com> wrote:
Wow,=C2=A0List.rev_map f (List.rev li) looks very=C2=A0elegant, thank you all fo= r the helpful=C2=A0materials! I should definitely try Core lib soon.=

I have been working on a binary program analysis project = for over half a year in OCaml, and it is really enjoyable to write OCaml co= de!
hope I can open sourc= e the analysis tool eventually and=C2=A0contribute to the community :)

Best,
Shuai=C2=A0


On Sun, S= ep 28, 2014 at 4:26 PM, Yaron Minsky <yminsky@janestreet.com><= /span> wrote:
Indeed, the implementation from that post= did make it into
Core_kernel.=C2=A0 Here's the link:

https://github.com/janestreet/cor= e_kernel/blob/release-112.01.00/lib/core_list.ml#L380

y

On Sun, Sep 28, 2014 at 3:45 PM, Malcolm Matalka <mmatalka@gmail.com> wrote:
> https://blogs.janestreet.com/optimizing-list-map/
>
> And from the horse's mouth:
>
> https://groups.google.com/forum/#!msg/fa.cam= l/YaLYqkpn928/1jdo8a0K6AEJ
>
> Shuai Wang <wangshuai901@gmail.com> writes:
>
>> Hello list,
>>
>>
>> I am working on some stack_overflow exception in our recent projec= t written
>> in OCaml
>> and eventually it turns out that this exception is thrown by List.= map
>> function.
>>
>> By seeing the source code of OCaml's List module
>> <https://code.ohloh.net/fil= e?fid=3DP5Us_txNCMHIhpdfML6OZ8QN4Zs&cid=3DJigg8RAfQdg&s=3Docaml%20l= ist.ml&pp=3D0&fp=3D305967&fe=3Dml&ff=3D1&filterChecked= =3Dtrue&mp=3D1&ml=3D1&me=3D1&md=3D1#L3>,
>> it seems that map function
>> does not be implemented tail-recursively:
>>
>> let rec map f =3D function
>>=C2=A0 =C2=A0 =C2=A0[] -> []
>>=C2=A0 =C2=A0| a::l -> let r =3D f a in r :: map f l
>>
>>
>>
>> So my question is:
>>
>> *Why would OCaml's implementation List.map like this?=C2=A0 *<= br> >>
>> In my humble option, it definitely should be written in a tail-rec= ursive
>> way,
>> and it not, stack_overflow would be unavoidable.
>> For example in order to handle the exception,
>> I abandon the code using List.map and rewrite it into a tail-recur= sive help
>> function.
>>
>> Best,
>> Shuai
>
> --
> Caml-list mailing list.=C2=A0 Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs


--bcaec5485acc0aee5f05042c7071--