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 61D8F7FACD for ; Mon, 29 Sep 2014 04:31:52 +0200 (CEST) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of wangshuai901@gmail.com) identity=pra; client-ip=209.85.215.53; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="wangshuai901@gmail.com"; x-sender="wangshuai901@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of wangshuai901@gmail.com designates 209.85.215.53 as permitted sender) identity=mailfrom; client-ip=209.85.215.53; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="wangshuai901@gmail.com"; x-sender="wangshuai901@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-la0-f53.google.com) identity=helo; client-ip=209.85.215.53; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="wangshuai901@gmail.com"; x-sender="postmaster@mail-la0-f53.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtYBAIXDKFTRVdc1m2dsb2JhbABgg2Fbgn22PI8dgWiHUwJ5CBYBEQEBAQEBBgsLCRQshAMBAQEDARIRBBkBGxIMAwELBgULAwoNHQICIQEBEQEFAQoSBgESEgIOiAcBAwkIDZ02boswgXKDEIhBChknAwpnhjkBEQEFDo1ggiwLgniBUwEEhRQCA5EGgj6CO4IQgWKNM4RWGCmFMCEvAQGCSAEBAQ X-IPAS-Result: AtYBAIXDKFTRVdc1m2dsb2JhbABgg2Fbgn22PI8dgWiHUwJ5CBYBEQEBAQEBBgsLCRQshAMBAQEDARIRBBkBGxIMAwELBgULAwoNHQICIQEBEQEFAQoSBgESEgIOiAcBAwkIDZ02boswgXKDEIhBChknAwpnhjkBEQEFDo1ggiwLgniBUwEEhRQCA5EGgj6CO4IQgWKNM4RWGCmFMCEvAQGCSAEBAQ X-IronPort-AV: E=Sophos;i="5.04,617,1406584800"; d="scan'208";a="81205107" Received: from mail-la0-f53.google.com ([209.85.215.53]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 29 Sep 2014 04:31:51 +0200 Received: by mail-la0-f53.google.com with SMTP id ty20so4536232lab.26 for ; Sun, 28 Sep 2014 19:31:50 -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 :content-type; bh=1ein/dqJKWsi7+2R48jvKdUaAGS9Y4SRm75pk8V/eCE=; b=ozjfUpRc/l3/81Rqnon9je+IRNXgnHw9/89TOp/zIpCfCDDngKjOjMHvStqCngTu8Q 1WD47c3JiH/TlSytsTKAm0ISU+YRZwzW5lJkHsgJMLU4gSG7Qhf7yqHRPlEDW4TWhm/l LBBu56CwvnPE/tvv34l+ViPgcS3wYQrwjWol6+6wBr88NaGhRfJ97afQ3MHKcZ3HfARq lpxt9U3q2QrUfj5BOcLOk9F8OpVO5HaradTCuTbZu5iBFLRjApfozhubAEXCggSew5NN tcAXYsxnj1cA4d53+G1ocX9XB3+6tuFWxaetfVT5fHJBYPkUnfkwxqlr7OspSEyf1gh0 9tng== MIME-Version: 1.0 X-Received: by 10.112.14.199 with SMTP id r7mr34447993lbc.58.1411957910046; Sun, 28 Sep 2014 19:31:50 -0700 (PDT) Received: by 10.114.59.101 with HTTP; Sun, 28 Sep 2014 19:31:49 -0700 (PDT) In-Reply-To: References: <87bnpzpm0l.fsf@gmail.com> Date: Sun, 28 Sep 2014 22:31:49 -0400 Message-ID: From: Shuai Wang To: Yaron Minsky , caml-list@inria.fr Content-Type: multipart/alternative; boundary=001a11332feeaa8cfc05042b1180 Subject: Re: [Caml-list] Why List.map does not be implemented tail-recursively? --001a11332feeaa8cfc05042b1180 Content-Type: text/plain; charset=UTF-8 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 > --001a11332feeaa8cfc05042b1180 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Wow,=C2=A0List.rev_map f = (List.rev li) looks very=C2=A0elegant, thank you all for the helpful=C2=A0m= aterials! 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=C2=A0contribute to the community :)

Best,
Shuai=C2=A0



On Sun, Sep 28, 2014 at 4:26 PM, Yaron Minsky <yminsky@janestreet.com> wrote:
Indeed, t= he 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

--001a11332feeaa8cfc05042b1180--