Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Gabriel Scherer <gabriel.scherer@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2356 bytes --]

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 <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 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
>

[-- Attachment #2: Type: text/html, Size: 9985 bytes --]