It seems the only way to make such recursive list is by using Obj
module.
Copy the list and make it recursive
let cycle lst = match lst with
| [] -> []
| _ ->
let rec get_last_cell = function
| [] -> assert false
| _::[] as last -> last
| _::tl -> (get_last_cell tl)
in
let new_lst = List.map (fun x -> x) lst in
let last_cell = get_last_cell new_lst in
Obj.set_field (Obj.repr last_cell) 1 (Obj.repr new_lst);
new_lst
Create recursive list and then insert new cons cells
let cycle lst = match lst with
| [] -> []
| hd::tl ->
let rec loop cell lst =
match lst with
| [] -> ()
| hd::tl ->
let new_cell = [hd] in
let new_cell_obj = Obj.repr new_cell in
let cell_obj = Obj.repr cell in
Obj.set_field new_cell_obj 1 (Obj.field cell_obj 1);
Obj.set_field cell_obj 1 new_cell_obj;
loop new_cell tl
in
let rec cyc_lst = hd::cyc_lst in
loop cyc_lst tl;
cyc_lst
The idea is pretty straightforward:
- Create recursive list
cyc_lst
with only one element. - Insert one or more new cons cells immediately before tail of
cyc_lst
.
Example
cycle [1;2]
Create recursive list
cyc_lst
. It is represented in memory as a self-recursive cons celllet rec cyc_lst = hd::cyc_lst .--------. | | | +---+-|-+ `->| 1 | * | +---+---+
Create
new_cell
using 2 as the only elementlet new_cell = [hd] cell new_cell .--------. | | | +---+-|-+ +---+---+ `->| 1 | * | | 2 | X | +---+---+ +---+---+
Set
new_cell
tail pointer to first cellObj.set_field new_cell_obj 1 (Obj.field cell_obj 1) cell new_cell .--------.--------------. | | | | +---+-|-+ +---+-|-+ `->| 1 | * | | 2 | * | +---+---+ +---+---+
Set
cell
tail pointer tonew_cell
Obj.set_field cell_obj 1 new_cell_obj cell new_cell .-----------------------. | | | +---+---+ +---+-|-+ `->| 1 | *------->| 2 | * | +---+---+ +---+---+
I hope GC is ok with such list manipulations. Let me know if it is not.