brogoff wrote:
> No doubt the implementors will want me guillotined for bringing this up again,
> but using the (still functional!) set_cdr! tail recursive functions, which do
> *not* reverse the list, are always faster than the non tail recursive
> list functions, even for small lists, at least in my experience. So I suspect
> that your "for instance" is in fact the only reason for the disparity. I'd
> welcome a counterexample.

This optimization is probably reasonable.  Note that assignment can have 
a somewhat unexpected cost when the runtime uses a generational garbage 
collector (as OCaml does).

Speaking generally, the collector would like the invariant "all pointers 
in a generation refer to younger generations", where the "younger" 
relation is reflexive.  This is true for purely functional languages, 
but not true when assignment is added.

In general, the implementation needs to add a check during assignment: 
"if the value being modified belongs to a strictly older generation than 
the value being stored, then mark it."

In the implementation of List.map using set_cdr! it should be possible 
to eliminate the check.  The cons-cell was just allocated, so it should 
belong to the minor heap.

Jason

-- 
Jason Hickey                  http://www.cs.caltech.edu/~jyh
Caltech Computer Science      Tel: 626-395-6568 FAX: 626-792-4257