From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 C9B1F7FACD for ; Mon, 29 Sep 2014 14:08:21 +0200 (CEST) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of goswin-v-b@web.de) identity=pra; client-ip=212.227.15.4; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="goswin-v-b@web.de"; x-sender="goswin-v-b@web.de"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of goswin-v-b@web.de designates 212.227.15.4 as permitted sender) identity=mailfrom; client-ip=212.227.15.4; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="goswin-v-b@web.de"; x-sender="goswin-v-b@web.de"; 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@mout.web.de) identity=helo; client-ip=212.227.15.4; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="goswin-v-b@web.de"; x-sender="postmaster@mout.web.de"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AooCALpKKVTU4w8EnGdsb2JhbABgg2HKaYFihXECgQwWAREBAQEBAQYNCQkULIQEAQEEJxNPCxgJJQ8FDRs0iCkBAxUJt0UfKw2HNASNboFZXhaDGIEdBZYfgj6CO4IPhzsTh0iKLWoBgQaBQwEBAQ X-IPAS-Result: AooCALpKKVTU4w8EnGdsb2JhbABgg2HKaYFihXECgQwWAREBAQEBAQYNCQkULIQEAQEEJxNPCxgJJQ8FDRs0iCkBAxUJt0UfKw2HNASNboFZXhaDGIEdBZYfgj6CO4IPhzsTh0iKLWoBgQaBQwEBAQ X-IronPort-AV: E=Sophos;i="5.04,620,1406584800"; d="scan'208";a="81263324" Received: from mout.web.de ([212.227.15.4]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 29 Sep 2014 14:08:21 +0200 Received: from frosties.localnet ([95.208.222.117]) by smtp.web.de (mrweb001) with ESMTPSA (Nemesis) id 0MSav6-1XiReg2Urc-00RYVb for ; Mon, 29 Sep 2014 14:08:18 +0200 Received: from mrvn by frosties.localnet with local (Exim 4.82) (envelope-from ) id 1XYZkX-0005RW-W3 for caml-list@inria.fr; Mon, 29 Sep 2014 14:08:18 +0200 Date: Mon, 29 Sep 2014 14:08:17 +0200 From: Goswin von Brederlow To: caml-list@inria.fr Message-ID: <20140929120817.GB20628@frosties> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.23 (2014-03-12) X-Provags-ID: V03:K0:jEvmuWCHAXuIsEn1xzWTZPstITRDn2N7kS9CNOAENO98Yd3N4Rq 0vqJZdm190GvOVuAQBveQvH4CVuTaen5vUCqS29GnkTdSmi5fssTKPT5pp8uKLIB0XRgd5A KFD8VRsnCx4VVgjQB83MQF+gP9w+1g4G1f6Zm0BCNGwEAKTGBuYEXAPEtRyMsf1AJyVm7WM oMEsxNpTLo1itTnWmx3kw== X-UI-Out-Filterresults: notjunk:1; Subject: Re: [Caml-list] Why List.map does not be implemented tail-recursively? And I'll will do the same, reply anyway. You can't write List.map tail recursive unless: 1) You use List.rev (List.rev_map fn list). or 2) Use hacks to create a mutable list so you can grow it head to tail instead of tail to head. The fastest code seems to be when you do List.map recursively up to some limit (say 1000 items) and return the remainder. Repeat and glue the lists together into one large list using hacks. MfG Mrvn On Sun, Sep 28, 2014 at 01:45:41PM -0600, Anthony Tavener wrote: > (Oh, Gabriel beat me to the punch, but I'll add my reply anyway.) > > The standard library is a fairly minimal library of basic features. Not a > high-level full-featured library which helps you make good choices. :) > > However, the documentation (in .mli files) is fairly clear about what is > tail-recursive or not. And there is rev_map: > > val rev_map : ('a -> 'b) -> 'a list -> 'b list > (** [List.rev_map f l] gives the same result as > {!List.rev}[ (]{!List.map}[ f l)], but is tail-recursive and > more efficient. *) > > > On Sun, Sep 28, 2014 at 1:31 PM, Shuai Wang wrote: > > > 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