From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 37D4A7FACD for ; Mon, 29 Sep 2014 07:40:53 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of mjambon@gmail.com) identity=pra; client-ip=209.85.192.182; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="mjambon@gmail.com"; x-sender="mjambon@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of mjambon@gmail.com designates 209.85.192.182 as permitted sender) identity=mailfrom; client-ip=209.85.192.182; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="mjambon@gmail.com"; x-sender="mjambon@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-pd0-f182.google.com) identity=helo; client-ip=209.85.192.182; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="mjambon@gmail.com"; x-sender="postmaster@mail-pd0-f182.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtwBAIXwKFTRVcC2m2dsb2JhbABgg2GDWLZNkQWIWRYBEQEBAQEBBgsLCRQshAMBAQEDARIRBBEIAS0KAQEDAQsBBQUYAgIFBBIIAwICCQMCAQIBDxMBBQEKAREGDQEFAgEBDgIOiAgDCQgFCJ1JboswhQKIXycDCocyAQUOgR6MQoUvgVMBBIUUAgOGNocbgzWCPoI7g3KFcIdDhFZBgWyDSEwBAYJIAQEB X-IPAS-Result: AtwBAIXwKFTRVcC2m2dsb2JhbABgg2GDWLZNkQWIWRYBEQEBAQEBBgsLCRQshAMBAQEDARIRBBEIAS0KAQEDAQsBBQUYAgIFBBIIAwICCQMCAQIBDxMBBQEKAREGDQEFAgEBDgIOiAgDCQgFCJ1JboswhQKIXycDCocyAQUOgR6MQoUvgVMBBIUUAgOGNocbgzWCPoI7g3KFcIdDhFZBgWyDSEwBAYJIAQEB X-IronPort-AV: E=Sophos;i="5.04,618,1406584800"; d="scan'208";a="98332100" Received: from mail-pd0-f182.google.com ([209.85.192.182]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 29 Sep 2014 07:40:52 +0200 Received: by mail-pd0-f182.google.com with SMTP id y10so4712118pdj.41 for ; Sun, 28 Sep 2014 22:40:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=5bfpWKFHRLl1ChRM2tNRXQMzP26bPmiLW2cLN4aCEl4=; b=IPpevJWRKHl4qMVs3GfSHBf7bdVqzGbbn6wJm+yu2zKWzDODiIwR7gPX+DEuGdM5Cu /ABCMMJL0MvSAI0VbSDSJheN6c7t68D3/isOHqsbvcmrbP8Qz6kUgOdwCPYoVrONPZV+ K5s/zpvtjH65mSR7iEga7vs4RZ61OdMJbFAeq9SfmFiFFIG2ZjAn1VZsub9lVw7kCEte 7XMLFzbXNwJKngh/s3PWUmRa40Ar/F23btYcpNXWqlJ90mk3cZNbbceETrl1t5TKl5mJ xDfPrvj7NVryOdOx9xym81RxBd0w0hWFupyAlRdVMiwBBvZUg9owDjLpUxsmrpk/fPu5 Nlnw== X-Received: by 10.66.254.195 with SMTP id ak3mr55245952pad.142.1411969250143; Sun, 28 Sep 2014 22:40:50 -0700 (PDT) Received: from [192.168.2.7] (c-67-180-86-2.hsd1.ca.comcast.net. [67.180.86.2]) by mx.google.com with ESMTPSA id i13sm10647953pdm.93.2014.09.28.22.40.49 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 28 Sep 2014 22:40:49 -0700 (PDT) Sender: Martin Jambon Message-ID: <5428F0DF.9090400@ens-lyon.org> Date: Sun, 28 Sep 2014 22:40:47 -0700 From: Martin Jambon User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.0 MIME-Version: 1.0 To: Anthony Tavener CC: Yaron Minsky , "caml-list@inria.fr" , Shuai Wang References: <87bnpzpm0l.fsf@gmail.com> In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [Caml-list] Why List.map does not be implemented tail-recursively? On Sun 28 Sep 2014 09:09:48 PM PDT, Anthony Tavener wrote: > 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. I also was obsessed with this when I started using OCaml a long time ago and was worried that list operations would double the cost of my algorithms (do the math: this is not how it works). Unfortunately the practice obfuscates the source code. It makes it tricky to add or remove an operation in the chain, and overall it's an unnecessary cognitive burden for anyone reading the code. These optimizations should be done outside of the application code, either in the list library or by the compiler; most of the time they are absolutely needless anyway. Martin > 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 > >> > , > >> 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 > > >