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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id DD6877FACD for ; Sun, 28 Sep 2014 21:45:43 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of anthony.tavener@gmail.com) identity=pra; client-ip=209.85.220.174; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="anthony.tavener@gmail.com"; x-sender="anthony.tavener@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of anthony.tavener@gmail.com designates 209.85.220.174 as permitted sender) identity=mailfrom; client-ip=209.85.220.174; receiver=mail2-smtp-roc.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 (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-vc0-f174.google.com) identity=helo; client-ip=209.85.220.174; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="anthony.tavener@gmail.com"; x-sender="postmaster@mail-vc0-f174.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtYBAONjKFTRVdyum2dsb2JhbABggkiBGU0Ogn3HD4dTAnMIFgERAQEBAQEGCwsJFCyEBAEBAwESEQQZARsdAQMBCwYFCzcCAiEBAREBBQEcBhMiiAcBAwkIDZ0yboswgXKDEIg3ChknDWeGOQERAQEEDo1ggiwEB4J4gVMFhluEdIcbgzWCPoI7ghCPFYRWGCmFMx4vAYJJAQEB X-IPAS-Result: AtYBAONjKFTRVdyum2dsb2JhbABggkiBGU0Ogn3HD4dTAnMIFgERAQEBAQEGCwsJFCyEBAEBAwESEQQZARsdAQMBCwYFCzcCAiEBAREBBQEcBhMiiAcBAwkIDZ0yboswgXKDEIg3ChknDWeGOQERAQEEDo1ggiwEB4J4gVMFhluEdIcbgzWCPoI7ghCPFYRWGCmFMx4vAYJJAQEB X-IronPort-AV: E=Sophos;i="5.04,615,1406584800"; d="scan'208";a="98299060" Received: from mail-vc0-f174.google.com ([209.85.220.174]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 28 Sep 2014 21:45:43 +0200 Received: by mail-vc0-f174.google.com with SMTP id hy4so739821vcb.19 for ; Sun, 28 Sep 2014 12:45:41 -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=aUM88z3CiLw8jhP8xV+T6BTWzKOinwJNHNaQhTdozTM=; b=WNzqKt8Z8Fnq3qkDeBuJwO0ZwaIfQ6iqQ/c6a0gfgdE/1PrS0mgm7OkL7e4xzOftpw WeXNS28X5EX7RqWzZ6FbZfgKU1RDWhC+qocuYFhrKOKABTlJg3plQacT6Jp25B8jtizY EFtsWuV3Y7R+F/axr2hcqc1fUh16VmAt+WymijV4kYG6TzXGIa5eC2JJ1bN7XMWonu95 CWdh4z4YnJwj4QfLPsnUcTnOm8Rfl9cc8OrJXOE+gt+wuiGMV7wpjxlUedZgYRes89m3 K+tQ9A+Pwke1LIQtzSCc3gaVJA8U3T5I7WXv+3d8GV4oz1PMu/rfS5h7oSflbubVIurJ dqpQ== MIME-Version: 1.0 X-Received: by 10.52.141.45 with SMTP id rl13mr1623149vdb.49.1411933541760; Sun, 28 Sep 2014 12:45:41 -0700 (PDT) Received: by 10.220.159.133 with HTTP; Sun, 28 Sep 2014 12:45:41 -0700 (PDT) In-Reply-To: References: Date: Sun, 28 Sep 2014 13:45:41 -0600 Message-ID: From: Anthony Tavener To: Shuai Wang Cc: "caml-list@inria.fr" Content-Type: multipart/alternative; boundary=bcaec51ba1b934046f05042565ae Subject: Re: [Caml-list] Why List.map does not be implemented tail-recursively? --bcaec51ba1b934046f05042565ae Content-Type: text/plain; charset=UTF-8 (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 > --bcaec51ba1b934046f05042565ae Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
(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 li= brary which helps you make good choices. :)

Howeve= r, the documentation (in .mli files) is fairly clear about what is tail-rec= ursive or not. And there is rev_map:

va= l rev_map : ('a -> 'b) -> 'a list -> 'b list
=
(** [List.rev_map f l] gives the same result as
=C2=A0 =C2= =A0{!List.rev}[ (]{!List.map}[ f l)], but is tail-recursive and
= =C2=A0 =C2=A0more efficient. *)


On Sun, Sep 28, 2014 at 1:3= 1 PM, Shuai Wang <wangshuai901@gmail.com> wrote:
Hello= list,

I am working on= some stack_overflow exception in our recent project written in OCaml
=
and eventually i= t turns out that this exception is thrown by List.map function.

By seeing the source code = of OCaml's=C2=A0List module, it = seems that map function=C2=A0
does not be implemented tail-recursively:=C2=A0

let rec map function
    [] -> []
  | a::l -> let r =3D f a in r :: map f l





--bcaec51ba1b934046f05042565ae--