From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <mmatalka@gmail.com>
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 EA2B87FACD
	for <caml-list@sympa.inria.fr>; Sun, 28 Sep 2014 21:45:16 +0200 (CEST)
Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender
  authenticity information available from domain of
  mmatalka@gmail.com) identity=pra; client-ip=74.125.82.42;
  receiver=mail3-smtp-sop.national.inria.fr;
  envelope-from="mmatalka@gmail.com";
  x-sender="mmatalka@gmail.com"; x-conformance=sidf_compatible
Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of
  mmatalka@gmail.com designates 74.125.82.42 as permitted
  sender) identity=mailfrom; client-ip=74.125.82.42;
  receiver=mail3-smtp-sop.national.inria.fr;
  envelope-from="mmatalka@gmail.com";
  x-sender="mmatalka@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-wg0-f42.google.com) identity=helo;
  client-ip=74.125.82.42;
  receiver=mail3-smtp-sop.national.inria.fr;
  envelope-from="mmatalka@gmail.com";
  x-sender="postmaster@mail-wg0-f42.google.com";
  x-conformance=sidf_compatible
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AtMBAE1kKFRKfVIqm2dsb2JhbABggmt2Tcoah1MCexYBEQEBAQEBBgsLCRQshAQBAQMBEhUZARsdAQMBCwYFCxYlDwEEDQIRAQUBIhMiiAcBAwkIAQQInTJujSKDEIg3ChknDWeGOQERAQEEDo1ggjAHhEsFhRQCkQmCPoI7ghCPFYRWQYUUbAGCSQEBAQ
X-IPAS-Result: AtMBAE1kKFRKfVIqm2dsb2JhbABggmt2Tcoah1MCexYBEQEBAQEBBgsLCRQshAQBAQMBEhUZARsdAQMBCwYFCxYlDwEEDQIRAQUBIhMiiAcBAwkIAQQInTJujSKDEIg3ChknDWeGOQERAQEEDo1ggjAHhEsFhRQCkQmCPoI7ghCPFYRWQYUUbAGCSQEBAQ
X-IronPort-AV: E=Sophos;i="5.04,615,1406584800"; 
   d="scan'208";a="81189322"
Received: from mail-wg0-f42.google.com ([74.125.82.42])
  by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 28 Sep 2014 21:45:16 +0200
Received: by mail-wg0-f42.google.com with SMTP id z12so1671031wgg.25
        for <caml-list@inria.fr>; Sun, 28 Sep 2014 12:45:16 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20120113;
        h=from:to:cc:subject:references:date:in-reply-to:message-id
         :user-agent:mime-version:content-type;
        bh=1aSLlZ2jGaTWxk1uY6Jsc2lKRlmmfUYL/eNfauXuA84=;
        b=txlg/nhcwtJl9R5LIb3GDuNSZEsHxF9KI8/LQq0xBOg2KOuThNQalIe9+dV7t7ynho
         NK3Ux0rTQmfee46wQc5U0S5S1qYJnyC90uonhKbhA000bm61v1iRBW4YmkB+a94H/HB4
         rpbhaI6c3L8J8+e+kBvv8hZUGGefybtujafVl7iwxLx6a/rsNTfKRCbwonPPK4Q0i9oQ
         vIS/t7+wAw0IrXuTmk95Fj2A5KuKQbkhIzZ9k8o/4Ji6iRhTBvk9t9N+umi3CJe/n6KS
         rxuSI5KpnBnnsLkUGyDS6KNAjLw6rWm0OXcZYs5dGeOcZ8qtMM47DrfKF8s/p108oS02
         rqOg==
X-Received: by 10.180.94.163 with SMTP id dd3mr61838882wib.31.1411933516043;
        Sun, 28 Sep 2014 12:45:16 -0700 (PDT)
Received: from localhost ([2a01:7e00::f03c:91ff:fe70:2696])
        by mx.google.com with ESMTPSA id di1sm9420626wib.21.2014.09.28.12.45.14
        for <multiple recipients>
        (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
        Sun, 28 Sep 2014 12:45:14 -0700 (PDT)
From: Malcolm Matalka <mmatalka@gmail.com>
To: Shuai Wang <wangshuai901@gmail.com>
Cc: caml-list@inria.fr
References: <CAEQMQonxc3uAHb=6GfYRk4nYTOcx2nHs+ObHZ4P2Rz8mPbdJow@mail.gmail.com>
Date: Sun, 28 Sep 2014 19:45:14 +0000
In-Reply-To: <CAEQMQonxc3uAHb=6GfYRk4nYTOcx2nHs+ObHZ4P2Rz8mPbdJow@mail.gmail.com>
	(Shuai Wang's message of "Sun, 28 Sep 2014 15:28:23 -0400")
Message-ID: <87bnpzpm0l.fsf@gmail.com>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
Subject: Re: [Caml-list] Why List.map does not be implemented
 tail-recursively?

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 <wangshuai901@gmail.com> 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