Hi, 

> I realize that this problem can be coded around, sometimes 
> with better data
> structures, or by the double reversing approach (which is 
> what I used to use)
> but my own sense of programming language aesthetics is that 
> this is a flaw, or
> at least a hole in the language that should be filled one day.

There is an implementation of VLists for OCaml. VLists are - like 
single linked lists - persistent, but have better performance,
require less memory and are GC friendlier. Here is
the announcement and a link to the paper:

http://sourceforge.net/mailarchive/forum.php?thread_id=6740097&forum_id=2988
0

Stack overflow problems should be solved. Unfortunatly you loose 
the ability of pattern matching and  List contruction with the
bracket notation.

The paper is quite nice.

Christoph Bauer