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 92F547FACD for ; Sun, 28 Sep 2014 21:43:44 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.223.180; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.223.180 as permitted sender) identity=mailfrom; client-ip=209.85.223.180; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@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-ie0-f180.google.com) identity=helo; client-ip=209.85.223.180; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-ie0-f180.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtwBAONjKFTRVd+0lGdsb2JhbABggkiBGVuCfYJgs1yOa4Foh1MCcwgWAREBAQEBBwsLCRIuhAQBAQMBEhEEGQEbHQEDAQsGBQs3AgIhAQERAQUBHAYTIogHAQMJCA2dMm6LMIFygxCINwoZJw1nhjkBEQEFDoocg0SBSGQEB4J4gVMFhluMD4M1gj6CO4IQgWKNM4RWGCmCeoIcOy8BAYJIAQEB X-IPAS-Result: AtwBAONjKFTRVd+0lGdsb2JhbABggkiBGVuCfYJgs1yOa4Foh1MCcwgWAREBAQEBBwsLCRIuhAQBAQMBEhEEGQEbHQEDAQsGBQs3AgIhAQERAQUBHAYTIogHAQMJCA2dMm6LMIFygxCINwoZJw1nhjkBEQEFDoocg0SBSGQEB4J4gVMFhluMD4M1gj6CO4IQgWKNM4RWGCmCeoIcOy8BAYJIAQEB X-IronPort-AV: E=Sophos;i="5.04,615,1406584800"; d="scan'208";a="98298750" Received: from mail-ie0-f180.google.com ([209.85.223.180]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 28 Sep 2014 21:43:43 +0200 Received: by mail-ie0-f180.google.com with SMTP id ar1so15886661iec.39 for ; Sun, 28 Sep 2014 12:43:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=A9T17yCSTQLMIIuY6bi7SmBPrLNoIIaOLwBQQPQdRKQ=; b=rvLhjFTsSysEzddOiTsTftE4pd9NuQl3VmfOGQKkYhtCW2kej1k2P2ogzH1WLQ8nod Biw/DxW/IN1ub0hC6IOB/uQOO9CP1TlCBz1gH4hGJqzh9chI8exR7VWeAroGlFWaStHu 0iZBnUVo4MlyNv7rhjGvyJMiFXV9++e2PUcI/UboByrG0jci5W/fe3YuT9TAL9T2zPjB DRdxe5ipwoKSSiEW9CkFMIThPClWglWTGLiqnEwBWvvAmhlnEwhmd/NpXzc8rsUFgeNQ RefnCIflmBkplDKRcaHaOKYgfE+qt+0b3SvbsfIY8SoB1QLFGCHW4KIQduj/NK03C2M3 /8xA== X-Received: by 10.50.66.36 with SMTP id c4mr30160607igt.48.1411933035370; Sun, 28 Sep 2014 12:37:15 -0700 (PDT) MIME-Version: 1.0 Received: by 10.107.130.195 with HTTP; Sun, 28 Sep 2014 12:36:35 -0700 (PDT) In-Reply-To: References: From: Gabriel Scherer Date: Sun, 28 Sep 2014 21:36:35 +0200 Message-ID: To: Shuai Wang Cc: caml users Content-Type: multipart/alternative; boundary=001a1134cc1e051fe30504254711 Subject: Re: [Caml-list] Why List.map does not be implemented tail-recursively? --001a1134cc1e051fe30504254711 Content-Type: text/plain; charset=UTF-8 The compiler library chose to keep it's implementation simple and clean, at the cost of not being tail-recursive, and therefore unsuitable for large lists. This is documented in the manual: http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html > Some functions are flagged as not tail-recursive. A tail-recursive function uses constant stack space, while a non-tail-recursive function uses stack space proportional to the length of its list argument, which can be a problem with very long lists. > List.map f [a1; ...; an] applies function f to a1, ..., an, and builds the list [f a1; ...; f an] with the results returned by f. Not tail-recursive. Other libraries have made different design choices, so you can easily use a different List module that provides tail-recursive operations. There are several larger libraries, some (such as Batteries http://batteries.forge.ocamlcore.org/ ) which directly extend the compiler library, and are therefore usable as a drop-in replacement for it, some others (such as Core https://ocaml.janestreet.com/ocaml-core/111.28.00/doc/core/ ) which use different conventions. They all provide tail-recursive mapping functions suitable for use on long lists. (Of course you can also simply replace `List.map f li` with `List.rev_map f (List.rev li)` if you know `li` may be long.) On Sun, Sep 28, 2014 at 9: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 > --001a1134cc1e051fe30504254711 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
The compiler library chose to keep it's impl= ementation simple and clean, at the cost of not being tail-recursive, and t= herefore unsuitable for large lists. This is documented in the manual:
= =C2=A0 http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html

= >=20 Some functions are flagged as not tail-recursive. A tail-recursive function uses constant stack space, while a non-tail-recursive function uses stack space proportional to the length of its list argument, which can be a problem with very long lists.

>=C2=A0 List.map f [a1; ...; an] applie= s function f to a1, ..., an, and builds the list [f a1; ...; f an] with the results returned by f. Not tail-recurs= ive.

Other libraries have made different design choices, so yo= u can easily use a different List module that provides tail-recursive opera= tions. There are several larger libraries, some (such as Batteries http://batteries.forge.ocamlcore= .org/ ) which directly extend the compiler library, and are therefore u= sable as a drop-in replacement for it, some others (such as Core https://ocaml= .janestreet.com/ocaml-core/111.28.00/doc/core/ ) which use different co= nventions. They all provide tail-recursive mapping functions suitable for u= se on long lists.

(Of course you can also simply replace `List= .map f li` with `List.rev_map f (List.rev li)` if you know `li` may be long= .)

On Su= n, Sep 28, 2014 at 9:31 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 it turns out that this exception is thrown by List.map= function.
=
By see= ing the source code of OCaml's=C2=A0= List module, it seems that map function=C2=A0
does not be implemented tail-recursi= vely:=C2=A0

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





--001a1134cc1e051fe30504254711--