This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] Recursive lists
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Christophe Raffalli Subject: [Caml-list] About Obj (was Recursive lists)
```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
---------------------------------------------

```