[Caml-list] About Obj (was Recursive lists)

[Christophe Raffalli <Christophe.Raffalli@univ-savoie.fr>]

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

Jean-Christophe Filliatre wrote:
> sejourne_kevin wrote:
> 
>>(** Take a list and connect the end on the beginning
>>   Copyright : Kévin ;)
>>*)
>>let cycle l =
>>  let rl= ref l in
>>  let rec go_fin = function
>>      [] -> invalid_arg "cycle:[] can't be !"
>>    | [x] as f -> Obj.set_field (Obj.repr f) 1 (Obj.repr !rl);l
>>    | x::reste-> go_fin reste
>>  in go_fin l
>>;;
>>I haven't test GC issu.
> 
> 
> This shouldn't be advised, and not even posted on this list.
> 

And how do you write a tail recursive map doing only one structure 
traversal (which is important with the penalty for memory access) on 
immutable list without the Obj module ?

However, using Obj you can write once for all some functions to 
construct a list starting with its head, for instance with the following 
interface (you can write an implmentation with Stack but the "extract" 
function will not be in constant time):

type 'a prelist (* mutable type of a list under construction *)

val start : unit -> 'a prelist
val extract : 'a prelist -> 'a list
val cons : 'a -> 'a prelist -> unit

Then, map can be rewritten

let map f l =
   let pl = start () in
   let rec fn = function
     [] -> extract pl
   | a::l -> cons (f a) pl; fn l
   in
   fn l

This kind of code is not that intolerable and you can advise people to 
use Obj module to write an implementation of the above signature (if 
they are sure they really need it).
Since use of the Obj module is restricted to a small module, it will be 
easy to adapt to follow the evolution of the language.

The presence of the Obj module in the standard distribution itself tells 
that it is necessary and not only for C interface (this is not its main 
usage anyway, its main usage is to compile code typable only with 
dependent type).

Here is a possible implementation of the above module (I think it could 
be use to improve the actual implementation of map and fold_right in the 
standard library)

type 'a prelist = { mutable start : 'a list; mutable current : 'a list}

let start () = { start = []; current = []}

let cons a pl = match pl.current with
   [] -> let l = [a] in pl.current <- l; pl.start <- l
| l ->
	let l' = [a] in Obj.set_field (Obj.repr l) 1 (Obj.repr l');
         pl.current <- l'

let extract pl =
   let r = pl.start in
   pl.current <- []; pl.start <- [];
   (* to guaranty that we can not mute the list once it has been
   extracted *)
   r

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature
---------------------------------------------

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]